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

伊甸园日历游戏——轮流取数问题的输赢策略轮流取数问题的输赢策略一个小学的问题如题：可以从1,2,3中取数，两人轮流取数，取的数会累加起来，从0开始，谁先到24谁赢得比赛可以倒退表示某人拿到这个数的时候的输赢）假设对方也是高手，那么只有必输和必赢两种状态24-23 必赢（+1）22 必赢（+2）21 必赢（+3）20 必输，无论取1 2 3，都让对手进入必赢的状态19 必赢，取到20，则对手进入必输状态18 必赢，取到2017 必赢，取到2016 必输以此类推）扩展到更多，可以得到结论S表示可以取的数的集合,如上面的1,2,3T表示可以取到的数的集合,如上题的[0,24]中的整数当计算T[i]的输赢的时候,只要T[i+s[j]]中有一个是必输的，那么取到这个数，则可以必赢;若全都是必赢的,那么取到这个数就是必输的.则倒推可以得到所有的解下面是一个更加推广的题例题:伊甸园日历游戏描述 DescriptionAdam和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 Input32001 11 32001 11 22001 10 3样例输出 Sample Output YESNONO分析就如上面的推论一样,从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.  。