【USTC 1213】取石子游戏（尼姆博弈）

Description

在组合博弈论中，Nim游戏是一个非常经典的问题，Nim游戏可描述如下：
有n堆石子，每堆石子数分别为a₁, a₂, …, a_n(a_i≥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游戏的解法：
考虑把每堆的石子数a₁, a₂, …, a_n表示成二进制，那么当前游戏局面的Nim数为a₁, a₂, …, a_n的按位异或。比如在上面的例子中，3=11₍₂₎, 2=10₍₂₎, 2=10₍₂₎, 将这3个数按位异或得11₍₂₎=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≤10⁶)，表示石子的堆数。
第二行包含n个非负整数，表示每堆石子的数量，每堆石子不超过10⁹个。注意，可以有空的石子堆。
输入以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<br /><strong><br /></strong>由于这道题符合尼姆博弈的规则，所以写起来还算是简单的，详细请见我的另一篇有关博弈论的文章吧，在这就不多加阐述了。<br />要注意异或运算的运算顺序是在加减乘除之后的！！！！！

#include "stdio.h"
const int N=1000001;
int a[N];
int main()
{
    int i,t,n,min,p;
    while(scanf("%d",&n)!=EOF,n)
    {
        min=100000001;
        t=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            t=t^a[i];
        }
        if(t==0)
        printf("-1\n");
        else
        {
            for(i=0;i<n;i++)
            {
                p=a[i]-(t^a[i]);
                if(min>p&&p>0)
                min=p;
            } 
            printf("%d\n",min);
        }
    }
    return 0;
}