I am trying to solve this problem :
http://www.spoj.com/problems/MATGAME/

I read all the available entries. I can't figure out where is mistake in my code.

Strategy used:

- Calculated grundy value for each possible cell entry

void solve() {

```
grundy[0] = 0;
for(int i = 1; i <= 51; ++i) {
memset(used, false, sizeof(used));
int mex = 0;
for(int j = 1; j <= i; ++j)
used[grundy[i - j]] = true;
while(used[mex])
++mex;
grundy[i] = mex;
for(int j = i + 1; j <= 51; ++j)
grundy[j] = grundy[i];
}
```

}

- Then for each row calculated it's grundy number and xor-ed them.

int main() {

```
solve();
int test, n, m, item; // n rows, m columns
scanf("%d", &test);
while(test--) {
scanf("%d%d", &n, &m);
int gr_overall = 0; // NIM sum
for(int i = 0; i < n; ++i) {
int mex = 1; // Tried mex = 0 also gives WA
memset(used, false, sizeof(used));
for(int j = 0; j < m; ++j) {
scanf("%d", &item);
used[grundy[item]] = true; // Marking grundy number for each cell
}
while(used[mex]) ++mex; // Calculating minimum value
gr_overall ^= mex; // Calcualting NIM sum
}
if(gr_overall) cout << "FIRST" << endl;
else cout << "SECOND" << endl;
}
return 0;
```

}

Please help. Thank you.

asked
**19 Mar '14, 18:46**

2★codemex

1●1●2

accept rate:
0%