點擊打開鏈接
Rabbit and Grass
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1770 Accepted Submission(s): 1338
Problem Description
大學時光是浪漫的,女生是浪漫的,聖誕更是浪漫的,但是Rabbit和Grass這兩個大學女生在今年的聖誕節卻表現得一點都不浪漫:不去逛商場,不去逛公園,不去和AC男約會,兩個人竟然貓在寢食下棋……
說是下棋,其實隻是一個簡單的小遊戲而已,遊戲的規則是這樣的:
1、 棋盤包含1*n個方格,方格從左到右分別編號為0,1,2,…,n-1;
2、 m個棋子放在棋盤的方格上,方格可以為空,也可以放多於一個的棋子;
3、 雙方輪流走棋;
4、 每一步可以選擇任意一個棋子向左移動到任意的位置(可以多個棋子位於同一個方格),當然,任何棋子不能超出棋盤邊界;
5、 如果所有的棋子都位於最左邊(即編號為0的位置),則遊戲結束,並且規定最後走棋的一方為勝者。
對於本題,你不需要考慮n的大小(我們可以假設在初始狀態,棋子總是位於棋盤的適當位置)。下面的示意圖即為一個1*15的棋盤,共有6個棋子,其中,編號8的位置有兩個棋子。
大傢知道,雖然偶爾不夠浪漫,但是Rabbit和Grass都是冰雪聰明的女生,如果每次都是Rabbit先走棋,請輸出最後的結果。
Input
輸入數據包含多組測試用例,每個測試用例占二行,首先一行包含一個整數m(0<=m<=1000),表示本測試用例的棋子數目,緊跟著的一行包含m個整數Ki(i=1…m; 0<=Ki<=1000),分別表示m個棋子初始的位置,m=0則結束輸入。
Output
如果Rabbit能贏的話,請輸出“Rabbit Win!”,否則請輸出“Grass Win!”,每個實例的輸出占一行。
Sample Input
2 3 5 3 3 5 6 0
Sample Output
Rabbit Win! Grass Win!
Author
lcy
Source
ACM Short Term Exam_2007/12/13
通過找sg函數,發現sg[i]=i,一旦找到sg函數,此題就迎刃而解瞭。
SG函數打表:
#include #include int sg[1007],vis[1007]; int main() { sg[0]=0; int j; for(int i=1;i<=100;i++) { memset(vis,0,sizeof(vis)); for(j=0;j<i;j++)vis[sg[j]]=1; for(j=1;;j++)if(!vis[j])break; sg[i]=j; printf("%d %d\n",i,j); } }
#include int main() { int n,a,sum; while(scanf("%d",&n),n) { sum=0; for(int i=1;i<=n;i++) { scanf("%d",&a); sum^=a; } if(sum)printf("Rabbit Win!\n"); else printf("Grass Win!\n"); } }