The Matrix GameProblem code: SNCK01 |
All submissions for this problem are available.
[Problem Idea : Varun Jalan]
Two players A and B play the following game.
1) First, a matrix M of size N*M is chosen, and filled with non-zero numbers.
2) Player A starts the game and the players play alternately.
3) In his turn, a player chooses any row which has atleast one non zero nuumber in it. In this row, the leftmost non zero number is chosen. Let this number be K. The player subtracts any number between 1 and K inclusive from it.
4) The game ends when all the numbers in the matrix M are 0.
5) The player who plays last wins the game.
Given N,M and the initial matrix, determine who wins the game.
Assume that both players play optimally.
Input:
The first line contains the number of test cases T.
Each test case consists of 2 numbers N and M. There follow N lines each having M integers. The jth number on the ith line is the number M[i][j].
There is a blank line between consecutive test cases.
Output:
Output T lines, one for each case. Output "FIRST" if player A wins, else output "SECOND".
Constraints :
T <= 1000
1 <= N,M <= 50
The initial matrix values are between 1 and 50 inclusive.
Time limit : 2 seconds.
Sample Input :
3 2 2 1 1 1 1 1 3 2 1 1 2 2 3 2 3 2
Sample Output:
SECOND FIRST SECOND
| Date: | 2009-11-13 |
| Time limit: | 2s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ 4.0.0-8 C++ 4.3.2 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 ERL CAML CLPS PRLG WSPC BF ICK JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
what are test cases...?!!
what are test cases...?!!
line 5: "substracts any
line 5: "substracts any number means" ... one(1) number?
line 5: "substracts any
line 5: "substracts any number" means ... one(1) number?
From K he can substract any
From K he can substract any number between 1 and K and not necessarily 1 or K.
we should subtract between
we should subtract between 1-k ??
do we subtract from the whole
do we subtract from the whole ROW or just from tat cell
Yah its me again Busted again
Yah its me again Busted again assholes!!!!!!!!!!!!
Come on fuckin block my account?
I got more brains than your dad fuckers.
Heard of dynamic IP? Yah u gonna get your asses fucked motherfuckers!
Cya later, i gotta go and fuck ur moms.
send a mail to fuckmesideways@gmail.com if u need a pic of me fuckin ur mom.
SAALO BHOSADIKO JAAKE APNI MAA CHUDAO.
SABKA TIME KHARAB KAR RAHE HO
i know d fuckin prizes u got
i know d fuckin
prizes u got 4 the top20 muddafuckas!!
u got ur moms 2 b fucked wid niggas!!
wid deir 14 inch dicks stucked b/w ur moms legs
yeah!!baby
u got it rite
big black dicks in addn to dildos!!!!!1
gotta go fuckers
@ Lnr Kindly read the
@ Lnr
Kindly read the question carefully.
@ BUSTED Please have
@ BUSTED
Please have patience. There are many people who have got accepted submissions.
what does optimally mean???
what does optimally mean???
For the 3rd sample input /
For the 3rd sample input / output, if we follow this way, then I can always FIRST win:
1st chance:
1 2
3 2
3 2
If SECOND touches any of 2nd or 3rd row, I do the same on 3rd or 2nd row respectively.
And if he changes 1st row to 0 2, I make it 0 0.
So, how is SECOND winning here ?
:)
:)
@avtar.. i think u have ti
@avtar.. i think u have ti wrong..
2 2 in the frst line is the dim of the matrix.
woops :) .. when would these
woops :) ..
when would these questions be put up on the practice session ?
I believe this problem is
I believe this problem is based on Grundy numbers. But I can't understand why my solution doesn't work. I treat each row a subgame. And then calculate XOR of Grundy number of each of the subgames.
To solve a subgame, let's say that when Grundy number is equal to 0, the player to go loses the game, when Grundy number is > 0, player wins the game. If there is a single positive number in a row, then this is basically a nim game, and Grundy number of a single pile will be the same as the number.
By induction we can solve the problem for more numbers on a single row, this can be easily found by drawing the graph of states with Grundy numbers.
Unfortunately I got WA, is there anyone with AC who could describe the solution?
In the 2nd case: 1 32 1
In the 2nd case:
No, the first players
No, the first players subtracts 2 from the first number and will win.
LTUnited // Although I didn't
LTUnited // Although I didn't understand your solution perfectly, especially for the part "By induction we can solve the problem for more numbers on a single row, this can be easily found by drawing the graph of states with Grundy numbers.", my algorithm is quite similar to yours. I guess you made some mistakes during the contest... ;_;
@LTUnited I think if you have
@LTUnited I think if you have a correct algorithm, it will not take much to get it AC as it's easy in implementation. So if you can explain how you work with your induction part, we can help more here.Rest of your explanation part is same as what i did.