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;
}