Problem Description
1、 本游戏是一个二人游戏;
2、 有一堆石子一共有n个;
3、 两人轮流进行;
4、 每走一步可以取走1…m个石子;
5、 最先取光石子的一方为胜;
如果游戏的双方使用的都是最优策略,请输出哪个人能赢。
Input
输入数据首先包含一个正整数C(C<=100),表示有C组测试数据。
每组测试数据占一行,包含两个整数n和m(1<=n,m<=1000),n和m的含义见题目描述。
Output
如果先走的人能赢,请输出“first”,否则请输出“second”,
每个实例的输出占一行。
Sample Input
2
23 2
4 3
Sample Output
first
second
解题思路:
一次可以去走1,2,3…m个石子,容易得出该问题的PN图, 1,2,3...m
为必胜状态,m+1为必败状态,其余类推即可。所以只要n%(m+1) == 0
则先手必输反之先手必胜。
代码
#include <iostream>
using namespace std;
int main() {
int n, a, b;
cin >> n;
while(n--) {
cin >> a >> b;
if(a%(b+1) == 0)
cout << "second\n";
else
cout << "first\n";
}
return 0;
}
参考文献
[1] https://blog.csdn.net/pengwill97/article/details/76796070
[2] https://blog.csdn.net/qq_41289920/article/details/82793034
[1] https://blog.csdn.net/pengwill97/article/details/76796070
[2] https://blog.csdn.net/qq_41289920/article/details/82793034
本文作者:Author: 寒光博客
文章标题:巴什博弈
本文地址:https://dxoca.cn/Algorithm/181.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/Algorithm/181.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。