UC知道c++简单题，跪求高手详细讲解算法
来源：百度知道 编辑：UC知道 时间：2024/06/05 20:28:28
1、最初的捐款箱是空的；
2、两人轮流捐款，每次捐款额必须为正整数，并且每人每次捐款最多不超过m元(1<=m<=10)。
3、最先使得总捐款额达到或者超过n元（0<n<10000）的一方为胜者，则其可以亲赴灾区服务。
我们知道，两人都很想入选志愿者名单，并且都是非常聪明的人，假设林队先捐，请你判断谁能入选最后的名单？
Input
输入数据首先包含一个正整数C，表示包含C组测试用例，然后是C行数据，每行包含两个正整数n，m，n和m的含义参见上面提到的规则。
Output
对于每组测试数据，如果林队能入选，请输出字符串"Grass"， 如果徐队能入选，请输出字符串"Rabbit"，每个实例的输出占一行。
Sample Input
2
8 10
11 10
Sample Output
Grass
Rabbit
2、两人轮流捐款，每次捐款额必须为正整数，并且每人每次捐款最多不超过m元(1<=m<=10)。
3、最先使得总捐款额达到或者超过n元（0<n<10000）的一方为胜者，则其可以亲赴灾区服务。
我们知道，两人都很想入选志愿者名单，并且都是非常聪明的人，假设林队先捐，请你判断谁能入选最后的名单？
Input
输入数据首先包含一个正整数C，表示包含C组测试用例，然后是C行数据，每行包含两个正整数n，m，n和m的含义参见上面提到的规则。
Output
对于每组测试数据，如果林队能入选，请输出字符串"Grass"， 如果徐队能入选，请输出字符串"Rabbit"，每个实例的输出占一行。
Sample Input
2
8 10
11 10
Sample Output
Grass
Rabbit
定值取模,很简单的博弈问题.
如果m>=n很显然...我就不说了
m=1的时候,也没什么好说的...
现在只讨论m<n
其实，只要G队捐了一次恰好可以保证剩下来的是 (m+1)*k (k是任意自然数),就可以保证取胜.现在来说说这个(m+1)的渊源.
显然当k=0的时候G已经取胜了(刚好捐完了嘛);
当k!=0时,假设这个时候R捐了a元,那么G就捐 m+1-a元,而且这一点是肯定可以办得到的,因为 1 <= a <= m,故1 <= m+1-a <= m ;
这样一轮以后, k比原来要小1, 于是反复进行,直到k=0,大功告成,G可以去四川了.
那么怎么判断G队“捐了一次恰好可以保证剩下来的是 (m+1)*k”呢?
这是常识,或者说是数论中的一个基本定理,我就不多说了,看代码(c语言):
#include<stdio.h>
int main()
{
int c,n,m;
for(scanf("%d",&c);c--;)
{
scanf("%d%d",&n,&m);
if(m == 1) /* 毫无策略地竞争 */
{
puts( n&1 ? "Grass" : "Rabbit" );
continue;
}
if(m >= n) /* G队一出手摆平了 */
{
puts("Grass");
continue;
}
if(0 != n%(m+1)) /* 只需要这样就可以了，所以说G获胜的几率相当大 */
{
puts("Grass");
}
else
{
puts("Rabbit");