伊甸园日历游戏_轮流取数问题的输赢策略1.doc

伊甸园日历游戏——轮流取数问题的输赢策略
轮流取数问题的输赢策略
一个小学的问题。
如题：
可以从1,2,3中取数，两人轮流取数，取的数会累加起来，从0开始，谁先到24谁赢得比赛。

可以倒退。
（表示某人拿到这个数的时候的输赢）
假设对方也是高手，那么只有必输和必赢两种状态。
24-
23 必赢（+1）
22 必赢（+2）
21 必赢（+3）
20 必输，无论取1 2 3，都让对手进入必赢的状态
19 必赢，取到20，则对手进入必输状态
18 必赢，取到20
17 必赢，取到20
16 必输。。。
（以此类推）
扩展到更多，可以得到结论。
S表示可以取的数的集合,如上面的1,2,3
T表示可以取到的数的集合,如上题的[0,24]中的整数
当计算T[i]的输赢的时候,只要T[i+s[j]]中有一个是必输的，那么取到这个数，则可以必赢;若全都是必赢的,那么取到这个数就是必输的.

则倒推可以得到所有的解。

下面是一个更加推广的题。
例题:伊甸园日历游戏
描述 Description
Adam和Eve玩一个游戏，他们先从1900.1.1到2001.11.4这个日期之间随意抽取一个日期出来。然后他们轮流对这个日期进行操作： 
  1 ： 把日期的天数加1，例如1900.1.1变到1900.1.2 
  2 ： 把月份加1，例如：1900.1.1变到1900.2.1 
  其中如果天数超过应有天数则日期变更到下个月的第1天。月份超过12则变到下一年的1月。而且进行操作二的时候，如果有这样的日期：1900.1.31，则变成了1900.2.31，这样的操作是非法的，我们不允许这样做。而且所有的操作均要考虑历法和闰年的规定。 
  谁先将日期变到2001.11.4谁就赢了。 
  每次游戏都是Adam先操作，问他有没有必胜策略？
输入格式 Input Format
一个测试点。多组数据。 
 第一行为数据组数。 
 接下来一行X Y Z表示X年Y月Z日 
输出格式 Output Format
输出“YES”or“NO”表示亚当是否有必胜策略。 
样例输入 Sample Input
3
2001 11 3
2001 11 2
2001 10 3
样例输出 Sample Output
YES
NO
NO
分析
就如上面的推论一样,从2001.11.4从上往下一直推到1900.1.1,

具体要写对日期加减的函数.
1. const  
2. yt=1900;  
3. r:array[0..1,1..12] of longint=((31,28,31,30,31,30,31,31,30,31,30,31),(31,29,31,30,31,30,31,31,30,31,30,31));  
4. var  
5. f:array[0..150,1..12,1..31] of boolean;  
6. y,m,d,n,i:longint;  
7. procedure mk;  
8. var ry:longint;  
9. begin  
10. if (((y+yt) mod 100=0) and ((y+yt) mod 400=0)) or  
11. (((y+yt) mod 100<>0) and ((y+yt) mod 4=0)) then ry:=1 else ry:=0;  
12. if (m=1) and (d=0) then begin  
13. y:=y-1;m:=12;d:=31;  
14. end;  
15. if d>r[ry][m] then begin d:=d-r[ry][m];m:=m+1; end;  
16. if d<=0 then begin d:=d+r[ry][m-1];m:=m-1; end;  
17. if m>12 then begin m:=m-12;y:=y+1; end;  
18. if m<=0 then begin m:=m+12;y:=y-1; end;  
19. end;  
20. function yz(y,m,d:longint):boolean;  
21. var ry:longint;  
22. begin  
23. if (((y+yt) mod 100=0) and ((y+yt) mod 400=0)) or  
24. (((y+yt) mod 100<>0) and ((y+yt) mod 4=0)) then ry:=1 else ry:=0;  
25. if (m>12) or (m<1) or (d>r[ry,m]) or (d<1) then exit(false);  
26. if ((y>1900-yt)and(y<2001-yt))or((y=1900-yt)and((m>1)or((m=1)and(d>=1))))or((y=2001-yt)and((m<11)or((m=11)and(d<=4)))) then exit(true);  
27. exit(false);  
28. end;  
29. procedure init;  
30. var p:boolean;  
31. y1,m1,d1:longint;  
32. begin  
33. y:=2001-yt;m:=11;d:=4;f[y,m,d]:=false;  
34. while true do begin  
35. dec(d);mk;  
36. p:=false;  
37. y1:=y;m1:=m;d1:=d;inc(d);mk;  
38. if (yz(y,m,d)) and (not f[y,m,d]) then p:=true;  
39. y:=y1;m:=m1;d:=d1;inc(m);  
40. if (yz(y,m,d)) and (not f[y,m,d]) then p:=true;  
41. y:=y1;m:=m1;d:=d1;f[y,m,d]:=p;  
42. if (y<=0) and (m<=1) and (d<=1) then break;  
43. end;  
44. end;  
45. begin  
46. init;  
47. readln(n);  
48. for i:=1 to n do begin  
49. readln(y,m,d);  
50. if f[y-yt,m,d] then writeln('YES') else writeln('NO');  
51. end;  
52. end.