hdu 1847ゲーム基礎問題SG関数または法則の2つの方法
2839 ワード
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
大学の英語の4級試験がもうすぐ来ます.緊張して復習していますか.短学期のACMも練習する暇がないほど緊張しているかもしれませんが、どうせ私が知っているKikiもCiciもそうです.もちろん、試験場に十数年も浸潤した現代の大学生として、KikiとCiciは試験前のリラックスをもっと知っていて、いわゆる「弛緩有道」という意味です.いいえ、KikiとCiciは毎晩休む前にトランプをして神経をリラックスします.
「アップグレード」?「ダブルボタン」?「紅五」?それとも「闘地主」ですか.
もちろん違います!それはなんと俗っぽいことか.
コンピューター学院の学生として、KikiとCiciがトランプをするときは専門を忘れていません.彼女たちのトランプのルールはこうです.
1、 全部でn枚のカード;
2、 双方が交代でカードをつかむ.
3、 1人当たりのカードの個数は2のべき乗(1,2,4,8,16...)しかありません.
4、 カードを捕まえたら、勝負の結果も出てきた.最後にカードを捕まえた人は勝者だ.
KikiもCiciも十分頭がいいと仮定し(実は仮定しなくても、頭が悪い学生はいない~)、毎回Kikiが先にカードをつかんでいると仮定しますが、誰が勝つことができますか?
もちろん、トランプは誰が勝っても問題ありませんが、重要なのはすぐに来るCET-4が良い状態になることです.
Good luck in CET-4 everybody!
Input
入力データには複数のテストケースが含まれ、各テストケースは1行を占め、整数n(1<=n<=1000)を含む.
Output
Kikiが勝てば「Kiki」を出力し、そうでなければ「Cici」を出力し、各インスタンスの出力が1行を占めます.
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つの倍数は必敗状態です だからある
もう一つの方法はSG関数を探すことです
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3552 Accepted Submission(s): 2232
Problem Description
大学の英語の4級試験がもうすぐ来ます.緊張して復習していますか.短学期のACMも練習する暇がないほど緊張しているかもしれませんが、どうせ私が知っているKikiもCiciもそうです.もちろん、試験場に十数年も浸潤した現代の大学生として、KikiとCiciは試験前のリラックスをもっと知っていて、いわゆる「弛緩有道」という意味です.いいえ、KikiとCiciは毎晩休む前にトランプをして神経をリラックスします.
「アップグレード」?「ダブルボタン」?「紅五」?それとも「闘地主」ですか.
もちろん違います!それはなんと俗っぽいことか.
コンピューター学院の学生として、KikiとCiciがトランプをするときは専門を忘れていません.彼女たちのトランプのルールはこうです.
1、 全部でn枚のカード;
2、 双方が交代でカードをつかむ.
3、 1人当たりのカードの個数は2のべき乗(1,2,4,8,16...)しかありません.
4、 カードを捕まえたら、勝負の結果も出てきた.最後にカードを捕まえた人は勝者だ.
KikiもCiciも十分頭がいいと仮定し(実は仮定しなくても、頭が悪い学生はいない~)、毎回Kikiが先にカードをつかんでいると仮定しますが、誰が勝つことができますか?
もちろん、トランプは誰が勝っても問題ありませんが、重要なのはすぐに来るCET-4が良い状態になることです.
Good luck in CET-4 everybody!
Input
入力データには複数のテストケースが含まれ、各テストケースは1行を占め、整数n(1<=n<=1000)を含む.
Output
Kikiが勝てば「Kiki」を出力し、そうでなければ「Cici」を出力し、各インスタンスの出力が1行を占めます.
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
");
else printf("Kiki
");
}
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
");
}
else printf("Cici
");
}
return 0;
}