威佐夫博弈

有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。

 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

我们用（a_i,b_i）表示当前局势，当前局势为以下情况者（证明略），先手必输：

（0,0）

（1,2）

（3,5）

（4,7）

（6,10）

（8,13）

（9,15）

（11,18）

　……

（a_n,b_n）

 

结论：

　　a_n=未在前面出现过的最小的自然数=(int)((b_n-a_n)*1.618)。

 

using namespace std;
main()
{
    int a,b;
    scanf("%lld%lld",&a,&b);
    if(a>b) swap(a,b);
    int temp=abs(a-b);
    int ans=temp*(1.0+sqrt(5.0))/2.0;
    if(ans==a) printf("Second");
    else       printf("First");
    return 0;
}

 

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄