HDU 2188：选拔志愿者 ← 巴什博奕(Bash Game)

​【题目来源】
http://acm.hdu.edu.cn/showproblem.php?pid=2188

【题目描述】
••••••
选拔规则如下：
1、最初的捐款箱是空的；
2、两人轮流捐款，每次捐款额必须为正整数，并且每人每次捐款最多不超过 m 元(1<=m<=10)。
3、最先使得总捐款额达到或者超过 n 元（0<n<10000）的一方为胜者，则其可以亲赴灾区服务。
我们知道，两人都很想入选志愿者名单，并且都是非常聪明的人，假设林队先捐，请你判断谁能入选最后的名单？

【输入格式】
输入数据首先包含一个正整数 C，表示包含 C 组测试用例，然后是 C 行数据，每行包含两个正整数 n，m，n 和 m 的含义参见上面提到的规则。

【输出格式】
对于每组测试数据，如果林队能入选，请输出字符串"Grass"， 如果徐队能入选，请输出字符串"Rabbit"，每个实例的输出占一行。

【输入样例】
2
8 10
11 10

【输出样例】
Grass
Rabbit

【数据范围】
1<=m<=10
0<n<10000

【算法分析】
● 巴什博弈（Bash Game）是一个涉及两名玩家的双人博弈，属于公平组合游戏（ICG, Impartial Combinatorial Game）的典型例子。博弈中有一堆总数为 n 的物品，两名玩家轮流从中拿取物品，每次至少拿 1 件，至多拿 m 件，不能不拿，最终将物品拿完者获胜。分析如下：
（1）n≤m 时，由于一次最少拿一个，最多拿 m 个，甲可以一次拿完，先手赢。
（2）n=m+1 时，无论甲拿走多少个 （1~m 个），剩下的都多于 1 个且少于或等于 m 个，乙都能一次拿走剩余的石子，后手取胜。
上面两种情况可以扩展为以下两种情况。
（1）如果 n%(m+1)==0，即 n 是 m+1 的整数倍，那么不管甲拿多少，如 k 个，乙都拿 m+1-k 个，使剩下的永远是 m+1 的整数倍，直到最后的 m+1 个，所以后拿的乙一定赢。
（2）如果 n%(m+1)!=0，即 n 不是 m+1 的整数倍，还有余数 r，那么甲拿走 r 个，剩下的是 m+1 的倍数，这样就转移到了情况（1），相当于甲乙互换，结果是甲赢。
在这个拿石子的游戏中，对于后拿的乙来说是很不利的，只有在 n%(m+1)=0 的情况下乙才能赢，其他所有情况都是甲赢。

● 若仅对单一堆进行操作，两人轮流将数量每次增或减 1～m，先到达目标者胜，均为巴什博弈。​​​​​​​显然，本题为“减法版”的巴什博奕。

【算法代码】

#include <iostream>
using namespace std;

int main() {
    int T;
    cin>>T;
    while(T--) {
        int n,m;
        cin>>n>>m;
        if(n%(m+1)==0) {
            cout<<"Rabbit\n";
        } else cout<<"Grass\n";
    }
    return 0;
}

/*
in:
2
8 10
11 10

out:
Grass
Rabbit
*/

 

 

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/158802453

 

​