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;
}