Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
Author: goal00001111
Date: 18-12-08 19:47
Description:
描述 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"，它们表示对应的十行输入数据中有必胜策略的一方。
请注意大小写。
样例输入 Sample Input
1 1
1 2
1 3
1 4
1 5
2 1
2 2
2 3
2 4
2 5
样例输出 Sample Output
Matrix67
Matrix67
Matrix67
Matrix67
Matrix67
Matrix67
Shadow
Shadow
Matrix67
Matrix67
题目分析：
解决这类题目的方法就是枚举讨论。
假设现在轮到你吃，摆在你面前的是糖果堆A和B。当你吃完堆A后，B将决定你的命运：
如果B = 1：你就是那个最幸运的人；
如果B = 2或B = 3：你都只能自认倒霉，因为无论你怎么分，都将有一份是1；
如果B = 4：你该感到庆幸，因为4 = 2 + 2，你把烫手的山芋扔给了对方；
同样的5 = 2 + 3，6 = 3 + 3，你总能立于不败之地；
如果B = 7：你将在劫难逃！因为7 = 1 + 6 = 2 + 5 = 3 + 4。
分成7 = 1 + 6马上告负；
分成7 = 2 + 5可以勉强坚持一轮，但对方吃掉2，把剩下的5分成2和3送给你，你就输定了；
分成7 = 3 + 4，对方吃掉3，把剩下的4分成2和2，你也难逃厄运；
同样的8 = 1 + 7 = 2 + 6 = 3 + 5 = 4 + 4，你可以预见自己失败的命运了吧；
如果B = 9：胜利女神又偏向你了！因为9 = 2 + 7，无论对方吃掉哪一个都不好分；
同样的10 = 3 + 7 = 2 + 8，怎么分你自己看着办吧，别让自己输了就行。
现在发现了吧，如果B = [2, 3, 7, 8]，你稳赢；B = [2, 3, 7, 8]，你必输。
对于大于10的情况，我们可以设a = [2, 3, 7, 8]，b = [1, 4, 5, 6, 9, 10]。
观察集合a和b，我们可以发现每个b元素都能写成两个a元素之和对10求余的形式：
1 = (3 + 8) % 10; 4 = (2 + 2) % 10; 5 = (2 + 3) % 10; 6 = (3 + 3) % 10; 9 = (2 + 7) % 10; 10 = (3 + 7) % 10;
如果摆在你面前的两个堆的数量都可写为10 * i + a的形式，不管你吃掉哪一堆，留下的第二个数都是10 * i + a，这时你无论怎么分，分出来的两个数中肯定有一个可写为10 * i + b的形式，而10 * i + b = 10 * j + a + 10 * k + a，即两个数的个位数字都是集合a中的数，
这样经过一轮后，回到你手里的还是两个10 * i + a，你没办法赢。
另外一种情况：摆在你面前的两个堆的数量都可写为10 * i + b的形式，这样不管你吃掉那一堆，都可以把剩下的一堆分成10 * i + b = 10 * j + a + 10 * k + a，这样送给对方的是两个10 * i + a，他输定了。
最后一种情况：摆在你面前的一个堆的数量写为10 * i + a的形式，另一个堆的数量写为10 * j + b的形式，你把堆10 * i + a 吃掉，剩下的堆10 * j + b分成两个10 * i + a，稳操胜券。
因此得出结论：如果两个堆数量的个位数字都属于集合a，先拿者Matrix67必败，否则Matrix67胜。
说明：
算法思想：数学分析，总结规律。
数据结构：字符串（c++），集合（pascal）。
时间复杂度：O(1);
空间复杂度：O(1);
程序语言：分别用c++和pascal实现。
附注：虽然题目说输入的是两个正整数，但是“对于100%的数据，这些正整数均不超过10 000位。”，
所以千万不要用整型数据类型，而要用字符串，否则肯定越界。
C++语言使用一个很长的条件语句来判断正整数的个位数字是否属于集合a，而pascal语言则利用集合轻松搞定。
一个相似的题目：设有n根火柴，甲乙两人依次从中取走1根或2根，不能多取，也不能不取。
规定谁取走最后一根火柴谁就是胜利者，请你分析什么情况下先取者有必胜策略。
聪明的你想到答案了吗？
c++代码：
#include<iostream>
using namespace std;
int main(int argc, char* argv[])
{
string a, b;
char m, n;
for (int i=0; i<10; i++)
{
cin >> a;
cin >> b;
m = a[a.size()-1];
n = b[b.size()-1];
if ((m == '2' || m == '3' || m == '7' || m == '8')
&& (n == '2' || n == '3' || n == '7' || n == '8'))
{
cout << "Shadow" << endl;
}
else
{
cout << "Matrix67" << endl;
}
}
system("pause");
return 0;
}
PASCAL代码：
PROGRAM P1196 (INPUT, OUTPUT);
VAR
ch, m, n : char;
i : integer;
BEGIN
for i:=1 to 10 do
begin
read(ch);
while not (ch in ['0'..'9']) do {消除非数字字符}
read(ch);
while ch in ['0'..'9'] do {取个位数字}
begin
m := ch;
read(ch);
end; {while}
read(ch);
while not (ch in ['0'..'9']) do {消除非数字字符}
read(ch);
while ch in ['0'..'9'] do {取个位数字}
begin
n := ch;
read(ch);
end; {while}
if (m in ['2','3','7','8']) and (n in['2','3','7','8']) then
writeln('Shadow')
else
writeln('Matrix67');
end; {for}
END.