H : Typing Game / タイピングゲーム

物語

ここからは，タイピング力を鍛える時間です．皆さんは早く正確なタイピングをすることができますか？ Let’s enjoy Typing Game!

問題

タイピングゲームのゲームシステムとして，ジャッジ側が用意したAIの出力に対して対話的に動作するプログラムを作成せよ．

AIは N 個の文字列をタイプするゲームをプレイする．AIは体力を持っており，その初期値は H である．AIは体力がある限り文字のタイプを行う．システムはAIがタイプすべき文字列を提示する．システムはAIがタイプした文字を受け取り，次にタイプすべき文字と一致するか判定する．AIが文字列を1つタイプし終えると，システムは次の文字列を提示する．

また，各文字列にはミスタイプの許容回数が定められている．AIのある文字列におけるミスタイプの回数が許容回数を超えてしまうとAIの体力が1減り，システムは強制的に次の文字列を提示する．AIの体力が0になったらゲームオーバーとなる．最後の文字列において，タイプの成功またはミスタイプ回数の超過が起こった後で，AIの体力が残っていればゲームクリアとなる．

入出力形式

まず，入力が以下の形式で与えられる．

 N H
 S_1 T_1
 ...
 S_N T_N

1行目に文字列の数 N とAIの体力 H が空白区切りで与えられる．

続く N 行には i 行目に i 番目の文字列 S_i と，その文字列に対するミスタイプの許容回数 T_i が空白区切りで与えられる．

この入力は以下の制約を満たす．

• 1 ≤ N ≤ 100
• 1 ≤ H ≤ 10
• 1 ≤ |S_i| ≤ 15
• S_i はアルファベット'a'-'z'，または'A'-'Z'のみを含む．
• 0 ≤ T_i ≤ 20

システムは文字列 S_1 から文字列 S_N まで順番に処理をする．i 番目の文字列 S_i について，AIが j 文字目までタイプを成功させている場合，以下の処理をする．

システムはAIに対して，S_i を出力する．このとき，S_i の1文字目から j 文字目を"_" (アンダースコア) に置き換える．システムが間違った文字列を出力すると，AIは動作を中断しWrong Answerとなる．システムが出力する文字列が S である場合，C/C++での出力例は以下のようになる．

printf("? %s\n", S); fflush(stdout);

AIはシステムの出力を受け取ると，

c

の形式で返答する．c はAIがタイプした文字である．c はアルファベット'a'-'z'からなる．C/C++での返答の受け取り方の例は以下のようになる．

 char c[2];
 scanf("%s", c);
 /*
 char c;
 scanf("%c", &c);
 は空白文字読み込みの仕様上の理由で非推奨です．
 */

システムはAIの出力を受け取るとまずAIがタイプした文字と S_i の j+1 文字目が一致しているか判定する．この判定の際，大文字と小文字は区別しないことに注意せよ．一致しているときは，j+1 文字目までタイプに成功したとする．ここで j+1 文字目が S_i の最後の文字だった場合，S_i のタイプに成功したとし S_i の処理を終える．AIがタイプした文字と S_i の j+1 文字目が一致していなければ，S_i に対するミスタイプ回数を1だけ増やす．このとき T_i を超えていればAIの体力を1減らし，S_i の処理を終える．S_i の処理を終えたとき，AIの体力が0であればゲームオーバーとする．ゲームオーバーでなければ i が N のときゲームクリアとし，そうでなければ S_{i+1} の処理に移る．

また，ゲームオーバーの際には"! Game Over"を，ゲームクリアの際には"! Game Clear [タイプ成功率]"を出力せよ．タイプ成功率は (成功タイプ数) / (合計タイプ数) × 100 で計算される値を小数点以下第2位で切り捨てた値とする．小数点以下第1位が0であっても小数点以下第1位まで出力せよ．C/C++での出力例は以下のようになる．

printf("! Game Over\n"); fflush(stdout);

printf("! Game Clear %.1lf\n", success_type_rate); fflush(stdout);

※printfの書式を"%.1lf"とした場合，出力される浮動小数点数は小数点以下第2位が四捨五入される．このため，タイプ成功率を浮動小数点数として計算し，上記の手法で出力した場合，正しい出力結果が得られないことがあることに注意せよ．

入出力例1

システムの出力
システムへの入力・AIの返答

2 5
ICPC 2
Tsurai 5

? ICPC

i
? _CPC

g
? _CPC

p
? _CPC

c
? __PC

p
? ___C

c
? Tsurai

t
? _surai

s
? __urai

u
? ___rai

r
? ____ai

a
? _____i

i
! Game Clear 83.3

入出力例2

システムの出力 
システムへの入力・AIの返答

2 1
ICPC 1
Tsurai 1

? ICPC

i
? _CPC

c
? __PC

o
? __PC

p
? ___C

d
! Game Over