Posted on 2010-08-09 21:09
MiYu 閱讀(449)
評論(0) 編輯 收藏 引用 所屬分類:
ACM ( 組合 ) 、
ACM ( 博弈 )
MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1849
題目描述:
Problem Description
大學(xué)時光是浪漫的，女生是浪漫的，圣誕更是浪漫的，但是Rabbit和Grass這兩個大學(xué)女生在今年的圣誕節(jié)卻表現(xiàn)得一點都不浪漫：不去逛商場，不去逛公園，不去和AC男約會，兩個人竟然貓在寢食下棋……
說是下棋，其實只是一個簡單的小游戲而已，游戲的規(guī)則是這樣的：
1、 棋盤包含1*n個方格，方格從左到右分別編號為0，1，2，…，n-1；
2、 m個棋子放在棋盤的方格上，方格可以為空，也可以放多于一個的棋子；
3、 雙方輪流走棋；
4、 每一步可以選擇任意一個棋子向左移動到任意的位置（可以多個棋子位于同一個方格），當(dāng)然，任何棋子不能超出棋盤邊界；
5、 如果所有的棋子都位于最左邊（即編號為0的位置），則游戲結(jié)束，并且規(guī)定最后走棋的一方為勝者。
對于本題，你不需要考慮n的大小（我們可以假設(shè)在初始狀態(tài)，棋子總是位于棋盤的適當(dāng)位置）。下面的示意圖即為一個1*15的棋盤，共有6個棋子，其中，編號8的位置有兩個棋子。
大家知道，雖然偶爾不夠浪漫，但是Rabbit和Grass都是冰雪聰明的女生，如果每次都是Rabbit先走棋，請輸出最后的結(jié)果。
Input
輸入數(shù)據(jù)包含多組測試用例，每個測試用例占二行，首先一行包含一個整數(shù)m（0<=m<=1000），表示本測試用例的棋子數(shù)目，緊跟著的一行包含m個整數(shù)Ki(i=1…m; 0<=Ki<=1000)，分別表示m個棋子初始的位置，m=0則結(jié)束輸入。
Output
如果Rabbit能贏的話，請輸出“Rabbit Win!”，否則請輸出“Grass Win!”，每個實例的輸出占一行。
Sample Input
2
3 5
3
3 5 6
0
Sample Output
Rabbit Win!
Grass Win!
題目分析 :
MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
標(biāo)準(zhǔn) 的 nim 博弈 問題, 不要想復(fù)雜了 . 因為只能往左移, 所以可以將 初始的每個棋子的位置看成一個堆, 比如說, 1個棋子在 n-1格, 那么就代表這個堆有 n-1個數(shù)
左移1格,就是取走一個, 所以有 m 棋子就代表有m個堆, 全部到0就是取完了............ 更具體的 nim 博弈介紹請點擊 << 博弈入門 >>
代碼如下:
MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
#include <iostream>
int heap[1001];
int main ()
{
int T;
while ( scanf ( "%d",&T ), T )
{
int res = 0 , nCount = 0;
for ( int i = 0; i != T; ++ i )
{
scanf ( "%d",heap + i );
res ^= heap[i];
}
puts ( res == 0 ? "Grass Win!" : "Rabbit Win!" );
}
return 0;
}