欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

zcmu 1122: 取石子游戏II

程序员文章站 2022-07-15 13:37:38
...

1122: 取石子游戏II

Time Limit: 1 Sec Memory Limit: 128 MB

Description

一堆石子有n个,两人轮流取.每次取最少取1个,最多取m个。取完者胜.先取者负输出"Second win".先取者胜输出"First win"

Input

多组测试数据。

每组测试数据包含2个正整数n,m。(n,m<=10000000)

Output

对于每组测试数据,输出谁获胜.

Sample Input

2 1
3 2
3 1
Sample Output

Second win
Second win
First win
HINT

Source

【分析】
经典的巴什博弈,这个我觉得相较于斐波那契博弈,巴什博弈更好理解一点;
归纳一句话就是:给对手留下(m+1)的倍数,自己就能赢
那么,要先手并且n%(m+1)==0的话,是不是就不可以给对手留下(m+1)的倍数了,此时,先手必败!

【代码】

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
   int n,m;
   while(scanf("%d%d",&n,&m)!=EOF)
   {
       if(n%(m+1)==0)
       {
           printf("Second win\n");
       }
       else
       {
           printf("First win\n");
       }
   }
    return 0;
}