Good Luck in CET-4 Everybody!
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3552 Accepted Submission(s): 2232
Problem Description
大學英語四級考試就要來臨了,你是不是在緊張的復習?也許緊張得連短學期的ACM都沒工夫練習了,反正我知道的Kiki和Cici都是如此。當然,作為在考場浸潤了十幾載的當代大學生,Kiki和Cici更懂得考前的放松,所謂“張弛有道”就是這個意思。這不,Kiki和Cici在每天晚上休息之前都要玩一會兒撲克牌以放松神經。
“升級”?“雙扣”?“紅五”?還是“斗地主”?
當然都不是!那多俗啊~
作為計算機學院的學生,Kiki和Cici打牌的時候可沒忘記專業,她們打牌的規則是這樣的:
1、 總共n張牌;
2、 雙方輪流抓牌;
3、 每人每次抓牌的個數只能是2的冪次(即:1,2,4,8,16…)
4、 抓完牌,勝負結果也出來了:最後抓完牌的人為勝者;
假設Kiki和Cici都是足夠聰明(其實不用假設,哪有不聰明的學生~),並且每次都是Kiki先抓牌,請問誰能贏呢?
當然,打牌無論誰贏都問題不大,重要的是馬上到來的CET-4能有好的狀態。
Good luck in CET-4 everybody!
Input
輸入數據包含多個測試用例,每個測試用例占一行,包含一個整數n(1<=n<=1000)。
Output
如果Kiki能贏的話,請輸出“Kiki”,否則請輸出“Cici”,每個實例的輸出占一行。
Sample Input
1
3
Sample Output
Kiki
Cici
Author
lcy
Source
ACM Short Term Exam_2007/12/13
Recommend
lcy
第一種方法 規律:根據必勝態必敗態的特性
P 為必敗態 N為必勝態
則 x 0 1 2 3 4 5 6 7 8 9 10 11 12
狀態 P N N P N N P N N P N N P
故3個倍數為必敗態 所以 有
#include<stdio.h> int main() { int i,j,n; while(scanf("%d",&n)!=EOF) { if(n%3==0) printf("Cici\n"); else printf("Kiki\n"); } return 0; }
另外一種方法 就是找SG函數
#include<stdio.h> #include<string.h> int SG[1111],vis[1111]; void get_sg() { int i,j,num[20]; for(i=0;i<=10;i++) num[i]=1<<i; for(i=0;i<=1000;i++) { if(!SG[i])//必敗態 for(j=0;j<=10;j++) { if(i+num[j]<=1000) SG[i+num[j]]=1;//必勝態 } } } int main() { int n,i,j; get_sg(); while(scanf("%d",&n)!=EOF) { if(SG[n]==1) { printf("Kiki\n"); } else printf("Cici\n"); } return 0; }