配点

満点

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個の整数をスペース区切りで読み取る。

例：

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

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

例：

```plain
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

* * *

Writer: tomerun

* * *

### Source Name

Autumn Fest

* * *