Posted on 2010-08-09 21:37
MiYu 閱讀(468)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM ( 組合 ) 、
ACM ( 博弈 )
MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2188
題目描述:
悼念512汶川大地震遇難同胞——選拔志愿者
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1337 Accepted Submission(s): 716
Problem Description
對(duì)于四川同胞遭受的災(zāi)難，全國(guó)人民紛紛伸出援助之手，幾乎每個(gè)省市都派出了大量的救援人員，這其中包括搶險(xiǎn)救災(zāi)的武警部隊(duì)，治療和防疫的醫(yī)護(hù)人員，以及進(jìn)行心理疏導(dǎo)的心理學(xué)專家。根據(jù)要求，我校也有一個(gè)奔赴災(zāi)區(qū)救災(zāi)的名額，由于廣大師生報(bào)名踴躍，學(xué)校不得不進(jìn)行選拔來(lái)決定最后的人選。經(jīng)過(guò)多輪的考核，形勢(shì)逐漸明朗，最后的名額將在“林隊(duì)”和“徐隊(duì)”之間產(chǎn)生。但是很巧合，2個(gè)人的簡(jiǎn)歷幾乎一模一樣，這讓主持選拔的8600很是為難。無(wú)奈，他決定通過(guò)捐款來(lái)決定兩人誰(shuí)能入選。
選拔規(guī)則如下：
1、最初的捐款箱是空的；
2、兩人輪流捐款，每次捐款額必須為正整數(shù)，并且每人每次捐款最多不超過(guò)m元(1<=m<=10)。
3、最先使得總捐款額達(dá)到或者超過(guò)n元（0<n<10000）的一方為勝者，則其可以親赴災(zāi)區(qū)服務(wù)。
我們知道，兩人都很想入選志愿者名單，并且都是非常聰明的人，假設(shè)林隊(duì)先捐，請(qǐng)你判斷誰(shuí)能入選最后的名單？
Input
輸入數(shù)據(jù)首先包含一個(gè)正整數(shù)C，表示包含C組測(cè)試用例，然后是C行數(shù)據(jù)，每行包含兩個(gè)正整數(shù)n，m，n和m的含義參見上面提到的規(guī)則。
Output
對(duì)于每組測(cè)試數(shù)據(jù)，如果林隊(duì)能入選，請(qǐng)輸出字符串"Grass"， 如果徐隊(duì)能入選，請(qǐng)輸出字符串"Rabbit"，每個(gè)實(shí)例的輸出占一行。
Sample Input
2
8 10
11 10
Sample Output
Grass
Rabbit
題目分析:
非常非常標(biāo)準(zhǔn)的 bash 博弈, 只要把 捐款看成取款就行了, 誰(shuí)最后取光錢誰(shuí)就贏. 更多資料請(qǐng)點(diǎn)擊
博弈入門代碼如下:
MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
#include <iostream>
int main ()
{
int T;
scanf ( "%d",&T );
{
while ( T -- )
{
int n,m;
scanf ( "%d%d", &n, &m );
puts ( n % ( 1 + m ) != 0 ? "Grass" : "Rabbit" );
}
}
return 0;
}