HDOJ 2177 取(二堆)石子游戏 博弈 威佐夫博奕变形(Wythoff Game)
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 1000005 int a,b; double t; int fl[N];//标记第i个奇异局势的左边那位为i int fr[N];//标记第i个奇异局势的右边那位为i void 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]){//固定a printf("%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]){//固定b printf("%d %d\n",b-fr[b],b); } } } return 0; }