寒光博客

巴什博弈
Problem Description 1、 本游戏是一个二人游戏; 2、 有一堆石子一共有n个; 3、 ...
扫描右侧二维码阅读全文
23
2019/07

巴什博弈

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

本文作者:Author:     文章标题:巴什博弈
本文地址:https://dxoca.cn/Algorithm/181.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:July 31st, 2019 at 12:16 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment