GAME OF ARRAY
All submissions for this problem are available.
Oliver loves playing games. He wants to play a game with his friend, Flash, using an array, A, of N distinct integers. The rules are as follows:
- Flash always plays first and the two players move in alternating turns.
- In a single move, a player chooses the maximum element currently present in the array and removes it as well as all the other elements to its right. For example, if A = [2, 3, 5, 4, 1], then it becomes A = [2, 3] after the first move because we remove the maximum element (i.e., 5) and all elements to its right (i.e., 4 and 1).
- The modifications made to the array during each turn are permanent, so the next player continues the game with the remaining array. The first player who is unable to make a move loses the game.
The first line contains a single integer T denoting the number of games. The 2.T subsequent lines describe each game array over two lines:
- The first line contains a single integer, N, denoting the number of elements in A.
- The second line contains N distinct space-separated integers describing the respective values of A1, A2, ..., AN for array A.
For each game, print the name of the winner on a new line (i.e., either FLASH or OLIVER).
Should contain all the constraints on the input data that you may have. Format it like:
- Array A contains N distinct integers.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 105
- 1 ≤ Ai ≤ 109
- The sum of N over all games does not exceed 105.
Input: 2 5 5 2 6 3 4 2 3 1 Output: OLIVER FLASH
Oliver and Flash play the following two games:
1. Initially, the array looks like this: [5, 2, 6, 3, 4]. In the first move, Flash removes 6 and all the elements to its right, resulting in: A = [5, 2]. In the second move, Oliver removes 5 and all the elements to its right, resulting in: A = . At this point, the array is empty and Flash cannot make any more moves. This means Oliver wins, so we print OlLIVER on a new line.
2. In the first move, Flash removes 3 and all the elements to its right, resulting in A = . As there are no elements left in the array for Oliver to make a move, Flash wins and we print FLASH on a new line.
|Time Limit:||10 sec|
|Source Limit:||1000000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions