Written by    10:00 July 29, 2014 


Matches Game
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 9306 Accepted: 5372


Here is a simple game. In this game, there are several piles of matches and two players. The two player play in turn. In each turn, one can choose a pile and take away arbitrary number of matches from the pile (Of course the number of matches, which is taken away, cannot be zero and cannot be larger than the number of matches in the chosen pile). If after a player’s turn, there is no match left, the player is the winner. Suppose that the two players are all very clear. Your job is to tell whether the player who plays first can win the game or not.


The input consists of several lines, and in each line there is a test case. At the beginning of a line, there is an integer M (1 <= M <=20), which is the number of piles. Then comes M positive integers, which are not larger than 10000000. These M integers represent the number of matches in each pile.


For each test case, output “Yes” in a single line, if the player who play first will win, otherwise output “No”.

Sample Input

Sample Output


POJ Monthly,readchild



题目本身大概的意思就是说有M个火柴堆,A和B可以依次先后(按照ABABABABAB的顺序)从任一火柴堆中那出数目大于零且不大于所选择火柴堆的数量的火柴,谁最后一个拿完全部火柴谁就是赢家,然后题目要求判断所给的情况中先动手的即A是否可以取胜。 万万没想到,这个题目要用异或(XOR)来解。 最后取胜的状态XOR(0,0,0,0,0,0,0。。。) = 0,然后再加上两个最关键的结论:


  • 当XOR(M1, M2, …Mn) != 0 时,总是可以通过改变一个Mi的值,就可以让XOR(M1, M2, …Mn) = 0


  • 当XOR(M1, M2, …Mn) = 0 时,任意一个Mi的值的改变,就可以让XOR(M1, M2, …Mn) != 0 也就是说如果一开始XOR(M1, M2, …Mn) = 0,那么先手者肯定会使XOR(M1, M2, …Mn) != 0,后手者无论如何都可以使XOR(M1, M2, …Mn) = 0,如此循环至最终XOR(0,0,0,0,0,0,0。。。) = 0,后手者必赢,所以XOR(M1, M2, …Mn) = 0就是必输局面,相反,如果一开始XOR(M1, M2, …Mn) != 0,那么就是必胜局面。



Category : acmstudy

Tags :