http://www.spoj.com/problems/MATGAME/
I have been trying to solve this problem on spoj. I calculated grundy number for every row and than took their xor. I am getting wrong answer but am unable to find an error.
int ex = 0;
for(int i = 0; i < n; i ++)
{
int g = ar[i][m-1];
for(int j = m-2; j >= 0; j --)
{
if(g == 0)
g = ar[i][j];
else
g = ar[i][j] - 1;
}
ex = ex ^ g;
}
if(ex) printf("FIRST\n");
else printf("SECOND\n");
This is the code. Any help is greatly appreciated.
A good discussion on this problem exists here.
http://www.codechef.com/problems/SNCK01 Check this link.
This part of your code logic is wrong (the else part):
if(g == 0) g = ar[i][j]; else g = ar[i][j] — 1;
The else part in your code is valid only when ar[i][j]<=g
=)
thanks guys.. I got my mistake :)
As said, computation of g was wrong.