今天晴天 » 日志 » P1196吃糖果游戏 题解
P1196吃糖果游戏 题解
Ronice 发表于 2006-10-21 11:19:48
描述 Description
Matrix67和Shadow正在做一个小游戏。
桌子上放着两堆糖果，Matrix67和Shadow轮流对这些糖果进行操作。在每一次操作中，操作者需要吃掉其中一堆糖果，并且把另一堆糖果分成两堆（可以不相等）留给对方操作。游戏如此进行下去，糖果数会越来越少，最后必将出现这样一种情况：某人吃掉一堆糖果后发现另一堆里只剩一块糖果不能再分了。游戏规定此时该操作者吃掉最后这一块糖果从而取胜。
这个游戏是不公平的。对于任意一种初始状态，总有一方有必胜策略。所谓有必胜策略是指，无论对方如何操作，自己总有办法取胜。
Matrix67和Shadow将进行10次游戏，每一次游戏中总是Matrix67先进行操作。Matrix67想知道每一次游戏中谁有必胜策略。
输入格式 Input Format
输入数据一共10行，每行有两个用空格隔开的正整数，表示一次游戏开始时桌子上两堆糖果分别有多少个。
对于50%的数据，这些正整数均不超过100；
对于70%的数据，这些正整数均不超过10 000；
对于100%的数据，这些正整数均不超过10 000位。
输出格式 Output Format
输出十行字符串。这些字符串只能是“Matrix67”或“Shadow”，它们表示对应的十行输入数据中有必胜策略的一方。
请注意大小写。
显然当A吃完其中一堆后，如果剩下那堆为2或3则A必败。
当A吃完其中一堆后，剩下那堆为7,8，则A也必败：
7=2+5=3+4；
8=3+5=4+4; 4=2+2；
对于两堆 10i+a,10j+a,(a为2,3,7,8)
1、A吃完一堆，会努力的分出10i+a,此时另一堆剩下10j+(-)5获10m;
注意到2+8=10 3+7=10; 8-3=5; 7-2=5;
2、B吃完其中第一堆，分离第二堆时，分离出a后，还是剩于10k+a;跳至1、
3、当然，如果A吃完其中一堆后，分离出的两堆也可以是10i+c(c为1,4,5,6,9) 和10j-c+a;B吃完第二堆后，还是可以将第一堆分离成a,10i+a; 转至1
2+2=4； 2+3=5； 3+3=6； 2+7=9； 3+8=11;
推得A必败
当两堆中任意一堆不为10i+a时A都可以通过3取得必胜。
究其原因当尾数都是(2,3,7,8)时A必输，是因为
2+8=10 3+7=10
所以无论A如果处理10i+a B都可以将他转化为必败状态
