题解 P2252 【取石子游戏】

火柴神 · 2016-08-26 19:52:57 · 题解

一道威佐夫博弈的题

令k=abd(a-b)

flag=k*(1+√5)/2

若flag=a则先取必败

具体证明这里不写了

代码如下

#include <iostream>
#include<cstdio>
#include <cmath>
using namespace std;
int main(){     
    int a,b;    
    scanf("%d%d",&a,&b);
    if (a > b){
        int temp;
        temp = a;
        a = b;
        b =temp;
    }
    int k = b - a;
    int data = floor(k*(1.0+sqrt(5.0))/2.0);
    if (data == a)
        printf("0");
    else
        printf("1");
}