【poj1067】取石子游戏

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

http://poj.org/problem?id=1067 (题目链接)

题意

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

Solution

裸的威佐夫博奕（Wythoff Game），每次求出K判断是否是奇异局面即可。

代码

// poj1067

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#define esp 1e-8

#define inf 2147483640

#define LL long long

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);

using namespace std;

inline LL getint() {

    LL x=0,f=1;char ch=getchar();

    while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int main() {

    int a,b;

    double i=pow(5,0.5);

    while (scanf("%d%d",&a,&b)!=EOF) {

        if (a>b) swap(a,b);

        int k=(double)a*(i-1.0)/2.0;

        int s=k*(1+i)/2;

        if (s==a && a+k==b) printf("0\n");

        else {

            k++;

            s=k*(1+i)/2;

            if (s==a && a+k==b) printf("0\n");

            else printf("1\n");

        }

    }

    return 0;

}