学步园

nyoj 886 :点击打开链接

威佐夫博弈， 在判断的基础上加上输出第一步走法。

输出第一步走法实际就是将石子数减小到必败态，计算出来的k和k+s就是一组必败态，只要判断a到k，和b到k+s的距离是否相等来就能判断是否能从两堆中取相同数目的石子达到必败态。

接下来考虑从某一堆中取石子，

a[i] = [i * (1 + sqrt(5)) / 2],b[i] = a[i] +ｉ

通过枚举i，知道i以后可以算出a[i] 和b[i]。然后进行判断即可。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main (void)
{
	int a, b, temp;
	double p = (double)((1.0 + sqrt(5.0)) / 2.0);
	while(scanf("%d %d",&a, &b) != EOF)
	{
		if(a == 0 && b == 0)
			break;
		if(a > b)
		{
			temp = a;
			a = b;
			b = temp;
		}
		int s = b - a;
		int k, i;
		k = floor(s * p);
		if(k == a)
			printf("0\n");
		else
		{
			printf("1\n");
			//拿走相同数量的石子  注意两个条件都要写，不然WA 
			if(a - k == b - (k + s) && a >= k)
				printf("%d %d\n", k, k + s);
			
			for(i = 0;; i++)
			{
				temp = i * p;
				//printf("          %d, %d\n", temp, temp + i);
				if(temp >= b)
					break;
				//从b中拿石子，且拿完b比a大 
				if(b > temp + i && a == temp)
					printf("%d %d\n", temp, temp + i);
				//从b中拿石子，但拿完b比a小 
				else if(a == temp + i)
					printf("%d %d\n", temp, temp + i);
				//从a中拿，拿完肯定a还是小于b 
				else if(b == temp + i && a > temp)
					printf("%d %d\n", temp, temp + i);
			}
		}	
	}
	return 0;
}