The first instalment of a silly plan—another plan whose second instalment may never arrive.
The difference from the classic Nim game is that a pile which has been moved cannot be moved again.
At first I thought checking the parity of n would be enough.
Then I realised I had misread the statement: the same number cannot be taken from a single pile twice.
Build a table to find the pattern of the Sprague–Grundy function. Use brute force plus dynamic programming while computing it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| int vis[1005];
int sg[22][1<<21];
int mex() {
for(int i = 0; ; i++) if(!vis[i]) return i;
}
void pre() {
memset(sg, 0, sizeof(sg));
REPP(i,1,20) {
sg[i][0] = 0;
for(int j = 1; j < (1<<20) ; j++) {
memset(vis, 0, sizeof(vis));
for(int k = 0; k < i; k++) if ((j >> k) &1)
vis[sg[i - k - 1][j ^ (1 << k)]] = 1;
sg[i][j] = mex();
}
}
REPP(i,0,20) {
printf("%d %d\n", i, sg[i][(1 << i) - 1]);
}
}
int main()
{
int n;
SA(n);
int cnt = 1;
int ans = 0;
REPP(i,1,n) {
int x;
SA(x);
for(cnt=1;cnt*(cnt+1)/2<=x;cnt++);
ans ^= (cnt-1);
}
if(ans) {
puts("YES");
} else {
puts("NO");
}
return 0;
}
|
