配点

満点

150

部分点

100

問題文

9桁の整数文字列に対して、マスターマインド（hit and blow）をやる。

基本的なマスターマインドのルールは、次のようなものである。

1. 親が、答えとなる9桁の'0'-'9'からなる文字列を決める。この答えは、同じ数字が複数回現れていても良いし、先頭が0になっていてもよい。
2. 競技者は、答えと思われる9桁の文字列を回答する。
3. 親は、回答に対してhit数とblow数の2つの整数を返す。
   • hit数は、正解と回答を比べて同じ位置に同じ数字がある個数
   • blow数は、hitしている数字を取り除いた後で、min(正解に含まれている数字cの数, 回答に含まれている数字cの数) を '0'<=c<='9' で足しあわせたもの。言葉で言うと、"正解と回答に両方含まれているが位置が異なる数字の個数"
4. 競技者の回答と答えが一致したら終了する。一致しない場合は2.に戻る。

hit数とblow数の例を次に挙げる。ここでは簡潔さのため、9桁ではなく4桁で例を示している。

正解	回答	hit数	blow数
0123	0134	2	1
0123	1199	1	0
0123	9911	0	1
1123	9911	0	2
0113	3911	1	2

ただし、ここでのマスターマインドはちょっと変わっていて、次の条件がついている。

• 競技者は、答えを推測するため、9桁の'0'-'9'からなる文字列9個を同時に送信する（これを"test"と呼ぶ）。送った文字列それぞれに対するhit数とblow数のペア9つが、ランダムな順に並び替えられて返される
• 何回かtestを行って正解が推測できたら、回答として9桁の'0'-'9'からなる文字列を1つだけ送信する（これを"challenge"と呼ぶ）。送信した文字列が答えと一致すればAccepted、間違っていればWrong Answerになる。
• 1つのテストケースを通して、testで同じ文字列を複数回使うことはできない。複数のtestをまたいでいてもだめ
• testは20回以下しか行えない
• challengeは1回しか行えない

次の場合、ジャッジ結果はRuntime Errorになる。

• testを定められた回数を超えて呼び出した
• testで同じ文字列を複数回使用した
• 送信した文字列が定められたフォーマットに合致していなかった

全てのテストケースに正解すると、test回数が一番多かったテストケースについてその回数をTとし、10<=T<=20の場合は100点、T<10の場合は150点が与えられる。

入出力形式

testを行う場合は、標準出力へ文字"?"とスペースに続けて9桁の'0'-'9'からなる文字列9個をスペース区切りで出力し改行する。

例：

printf("? %s %s ... %s\n", t[0], t[1], ... t[8]);
fflush(stdout);

testの結果は、標準入力から18個の整数をスペース区切りで読み取る。

例：

int hit, blow;
for (int i = 0; i < 9; ++i) {
  scanf("%d %d", &hit, &blow);
  // hitやblowを使う
}

challengeを行うときは、標準出力へ文字"!"とスペースに続けて9桁の'0'-'9'からなる文字列を1個出力し改行する。

例：

printf("! %s\n", answer);
fflush(stdout);

入出力例

正解が「123456788」の場合、入出力の一例は次のようになる。

プログラムからの出力	プログラムへの入力
? 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 012345678
	1 0 1 0 2 0 1 0 1 7 1 0 1 0 1 0 1 0
? 000000000 000000001 000000002 000000003 000000004 000000005 000000006 000000007 000000008
	0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0
………	………
! 123456789