POJ - 2348 Euclid's Game

Euclid's Game

博弈

很经典的博弈了

首先明确每个状态必然都对应着一个局面，先手必败 \(or\) 先手必胜

如果当前局面对于先手来说是能够选择的，也就是 \(b >= a * 2\)，对于一个最终局面 \(b' < a\)，如果先手必败，此时先手可以把这个局面丢给对方，否则可以让局面变成 \(b' + a\) 和 \(a\)，让对手把被迫必胜局面留给自己

因此就考虑轮到谁能有选择的时候，谁是先手就获胜

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long a, b;
    while(cin >> a >> b)
    {
        if((a | b) == 0) break;
        int f = 0;
        while(1)
        {
            if(a > b) swap(a, b);
            if(b >= a * 2 || b == a) break;
            b -= a;
            f ^= 1;
        }
        if(f == 0) cout << "Stan wins\n";
        else cout << "Ollie wins\n";
    }
    // cout << endl;
    return 0;
}