P3024 [USACO11OPEN] Cow Checkers S

题目分析：

由题意可将在棋盘中的坐标 (x,y)，看作一堆有 x 个石子的石堆，和一堆有 y 个石子的石堆。

1.向左走任意步：

可以看作将第一堆石子拿出任意个石子。

2.向下走任意步：

可以看作将第二堆石子拿走任意个石子。

3.向左走 k 步然后向下走 k 步（ k 可随便取值，只要不走出棋盘）。

可以看作第一二堆同时拿走任意个石子。

所以这就是经典的个威佐夫博弈。

更据 Betty 定理：经过通项公式可得出结论，当 \frac{\sqrt{5}+1}{2}\times(y-x)=x(x\le y) 时，先手必败，也就是 Bessie 必败，反之则 Farmer John 必败。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,t;
signed main(){
    // step 1、读题、声明变量
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // step 2、输入
    cin>>n>>m>>t;
    // step 3、处理
    while(t--){
        int x,y;
        cin>>x>>y;
        if(x>y) swap(x,y);//维护x比y小 
        double res=(sqrt(5.0)+1.0)*0.5*(y-x);//0.618黄金分割比,Betty定理 
        if((int)res==x) cout<<"Farmer John\n";//Farmer John必胜 
        else cout<<"Bessie\n";//Bessie必胜，Bessie为先手 
    }
    // step 4、输出
    return 0;
}