HDU 2177 取(2堆)石子游戏

Problem Description 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你胜，你第1次怎样取子?  

 

Input 输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000，且a<=b。a=b=0退出。  

 

Output 输出也有若干行，如果最后你是败者，则为0，反之，输出1，并输出使你胜的你第1次取石子后剩下的两堆石子的数量x,y,x<=y。如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜，先输出取走相同数量的石子的情况.  

 

Sample Input 1 2 5 8 4 7 2 2 0 0  

 

Sample Output 0 1 4 7 3 5 0 1 0 0 1 2 典型的威佐夫博弈题目，有关威佐夫博弈参见： http://blog.csdn.net/zhangxiang0125/archive/2011/02/08/6174639.aspx 至此，有关博弈初级入门的所有类型都分析完了。关键还是在于练习啊！ #include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef long long int64; int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); int anum,bnum; double xx=sqrt(5.0); while(scanf("%d%d",&anum,&bnum)!=EOF) { if(anum==0 && bnum==0) break; bool flag=false, tag=false; if(anum==(int)(abs(bnum-anum)*(1+xx)/2)) printf("0/n"); else { int a1,b1,a2,b2; //if(!anum) printf("0 0/n"); for(int i=1;i<=bnum;i++) { if((anum-i)>=0 && !flag)//在两堆中都拿 { if((anum-i)==(int)(abs(bnum-anum)*(1+xx)/2)) { a1=anum-i; b1=bnum-i; flag=true; } } if((anum-i>=0) && !tag)//在其中一堆中拿（假设a堆多，在a堆中拿） { if((anum-i)==(int)(abs(bnum-anum+i)*(1+xx)/2)) { a2=anum-i; b2=bnum; tag=true; } } if(!tag)//在b堆中拿 { if(((bnum-i)<anum?(bnum-i):anum)==(int)(abs((bnum-i)-anum)*(1+xx)/2)) { a2=anum; b2=bnum-i; tag=true; } } if(flag && tag) break; } if(flag || tag) { printf("1/n"); if(flag) printf("%d %d/n",a1,b1); if(tag) { if(a2>b2) printf("%d %d/n",b2,a2); else printf("%d %d/n",a2,b2); } } } } return 0; }