注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

HDU 2188 悼念512汶川大地震遇难同胞——选拔志愿者  

2014-05-07 20:50:23|  分类: 博弈入门 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
捐款额<n-m-1并且比较接近这个值,那么对手就能使捐款额达到n-m-1从而使自己进入必输的境地。因此问题就归结为谁最先使捐款额达到n-(m+1)就能获胜。继续上述分析就知道,谁先达到n-k(m+1),其中k为使n-k(m+1)为正的最大正整数,谁就能获胜。而策略就是使对手的上一次捐款和自己的本次捐款额和为m+1即可
因此只要n mod (m+1)==0,就是后手必胜,否则先手必胜。

对于四川同胞遭受的灾难,全国人民纷纷伸出援助之手,几乎每个省市都派出了大量的救援人员,这其中包括抢险救灾的武警部队,治疗和防疫的医护人员,以及进行心理疏导的心理学专家。根据要求,我校也有一个奔赴灾区救灾的名额,由于广大师生报名踊跃,学校不得不进行选拔来决定最后的人选。经过多轮的考核,形势逐渐明朗,最后的名额将在“林队”和“徐队”之间产生。但是很巧合,2个人的简历几乎一模一样,这让主持选拔的8600很是为难。无奈,他决定通过捐款来决定两人谁能入选。
选拔规则如下:
1、最初的捐款箱是空的;
2、两人轮流捐款,每次捐款额必须为正整数,并且每人每次捐款最多不超过m元(1<=m<=10)。
3、最先使得总捐款额达到或者超过n元(0<n<10000)的一方为胜者,则其可以亲赴灾区服务。
我们知道,两人都很想入选志愿者名单,并且都是非常聪明的人,假设林队先捐,请你判断谁能入选最后的名单?

 


Input

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

 


Output

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

 

#include<stdio.h>


int main()
{
int a,b,c;
scanf("%d",&c);
while(c--)
{
scanf("%d%d",&a,&b);
if(a%(b+1)==0)
{

printf("Rabbit\n");
}
else
{
printf("Grass\n");
}
}
return 0;
}


  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017