[Login|Register]
Problems

Status

Rank

Problem 1213
取石子游戏
Time Limit: 1000ms
Memory Limit: 65536kb
Description
在组合博弈论中,Nim游戏是一个非常经典的问题,Nim游戏可描述如下:
有n堆石子,每堆石子数分别为a1, a2, …, an (ai≥0)。现有两人轮流从这n堆中取石子,每次必须从某一堆中取任意多的石子,至少要取一个,必须从同一堆中取石子,并且不能超过这一堆石子的总数。如果某一方没有石子可取,那么他就输了。
例如有3堆石子,分别有3, 2, 2个,A和B两人轮流取。
A先从第2堆取1个,然后B从第1堆取3个,此时石子数分别为0, 1, 2
A又从第3堆取1个,然后B从第1堆取1个,此时石子数分别为0, 0, 1
A最后从第3堆取1个,此时所有石子都被取走,B无石子可取,所以B输了。
C. L. Bouton给出了Nim游戏的解法:
考虑把每堆的石子数a1, a2, …, an表示成二进制,那么当前游戏局面的Nim数为a1, a2, …, an的按位异或。比如在上面的例子中,3=11(2), 2=10(2), 2=10(2), 将这3个数按位异或得11(2)=3。所以3是当前游戏局面的Nim数。
这里不加证明地给出结论:假设游戏双方都非常聪明,当Nim数为0时,当前游戏者必败;当Nim数不为0时,当前游戏者必胜。
再考虑上面的例子,A取走第2堆的1个石子后,石子数变为3, 1, 2,其Nim数为0,从而使得B必败;此后A每次取石子后总能使得留给B的局面的Nim数为0,所以A最终取得了胜利。
既然你已经知道了如何判断当前Nim游戏局面是否必胜,那么请完成一个稍稍复杂些的任务:
给定Nim游戏的当前局面,如果必胜,请找出当前游戏者需要取走多少石子才能让对方必败,如果有多种取石子的方式,请给出要取石子数最少的。再如上面的例子,初始时,A从第1堆取3个石子,或从第2或3堆取1个石子都可以保证B必败,但因为后者所取的石子数最少,所以这种情况下答案为1。
Input
输入包含多组数据。
每组数据第一行为n (1≤n≤106),表示石子的堆数。
第二行包含n个非负整数,表示每堆石子的数量,每堆石子不超过109个。注意,可以有空的石子堆。
输入以n=0结束,不要处理这个数据。
Output
对每组数据输出一行,为需要取走的最少的石子数,如果当前局面必败则输出-1
Sample Input
1
10
2
17 17
3
3 2 2
4
1 2 3 4
0
Sample Output
10
-1
1
4
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.2ms with 1 query(s).