NYOJ 取石子儿(八) 威佐夫博弈
取石子（八）
- 描述
-
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你胜，你第1次怎样取子?
- 输入
- 输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000。a=b=0退出。
- 输出
- 输出也有若干行，如果最后你是败者，则为0，反之，输出1，并输出使你胜的你第1次取石子后剩下的两堆石子的数量x,y,x<=y。如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜，先输出取走相同数量的石子的情况，假如取一堆的有多种情况，先输出从石子多的一堆中取的情况，且要求输出结果保证第二个值不小于第一个值。
- 样例输入
-
1 2 5 72 20 0
- 样例输出
-
013 53 54 710 01 2
这种博弈比前面一种要稍微复杂一点。我们来看下下面这个游戏。
有两堆火柴棍,每次可以从某一堆取至少1根火柴棍(无上限)，或者从两堆取相同的火柴棍数。最后取完的是胜利者。好了,如果你不知道这个博弈定理,对于小数目的火柴棍数,可能还能推出来,但是如果火柴棍数一多,就不行了。看了下面的这个介绍,你也会有一种被骗的感觉。
首先我们知道两堆火柴是没有差别的,也就是说第一堆有a根,第二堆有b根和第一堆有b根,第二堆有a根是一样的结果。
我们用一个二维的状态（a,b)来记录当前剩下的火柴数，表示第一堆剩下a根火柴,第二堆剩下b根火柴。同样我们假设两个人的编号是A和B，且A先取。
那么如果某个人遇到了这样的状态(0,0)那么也就是说这个人输了。这样的状态我们叫做奇异状态,也可以叫做失败态。
那么接下来的几个失败态为(1,2),(3,5),(4,7),(6,10),(8,13)……
我们用a[i]表示失败态中的第一个,b[i]表示失败态中的第二个.(i从0开始).
那么我们可以看到b[i] = a[i]+i;（i >= 0）,a[i]是前面的失败态中没有出现过的最小的整数
下面我们可以得到三个基本的结论。
1.每个数仅包含在一个失败态中
首先我们知道a[k]是不可能和前面的失败态中的a[i],b[i]重复的(这点由a[i]的得到可以知道)
b[k] = a[k]+k > a[k-1]+k>a[k-1]+k-1+1>a[k-1]+(k-1) = b[k-1]>a[k-1]这样我们知道每个数仅在一个失败态中。
2.每个失败态可以转到非失败态。
加入当前的失败态为(a,b)，那么如果我们只在一堆中取的话,肯定会变成非失败态(这点由第一点可以保证),如果从两堆同时取的话,由于每个失败态的差是不一样的,所以也不可能得到一个失败态。也就是说一个失败态不管你怎么取,都会得到一个非失败态。
3.每个非失败态都可以转到一个失败态
对于这个结论,首先我们要知到每个状态(a,b)要么a = a[i],要么b = b[i].(每个数都出现在一个失败态中),下面我们分两种情况来讨论
I.a = a[i].如果b = a的话那么一次取完就变成了(0,0).如果b > b[i]的话,那么我们从第二堆中取走b-b[i]就变成了一个失败态。如果b < b[i].那么我们从两堆中同时取走a-a[b-a[i]]这样得到失败态(a[b-a[i]],a[b-a[i]]+b-a[i])(a[i] = a)
II.b = b[i].如果a > a[i]那么我们从第一堆中取走a-a[i]根火柴.
如果a < a[i].这里又分两种情况。第一是a = a[k](k < i)
那么我们从第二堆取走b - b[k]就行了。
第二是a = b[k]这样的话由于两堆火柴是没有区别的,所以我们把b变成a[k]就行了,也即是从第二堆火柴中取走b - a[k]就变成了失败态
至于怎么判断一个状态是否是失败态.我们可以用下面的方法来判断(本人暂时还不会证明)
a[i] = [i*(1+√5)/2](这里的中括号表示向下取整) b[i] = a[i]+i;
那么这就是一个失败态
具体的请查看:
http://blog.csdn.net/niushuai666/article/details/6638943
#include<iostream>
#include <cstdio>
#include <algorithm>
#include<math.h>
using namespace std;
int main()
{
int a,b,temp,temp2,k,i;
while(scanf("%d%d",&a,&b),a+b)
{
if(a>b)
swap(a,b);
k=b-a;
temp=k*(1.0+sqrt(5.0))/2.0;
if(a==temp) //奇异局势
printf("0\n");
else
{
printf("1\n");
if(abs(temp-a)==abs(temp+k-b)&&temp<a) //两堆
printf("%d %d\n",temp,temp+k);
if(a==0) //0 0情况，第一种奇异局势
printf("0 0\n");
for(i=1;i<=b;i++) //一堆
{
temp=i*(1.0+sqrt(5.0))/2.0;
temp2=temp+i;
if(temp>b)
break;
if(temp==a&&temp2<b)
printf("%d %d\n",a,temp2);
else if(temp2==a&&temp<b)
printf("%d %d\n",temp,a);
else if(temp2==b&&temp<a)
printf("%d %d\n",temp,b);
}
}
}
return 0;
}