Time Limit: 1 SecMemory Limit: 128 MB
Submit: 357Solved: 179
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
威佐夫博弈（Wythoff's game）是指的这样一个问题：有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。
我们用(a[k]，b[k]) (a[k] ≤ b[k] ,k=0，1，2，......n)来表示两堆物品的数量，并且称这个为局势。
首先我们来从最简单的情况开始分析：
如果现在的局势是(0，0)，很明显此时已经没有办法再取了，所以肯定是之前的人在上一局中取完了。
假设现在的局势是(1，2)，那么先手只有四种取法。
（1） 如果先手取走“1”中的1个，那么后手就从“2”中取出2个，此时取完，所以后手胜利。
（2）如果先手取走“2”中的2个，那么后手取走“1”中的1个，此时取完，后手胜利。
（3）如果先手取走“2”中的1个，那么后手就在两堆中各取走1个，此时取完，后手胜利。
（4）如果先手在“1”和“2”各取走了1个，那么后手取走“2”中的1个，此时取完，后手胜利。
由此可得，先手必输。
是不是觉得这个后手好厉害，无论先手怎么取，后手都会胜利。
在学习威佐夫博弈之前，我也是这样认为的。不过，当你继续看完这篇博客，你也会轻松获得胜利。
为了让大家更好地理解威佐夫博弈，我们继续来进行具体分析。
假设现在的局势是（3，5），首先根据上面分析的经验，我们知道先手肯定不能把任意一堆物品取完，这是因为每次可以从任意一堆取走任意个物品，那么后手就可以直接把另一堆取完，所以后手获胜。
所以我们这里就不分析那些情况，来分析其他的情况。
先看在一堆中取的情况：
（1） 假设先手在“3”中取1个，后手就可以在“5”中取走4个，这样就变成了（1，2）的局势，根据上面的分析，我们知道是先手输，后手获胜。
（2） 假设先手在“3”中取2个，后手就可以在 “5” 中取走3个，这样也变成了（1,2）的局势了，还是先手输，后手获胜。
（3）假设先手在“5”中取1个，后手就在 “3”和“5” 中各取走2个，这样又成了（1，2）的局势了，先手输，后手赢。
（4）假设先手在“5”中取2个，后手就在 “3”和“5” 中各取走3个，这样变成了（0，0）的局势，先手输，后手赢。
（5）假设先手在“5”中取3个，后手就在 “3”和“5” 中各取走1个，也变成了（1，2）的局势，先手输，后手胜利。
（6）假设先手在“5”中取4个，后手在“3”中取走1个，还是（1，2）的局势，先手输，后手赢。
我们发现上面列举的这几种局势，无论先手怎么取都是后手赢。
我们可以来找找那些先手必输局势的规律
第一个（0，0）
第二个（1，2）
第三个（3，5）
第四个（4 ，7）
第五个（6，10）
第六个 （8，13）
第七个 （ 9 ， 15）
第八个 （ 11 ，18）
第n个（a[k]，b[k]）
我们把这些局势称为“奇异局势”
我们会发现他们的差值是递增的，分别是0,1,2,3,4,5,6,7......n
有兴趣的读者可以自己模拟一下过程进行验证
我们用数学方法分析发现这些局势的第一个值是未在前面出现过的最小的自然数。
继续分析我们会发现，每种奇异局势的第一个值总是等于当前局势的差值乘上1.618
我们都知道0.618是黄金分割率。而威佐夫博弈正好是1.618，这就是博弈的奇妙之处！
即 a[k] = (int) （(b[k] - a[k])*1.618） 注：这里的int是强制类型转换，注意这不是简单的四舍五入，假如后面的值是3.9，转换以后得到的不是4而是3，也就是说强制int类型转换得到的是不大于这个数值的最大整数。
在编程题中，有些题目要求精度较高，我们可以用下述式子来表示这个值
1.618 = (sqrt(5.0) + 1) / 2
---------------------
作者：violetSweet
来源：CSDN
原文：https://blog.csdn.net/qq_41311604/article/details/79980882
版权声明：本文为博主原创文章，转载请附上博文链接！
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
int main(){
int n,m,a,b,t;
double c,r;
while(scanf("%d%d",&n,&m)==2)
{
a=min(n,m);
b=max(n,m);
r=(sqrt(5.0)+1)/2;
c=(double)(b-a);
t=(int)(r*c);
if(t==a)printf("0\n");
else printf("1\n");
}
return 0;
}
网友评论