202503021819 博弈论 石子 威佐夫博弈

石子 威佐夫博弈

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

title: input
2 1
8 4
4 7

title: output
0
1
0

title: 思路
从小到大枚举必输态：
第一种（0，0）
第二种（1，2）
第三种（3，5）
第四种  (4 ，7）
第五种（6，10）
第六种  (8，13）
第七种  (9 ， 15）
第八种  (11 ，18）
第n种  （a[k]，b[k]）
 
可以发现他们之间的**差值**是递增序列1234567
第一个数是前面未出现过的最大整数。
既然是差值递增序列且第一个数有独特的出现规则, 可否通过差值和第一个数来判断该局势是否为必输呢？
 
拿第一个数/差值可以发现, 其结果是固定的：
即$\frac{a_k}{b_k-a_{k}} = 1.618$
 
故满足这个条件就是必输局面
转换一下方便判断： $a_{k} = [1.618 * (b_{k}-a_k)]$
0.618是黄金分割率, 1.618可以用 (sqrt(5.0) + 1) / 2 高精度表示

#include <iostream>
#include <cmath>
using namespace std;
 
const int N = 1e2 + 10, M = 1e7, MOD = 100003;
int n, m, k;
int s[N], f[N];
 
int main()
{
    int n, m;
    double f = (sqrt(5.0) + 1.0) / 2.0;
    while (cin >> n >> m)
    {
        if (n > m)
            swap(n, m);
        if (n == (int)((m - n) * f))
            cout << 0 << endl;
        else
            cout << 1 << endl;
    }
 
    return 0;
}