A Coin Game
All submissions for this problem are available.
Once again, the smart friends Johnny and Mary have invented a new game. This time, the game is played with their coins and a strip of paper divided into cells. The cells are numbered from the left, starting from 1.
Before the game starts, Johnny and Mary put some coins at some random cells on the strip, each coin in a cell. They alternatively take their turn to play the game. At each step, a player must take a coin and move it to a cell to the left of it. There is at most one coin in a cell at any time of the game. Of course, a coin cannot jump over another coin.
The rule is simple: whoever cannot move loses the game. Mary takes her turn first.
Could you tell them who will win the game, provided that the winner will play the perfect strategy? If Mary could win the game, show her a winning move. If there are several winning moves, show her the winning move that uses the leftmost possible coin. If there are still several moves, show her the move that moves the coin as far as possible to the left.
The first line contains t, the number of test cases (about 100). Each test case has the following form:
- The first line contains an integer N (1 ≤ N ≤ 10000) describing the number of coins on the strip.
- The second line contains N integers p1, p2, ..., pn (1 ≤ p1 < p2 < ... < pn ≤ 109) representing the initial position of the coins.
Each test case is separated by a blank line.
For each test case, print either the string "Mary wins" or "Johnny wins" depending on who will win the game. If Mary could win the game in the next line, print the string "Move a to b" describing the desired winning move, where a is replaced by the position of the coin to move and b is replaced by the new position of that coin.
Remember to print a blank line after the output for each test case.
Input: 3 2 2 3 3 1 3 5 4 2 4 6 9 Output: Johnny wins Mary wins Move 5 to 4 Mary wins Move 2 to 1
Case 1: Mary's only possible move is to move the coin at position 2 to position 1. Johnny then moves 3 to 2 and wins the game.
Case 2: After Mary moves 5 to 4, the only possible move for Johnny is to move 3 to 2. Mary then finishes the game by moving 4 to 3.
Case 3: (see the above figure) Among the winning moves, moving 2 to 1 uses the leftmost possible coin.
|Time Limit:||0.158261 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.