【NOIP模拟赛】日历游戏

2014年11月2日1,8590

【问题描述】

moreDmoreD的宠物CD正在玩一个日历游戏,开始时,他们从190011日到20121222日(你懂的……)选一个日期开始,依次按照如下规则之一向后跳日期:

  1. 1. 跳到日历上的下一天。
  2. 2. 跳到日历上的下个月的同一天(如果不存在,则不能这么做)。

要是谁正好到达20121222日那么他就赢了,如果到达这天之后的日期那他就输了——原因你也懂的。

每次都是moreD先走的。

现在,给你一个日期,请问moreD一定能赢吗?

【输入】

输入共T行,每行三个整数,Y、M、D,分别表示年、月、日。日期在190011日到20121222日之间(包含两端)。

T并不在输入数据当中。

【输出】

要是moreD一定能赢,输出一行YES,否则输出NO

【输入输出样例一】

calendar.in

calendar.out

2012 12 20

NO

【输入输出样例二】

calendar.in

calendar.out

2012 12 21

YES

【数据描述】

对于50%的数据,是194911日后的日期。 T <= 5

对于100%的数据,是190011日后的日期。T <= 10

题解

对于日期直接的关系是一棵二叉树,然后用记忆化搜索解决

具体可以递推或者用sg函数

为了防止爆栈可以先分成几棵子树处理