HDU 1847 Good Luck in CET-4 Everybody!
8865 ワード
Good Luck in CET-4 Everybody!
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3352 Accepted Submission(s): 2099
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
ゲームのSG問題の解き方は通法だが、まだ覚えていない.
1 win
2 win
3 lost
4 win
5 win
6 lost
7 win
8 win
9 lost
10 win
11 win
12 lost
13 win
14 win
15 lost
16 win
17 win
18 lost
lostのを探し出して3 6 9 12 15 18額、3の倍数.
数字の増加は規則的で、1 2 4 8 16 32.....だから、このような結論も可能です.いつも1つの特殊な情況を探して、打ち破るこのような3倍数の情況、先に試みてみます...
過ぎたなんて
コード:
SGゲーム解の王道.
ポイントはSGの解に対して、直接すべての状況を表にします.sgの値が0の場合、奇異な状態で、負けて、さもなくば勝つ.
いくつかの例を示して説明する.他人の牛人のブログを貼る.
Ø g(0)={},G(0)={0, 1, …},f(0)=0;
Ø g(1)={},G(1)={0, 1, …},f(1)=0;
Ø g(2)={#(0)}={f(0)}={0},G(2)={1, 2, …},f(2)=1;
Ø g(3)={#(1)}={f(1)}={0},G(2)={1, 2, …},f(3)=1;
Ø g(4)={#(2), #(1, 1)}={f(2), f(1)+f(1)}={1, 0},G(4)={2, 3, …},f(4)=2;
Ø g(5)={#(3), #(1, 2)}={f(3), f(1)+f(2)}={1, 1},G(5)={0, 2, 3, …},f(5)=0;
Ø g(6)={#(4), #(1, 4), #(2, 2)}={2, 1, 0},G(6)={3, 4, …},f(6)=3;
Ø g(7)={#(4), #(1, 4), #(2, 3)}={2, 2, 0},G(7)={1, 3, 4, …},f(7)=1;
G 図2に示す局面S=(7, 3, 3)#S=f(7)+f(3)+f(3)=1+1+1=1があるので、Sが勝つ.
G ゲームCの初期局面S=(3, 4, 6)#S=1+2+3=01+10+11=0であるため、Sは負である.
手順:
2 このようなゲームゲームの一般的な解法:
F nメタグループ(a 1, a2, …, an)は,ゲーム中の局面を記述する.
F 局面Sに対応するバイナリ数を符号Sで表す.
F 記号$(x)で、局面(x)の次のすべての出現可能な局面の集合を表す.
F 定義集合g(x):$(x)={S 1, S2, …, Sk},g(x)={#S 1, #S2, …, #Sk}.
F 非負の整数セットを集合とし、集合G(x)は集合g(x)の補完を表す.
F 定義関数f(n):f(n)=min{G(n)}であり、すなわちf(n)は集合G(n)の最小数に等しい.
F 局面S=(a 1, a2, …, an),#S=f(a 1)+f(a 2)+…+f(an)は,2進数の加算を用いる.
ちょっと煩わしい感じがしますが、コードを組み合わせて分析してみましょう.
{
1.まず、次の状況が発生する可能性があることを要求します.
2.対応するSG値は配列で表記する.
3.最小値を見つけます.}
コード:
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3352 Accepted Submission(s): 2099
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
ゲームのSG問題の解き方は通法だが、まだ覚えていない.
1 win
2 win
3 lost
4 win
5 win
6 lost
7 win
8 win
9 lost
10 win
11 win
12 lost
13 win
14 win
15 lost
16 win
17 win
18 lost
lostのを探し出して3 6 9 12 15 18額、3の倍数.
数字の増加は規則的で、1 2 4 8 16 32.....だから、このような結論も可能です.いつも1つの特殊な情況を探して、打ち破るこのような3倍数の情況、先に試みてみます...
過ぎたなんて
コード:
#include<stdio.h>
int main()
{
int k,n;
while(scanf("%d",&n)>0)
{
k=n%3;
if(k==0)
printf("Cici
");
else printf("Kiki
");
}
return 0;
}SGゲーム解の王道.
ポイントはSGの解に対して、直接すべての状況を表にします.sgの値が0の場合、奇異な状態で、負けて、さもなくば勝つ.
いくつかの例を示して説明する.他人の牛人のブログを貼る.
Ø g(0)={},G(0)={0, 1, …},f(0)=0;
Ø g(1)={},G(1)={0, 1, …},f(1)=0;
Ø g(2)={#(0)}={f(0)}={0},G(2)={1, 2, …},f(2)=1;
Ø g(3)={#(1)}={f(1)}={0},G(2)={1, 2, …},f(3)=1;
Ø g(4)={#(2), #(1, 1)}={f(2), f(1)+f(1)}={1, 0},G(4)={2, 3, …},f(4)=2;
Ø g(5)={#(3), #(1, 2)}={f(3), f(1)+f(2)}={1, 1},G(5)={0, 2, 3, …},f(5)=0;
Ø g(6)={#(4), #(1, 4), #(2, 2)}={2, 1, 0},G(6)={3, 4, …},f(6)=3;
Ø g(7)={#(4), #(1, 4), #(2, 3)}={2, 2, 0},G(7)={1, 3, 4, …},f(7)=1;
G 図2に示す局面S=(7, 3, 3)#S=f(7)+f(3)+f(3)=1+1+1=1があるので、Sが勝つ.
G ゲームCの初期局面S=(3, 4, 6)#S=1+2+3=01+10+11=0であるため、Sは負である.
手順:
2 このようなゲームゲームの一般的な解法:
F nメタグループ(a 1, a2, …, an)は,ゲーム中の局面を記述する.
F 局面Sに対応するバイナリ数を符号Sで表す.
F 記号$(x)で、局面(x)の次のすべての出現可能な局面の集合を表す.
F 定義集合g(x):$(x)={S 1, S2, …, Sk},g(x)={#S 1, #S2, …, #Sk}.
F 非負の整数セットを集合とし、集合G(x)は集合g(x)の補完を表す.
F 定義関数f(n):f(n)=min{G(n)}であり、すなわちf(n)は集合G(n)の最小数に等しい.
F 局面S=(a 1, a2, …, an),#S=f(a 1)+f(a 2)+…+f(an)は,2進数の加算を用いる.
ちょっと煩わしい感じがしますが、コードを組み合わせて分析してみましょう.
{
1.まず、次の状況が発生する可能性があることを要求します.
2.対応するSG値は配列で表記する.
3.最小値を見つけます.}
コード:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int hash[1001],SG[1001];
int arry[12]={12,1,2,4,8,16,32,64,128,256,512,1024};
void getsg()
{
int tmp,i,j;
for(i=0;i<=1000;i++)
{
memset(hash,0,sizeof(hash[0]));// sg[i] ，
for(j=1;j<arry[0];j++)
{
if(arry[j]>i) //
break;
tmp=i-arry[j];
hash[SG[tmp]]=1; // g(5)={#(3), #(1, 2)}={f(3),f(1)+f(2)}={1, 1}，f(5)=0；
//f(n) SG[i].
}
for(j=0;;j++) // 。
if(hash[j]==0)
{
SG[i]=j; // SG[i]=1; hash[SG[tmp]]=1 。
break;
}
}
}
int main()
{
int k,n;
memset(SG,0,sizeof(SG[0]));
getsg();
while(scanf("%d",&n)>0)
{
k=SG[n];
if(k==0)
printf("Cici
");
else printf("Kiki
");
}
return 0;
}