問題一覧 > 通常問題

No.2848 Birthday Hit and Blow

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : / 解いたユーザー数 19
作問者 : 👑 AngrySadEightAngrySadEight / テスター : tko919tko919 torisasami4torisasami4
1 ProblemId : 11011 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-17 02:37:48

問題文

この問題はインタラクティブな問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う問題）です．

月と日からなる日付を，以下の形式で $4$ 文字の数字からなる文字列として表す方法を，MMDD 形式と呼びます．

  • 月を表す $2$ 桁の数と，日を表す $2$ 桁の数を，この順番に並べて $4$ 文字の数字からなる文字列とみなす．
  • ただし，月や日を表す数が $1$ 桁の場合は，その前に $0$ を加える．
  • 例えば，$1$ 月 $2$ 日，$12$ 月 $13$ 日，$8$ 月 $22$ 日を MMDD 形式で表すと，それぞれ 0102, 1213, 0822 となる．

Alice は，友人の Bob に誕生日のプレゼントを贈りたいと考えています．

Alice は，Bob の誕生日について，「MMDD 形式における各数字が相異なる」ことは知っていましたが，Bob の正確な誕生日を知らないため，いつ贈ればよいのかわかりません．

そこで，Alice は Bob の誕生日を尋ねることにしました．しかし，Bob は直接誕生日を教えてはくれません．そこで，以下の質問をすることによって誕生日を特定しようとすることにしました．

  • 各数字が相異なる $4$ 文字の数字からなる文字列 $S_Q$ を，Bob に伝える．Bob の誕生日の MMDD 形式を $S_A$ としたとき，次の値をそれぞれ教えてもらう．
    • $S_Q$ と $S_A$ の両方に含まれており，その位置も互いに等しい数字の個数 $H$．具体的には，$S_Q$ の $i$ 文字目と $S_A$ の $i$ 文字目が等しい整数 $i(1 \leq i \leq 4)$ の個数．
    • $S_Q$ と $S_A$ の両方に含まれているが，その位置は互いに異なっている数字の個数 $B$．具体的には，$S_Q$ の $i$ 文字目と $S_A$ の $j$ 文字目が等しく，なおかつ $i \neq j$ を満たす整数組 $(i, j)(1 \leq i, j \leq 4)$ の個数．
  • なお，以下に注意せよ．
    • $S_A$ の各数字は相異なることが保証されている．
    • $S_A$ はグレゴリオ暦において実在する日付の MMDD 形式であるが，$S_Q$ はグレゴリオ暦において実在する日付の MMDD 形式である必要はない．

しかし，Bob は気まずく感じてしまうため，$6$ 回までしか質問に答えてくれません．

Alice の立場で，Bob に $6$ 回以内の質問をすることにより，Bob の誕生日を当ててください．

なお，$S_A$ はプログラムとジャッジシステムの対話前に決定されます．

$T$ 個のテストケースが与えられるので，それぞれについて答えてください．

グレゴリオ暦において実在する日付とは

グレゴリオ暦において実在する日付とは，$d = (31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)$ に対して，$1 \leq i \leq 12$ かつ $1 \leq j \leq d_j$ を用いて「$i$ 月 $j$ 日」と表される日付のことを表します．

制約

  • $T$ は整数である．
  • $1 \leq T \leq 200$
  • $S_A$ はグレゴリオ暦において実在する日付の MMDD 形式である．
  • $S_A$ の各桁は相異なる．

入出力

この問題はインタラクティブな問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う問題）です．

あなたのプログラムが Alice の立場で，ジャッジプログラムが Bob の立場となります．

最初に，テストケースの数 $T$ が与えられます．

$T$

以降，$T$ 個のテストケースが続きます．

Bob に質問を行うには，以下の形式で出力してください．ここで，$S_Q$ は各桁が相異なる数字からなる $4$ 文字の文字列である必要があります．

? $S_Q$

この質問への返答は，次の形式で標準入力から与えられます．

$H$ $B$

ここで，$H$ は $S_Q$ と $S_A$ の両方に含まれており，その位置も互いに等しい数字の個数を，$B$ は $S_Q$ と $S_A$ の両方に含まれているが，その位置は互いに異なっている数字の個数を表します．

制約に違反する入力を行った場合や，質問回数が $6$ 回を超えた場合は，$H = -1, B = -1$ が入力として与えられます．この場合，既に不正解と判定されていますので，ただちにプログラムを終了してください．

Bob の誕生日を答える場合は，以下の形式で出力してください．ここで，$S_A$ は Bob の誕生日を MMDD 形式で表した $4$ 文字の文字列です．

! $S_A$

その後，その答えを表す値 $a$ が次の形式で標準入力から与えられます．

$a$

Bob の誕生日を正しく出力できた場合は $a = 0$ が入力として与えられます．この場合，次のテストケースがあれば続けて処理し，なければただちにプログラムを終了してください．

正しく出力できなかった場合は，$a = -1$ が入力として与えられます．この場合も，既に不正解と判定されていますので，ただちにプログラムを終了してください．

注意点

  • 出力のたびに必ず標準出力を flush してください．そうしない場合，TLE になる可能性があります．
  • 不正な出力が行われた場合，ジャッジの結果は不定です．
  • $H = -1, B = -1$ もしくは $a = -1$ が入力として与えられた後に，プログラムをただちに終了しなかった場合，ジャッジの結果は不定です．
  • すべてのテストケースに答えた後は，プログラムをただちに終了してください．そうしなかった場合，ジャッジの結果は不定です．
  • Bob の誕生日を答える出力は，質問回数に含まれません．
リアクティブ問題に慣れていない方は，リアクティブ形式の問題についてのまとめ もご確認ください．

サンプル

入力出力説明
1 $T = 1$ です．
? 1234 $S_Q = $ 1234 として質問を行います．$12$ 月 $34$ 日は存在しない日付ですが，このような質問をしてもかまいません．
0 2 $S_Q = $ 1234 のとき，$H = 0, B = 2$ でした．
? 9810 $S_Q = $ 9810 として質問を行います．
1 1 $S_Q = $ 9810 のとき，$H = 1, B = 1$ でした．
? 0123 $S_Q = $ 0123 として質問を行います．
3 0 $S_Q = $ 0123 のとき，$H = 3, B = 0$ でした．
! 0823 ここまでの情報から，$S_A = $ 0823 であるとわかったので，それを答えます．この出力は質問回数には含まれません．
0 $a = 0$ が入力から与えられたので無事に正解できました．全てのテストケースに対して答えたため，ここでプログラムを終了します．

なお，この一連の流れを図で表すと，以下のようになります．

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。