Posted on 2010-08-09 21:37
MiYu 閱讀(468)
評論(0) 編輯 收藏 引用 所屬分類:
ACM ( 組合 ) 、
ACM ( 博弈 )
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
題目地址:
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
對于四川同胞遭受的災難，全國人民紛紛伸出援助之手，幾乎每個省市都派出了大量的救援人員，這其中包括搶險救災的武警部隊，治療和防疫的醫護人員，以及進行心理疏導的心理學專家。根據要求，我校也有一個奔赴災區救災的名額，由于廣大師生報名踴躍，學校不得不進行選拔來決定最后的人選。經過多輪的考核，形勢逐漸明朗，最后的名額將在“林隊”和“徐隊”之間產生。但是很巧合，2個人的簡歷幾乎一模一樣，這讓主持選拔的8600很是為難。無奈，他決定通過捐款來決定兩人誰能入選。
選拔規則如下：
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
題目分析:
非常非常標準的 bash 博弈, 只要把 捐款看成取款就行了, 誰最后取光錢誰就贏. 更多資料請點擊
博弈入門代碼如下:
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
#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;
}