| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem C
取石子游戏
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 |