A Coin Game

Problem code: G3

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.

Input

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.

Output

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.

Example

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

Output details

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.

Date: 2009-08-15
Time limit: 1s
Source limit: 50000
Languages: C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK CAML CLPS PRLG WSPC


Comments

Hi, i have a doubt, in test

javasoul @ 1 Sep 2009 03:48 PM

Hi, i have a doubt, in test case 2, why can't marry first move 3 to 2 ?

 hi,   I'm a little confused

sanjay_ankur @ 1 Sep 2009 04:17 PM

 hi,

 

I'm a little confused about the move that is supposed to be printed. For eg in case 2, wouldn't the leftmost possible coin be "move 3 to 2" ? 

 

regards,

 

Ankur

Because if she did that, she

admin @ 1 Sep 2009 04:18 PM

Because if she did that, she would lose the game. The player can move a cell as far left so long as he does not jump over a coin.

uhm, Mary: 3 -> 2 Johnny: 5->

sanjay_ankur @ 1 Sep 2009 04:21 PM

uhm,

Mary:

3 -> 2

Johnny:

5-> 4

Mary:

4->3

 

now coins are at 1,2,3

Mary wins..

 

Is there something I'm not fully understanding?

" The player can move a cell

sanjay_ankur @ 1 Sep 2009 04:23 PM

" The player can move a cell as far left so long as he does not jump over a coin."

okay.. That changes things.. Understood. 

Hi Does that means we need

codesnooker @ 1 Sep 2009 04:29 PM

Hi

Does that means we need to consider the initial location of the coins placed on the cells?

 

 

 

Yes

admin @ 1 Sep 2009 04:34 PM

Yes

 hi, Result says SIGSEGV :(.

sanjay_ankur @ 1 Sep 2009 04:45 PM

 hi,

Result says SIGSEGV :(. Its running properly on my system, small inputs though. Is there a way to find out where its segfaulting? I have checked the array bounds etc. 

gcc-4.4.1-2 if that means anything.


 

 

Can you please fix the

triplem @ 1 Sep 2009 05:01 PM

Can you please fix the formatting of the input section.. it says 1 N 10000 and, more importantly, (1 p1 < p2 < ... < pn 10) which doesn't seem to make much sense.

Fixed.

admin @ 1 Sep 2009 05:05 PM

Fixed.

for the 3rd example, Move 9

cgy @ 1 Sep 2009 05:33 PM

for the 3rd example, Move 9 to 8 is also a possible solution.

so, output which one first?

sorry and I just see

cgy @ 1 Sep 2009 05:36 PM

sorry and I just see that...

" 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."

 

Read the problem statement.

admin @ 1 Sep 2009 05:36 PM

Read the problem statement. This is explained in it.

who will play 1st ?? marry or

mcsharma1990 @ 1 Sep 2009 07:57 PM

who will play 1st ?? marry or johnny???

Mary.

admin @ 1 Sep 2009 08:08 PM

Mary.

@admin: I cant see figures in

avd122 @ 1 Sep 2009 09:58 PM
@admin: I cant see figures in test case 3 solution

@admin: yes, where is the

shubhamgupta @ 2 Sep 2009 01:20 PM

@admin: yes, where is the figure for the 3rd test case?

Will check out the issue with

admin @ 2 Sep 2009 01:59 PM

Will check out the issue with figures. However, the problem statement explains the idea properly :)

  Paras Mendiratta > Does

Aby @ 2 Sep 2009 07:05 PM

 

Paras Mendiratta

> Does that means we need to consider the initial location of the coins placed on the cells?

 

Aniruddha (Codechef) -

>> Yes

 

If this is the case, then how come in  Test Case 1 Johny is able to move coin from cell 3 to 2.Also can any player move coin by more than 1 cells. i.e. say from 5 to 3.

 

Thanks,

Abhijeet

Johnny can move from cell 3

admin @ 2 Sep 2009 07:14 PM

Johnny can move from cell 3 to 2 because the coin at position 2 has been moved to 1 by Mary. Your second question has been answered in the problem statement :)

  Problem statement : " If

Aby @ 2 Sep 2009 07:22 PM

 

Problem statement : " If there are still several moves, show her the move that moves the coin as far as possible to the left."

This means coin could be moved by more than 1 cells. Correct?

Yes

admin @ 2 Sep 2009 07:33 PM

Yes

" If there are still several

Shitij @ 3 Sep 2009 09:26 AM

" If there are still several moves, show her the move that moves the coin as far as possible to the left"

 

1. does it necessarily mean that Mary moves the coin as far left as possible ?

ex- if mary can move a coin by 1 position or 2 positions, she always moves it by 2 positions (not by one position) and this is a  part of the "perfect strategy"  ?? So same thing applies to Johny (he's a perfect player too )??

 

also,

is Mary's winning move always the first move she plays ??

A general question. Does  a

mubin_skzr @ 4 Sep 2009 08:47 PM

A general question. Does  a time-out solution means correct solution but timed-out or only timed-out without any information about the solution?

the latter

balakrishnan_v @ 4 Sep 2009 09:16 PM

the latter

please fix images in this

st0le @ 5 Sep 2009 10:17 PM

please fix images in this challenge and the other ones aswell ...

  Dear Admin, May you please

Amit Mittal @ 5 Sep 2009 11:03 PM

 

Dear Admin,

May you please provide a sample input and output file for this problem (may not contain even a single actual test case or for that matter even a valid test case) that you use for automated judgement? I am just intrested in the 'specific' format of input and output for this particular problem as required by the automated system.

My algorithm is an O(n) algorithm per test case (precisely 2O(n/2)) and still it is exceeding time limit of 1 sec (which I believe is a per test case limit). Given that at max, n (number of coins) can be 10,000 only, it is highly unlikely that my loops are taking more than 1 sec (what can be slower than 0.1 ms per iteration??? 0.1ms for an iteration with simple calculations is a lot of time). I switched to C++ from C# due to input parsing issues and I strongly suspect that even in this case I am facing input/output issues and not the algorithmic issues due to which the automated system is raising timeouts.

I hope you will  help me out.

 

Thanks

The input and output

admin @ 7 Sep 2009 02:09 PM

The input and output specifications are mentioned in the problem statement itself. You have to read from stdin and output the answers to stdout.

" If there are still several

neoanderson @ 8 Sep 2009 07:38 PM


" If there are still several moves, show her the move that moves the coin as far as possible to the left"

 

Can there be a case where  a particular coin can give us more than one winning move?

like: move 20 to 18  or move  20 to 12 and both of them are winning?

 


is  p1<p2<p3 ..... <pn ? are

neoanderson @ 8 Sep 2009 07:40 PM

is  p1<p2<p3 ..... <pn ?

are the positions are input in sorted order?

 

Both your questions are

admin @ 8 Sep 2009 07:42 PM

Both your questions are answered in the problem statement :)

#include<stdio.h>

nitin14 @ 18 Sep 2009 11:43 PM
  1. #include<stdio.h>
  2. #include<conio.h>
  3. using namespace std;
  4. int p[10000];
  5. main(){
  6.   int t,n;scanf("%d",&t);while(t--){
  7.     scanf("%d",&n);
  8.     for(int i=1;i<=n;i++)scanf("%d",&p[i]);
  9.     int val=0;
  10.     vector<int> t;
  11.     for(int i=n;i>0;i-=2){
  12.       int diff=p[i]-p[i-1]-1;
  13.       val^=diff;
  14.       t.push_back(diff);
  15.     }
  16.     if(!val)puts("Johnny wins");
  17.     else {
  18.          puts("Mary wins");
  19.          int a=t.size()-1;
  20.          while(1){
  21.            int d=val^t[a];
  22.            if(d<=t[a]){
  23.             int b=n-2*a;
  24.             printf("Move %d to %dn",p[b],p[b]-(t[a]-d));
  25.             break;
  26.            } else if(d-t[a]<=p[n-2*a-1]-p[n-2*a-2]-1){
  27.             int b=n-2*a;
  28.             printf("Move %d to %dn",p[b-1],p[b-1]-(d-t[a]));
  29.             break;
  30.            }
  31.            a--;
  32.          }
  33.     }
  34.     puts("");
  35.   }
  36. }

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions