HDOJ 2177 取(2堆)石子游戏 博弈 威佐夫博奕变形（Wythoff Game）

//HDOJ 2177 取(2堆)石子游戏 威佐夫博奕变形（Wythoff Game）/*题意：在Wythoff Game游戏的基础上加一个限定：只有2堆石头  如果是必胜态，则需要输出所有可以走的第一步，如果可以同时取走相同的石子的情况要先输出思路：预处理记录奇异局势的左边位和右边位出现的是第几个奇异局势  正常的Wythoff Game规则判断胜负态  然后枚举所有可能出现的第一步走法，注意先输出可以同时取走一样石子的情况*/#include<stdio.h>#include<string.h>#include<stdlib.h>#include<cmath>#define N 1000005int a,b;double t;int fl[N];//标记第i个奇异局势的左边那位为iint fr[N];//标记第i个奇异局势的右边那位为ivoid init(){int i;memset(fl,-1,sizeof(fl));memset(fr,-1,sizeof(fr));for(i = 0; i*t+i <= N-5; ++i){int fa = int(i*t);fl[fa] = i;fr[fa+i] = i;}}int main(){t=(1+sqrt(5*1.0))/2;init();while(scanf("%d %d",&a,&b)!=EOF){if(a == 0 && b == 0)break;if(floor((b-a)*t) == a){puts("0");}else{int ta,tb,k;puts("1");k = b-a;ta = k*t;tb = ta+k;if(a>ta && b>tb){//同时取走相同数量的石子也能胜printf("%d %d\n",ta,tb);}if(fl[a]!=-1 && b > a+fl[a]){//固定aprintf("%d %d\n",a,a+fl[a]);}if(fr[a]!=-1 && a!=b){//固定a && 判重printf("%d %d\n",a-fr[a],a);}if(fr[b]!=-1 && a > b-fr[b]){//固定bprintf("%d %d\n",b-fr[b],b);}}}return 0;}