题目链接;https://vjudge.net/contest/381841#problem/A
A题是个威佐夫博弈的裸题,先了解一下威佐夫博弈。
预备知识:
博弈论之威佐夫博弈
威佐夫博弈 是指的这样一个问题:有两堆各若干个物品,两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品,规定每次至少取一个,至多不限,最后取光者胜利。
关于威佐夫博弈的推导请看:https://blog.csdn.net/qq_41311604/article/details/79980882
只需要知道:
1.满足威佐夫博弈则会有一些先手必输的局势。
2.我们会发现他们的差值(b[k]-a[k])是递增的,分别是0,1,2,3,4,5,6,7......n
3.局势的第一个值是未在前面出现过的最小的自然数。
结论:每种奇异局势的第一个值(这里假设第一堆数目小于第二堆的数目)总是等于当前局势的差值乘上1.618(充分必要条件)
注:在编程题中,有些题目要求精度较高,我们可以用下述式子来表示这个值
1.618 = (sqrt(5.0) + 1) / 2
代码:
#include<iostream> #include<math.h> #include<cstdio> using namespace std; int main() { int a, b; while(scanf("%d%d",&a,&b)!=EOF) { int maxn = max(a, b); int minn = min(a, b); double r = (sqrt(5.0) + 1) / 2; double tmp = maxn-minn; if(minn == (int)(r*tmp)) { printf("0\n"); } else { printf("1\n"); } } }