HDU 1527 取石子游戏（威佐夫博奕）

深碍√TFBOYSˉ_ 2024-02-17 19:53 16阅读 0赞

## 取石子游戏 ##

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 6889 Accepted Submission(s): 3757**

Problem Description

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

Input

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

Output

输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。

Sample Input

2 1
    8 4
    4 7

Sample Output

0
    1
    0

分析：威佐夫博奕

威佐夫博弈：

有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取完者得胜。这种情况下是颇为复杂的。

可以用两个数（a\[k\],b\[k\]）（ps：（a\[k\]≤b\[k\]）k为一个自然数)表示两堆物品的数量。如果该数量为奇异局势，那么先手输;

前几个奇异局势如下：（0,0,）、（1,2）、（3,5）、（4,7）、（6,10）······起始值a\[0\]=b\[0\]=0;k=0;

可以看出a\[k\]是在之前未出现过的最小自然数，而b\[k\] = a\[k\]+k，k代表出现的第几个奇异局势；

结论：两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。

那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？

我们有如下公式：a表示第一堆的个数，b表示第二堆的个数，c表示二者之差，当然a必须小于b;

再找规律的话我们会发现，ak= c\* 1.618 （ak==a表示奇异局势）

而1.618 = （sqrt（5.0）+ 1） / 2 。

大家都知道0.618是黄金分割率。而威佐夫博弈正好是1.618，这就是博弈的奇妙之处！

AC代码：

#include<cstdio>
    #include<cmath>
    using namespace std;
    int main(){
    	int a,b;
    	while(scanf("%d%d",&a,&b)==2){
    		if(a>b){
    			int tmp=a;
    			a=b;
    			b=tmp;
    		}
    		int c=b-a;
    		int ak=(int)((sqrt(5.0)+1)/2 * c);
    		if(ak==a)printf("0\n");
    		else printf("1\n");
    	}
    	return 0;
    }