【USTC 1213】取石子游戏(尼姆博弈)

2018-02-12 08:24:56来源:cnblogs.com作者:Kannyi人点击

分享

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
110217 1733 2 241 2 3 40
Sample Output
10-114

由于这道题符合尼姆博弈的规则,所以写起来还算是简单的,详细请见我的另一篇有关博弈论的文章吧,在这就不多加阐述了。
要注意异或运算的运算顺序是在加减乘除之后的!!!!!
#include "stdio.h"const int N=1000001;int a[N];int main(){    int i,t,n,min,m;    while(scanf("%d",&n)!=EOF,n)    {        min=100000001;        m=0;        for(i=0;i<n;i++)        {            scanf("%d",&a[i]);            m=m^a[i];        }        if(m==0)        printf("-1/n");        else        {            for(i=0;i<n;i++)            {                t=a[i]-(m^a[i]);                if(min>t&&t>0)                min=t;            }             printf("%d/n",min);        }    }    return 0;}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台