Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Nim
Description Nim is a 2-player game featuring several piles of stones. Players alternate turns, and on his/her turn, a player’s move consists of removing A position in Nim is called “losing” if the first player to move from that position would lose if both sides played perfectly. A “winning move,” then, is a move that leaves the game in a losing position. There is a famous theorem that classifies all losing positions. Suppose a Nim position contains k_{1} + k_{2} + … + k possible moves. We write each _{n}k in binary (base 2). Then, the Nim position is losing if and only if, among all the _{i}k’s, there are an even number of 1’s in each digit position. In other words, the Nim position is losing if and only if the _{i}xor of the k’s is 0._{i}Consider the position with three piles given by 111 There are an odd number of 1’s among the rightmost digits, so this position is not losing. However, suppose Input The input test file will contain multiple test cases, each of which begins with a line indicating the number of piles, 1 ≤ n = 0 and should not be processed.Output For each test case, write a single line with an integer indicating the number of winning moves from the given Nim position. Sample Input 3 7 11 13 2 1000000000 1000000000 0 Sample Output 3 0 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator