問題一覧 > 通常問題

No.624 Santa Claus and The Last Dungeon

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 10
作問者 : e869120e869120 / テスター : 紙ぺーぱー紙ぺーぱー
1 ProblemId : 2040 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-08-23 23:20:51

連絡

重要! Advent Calendar Contest も あと 2 日!
最後の 2 日間、ぜひお楽しみください!

重要な情報

この問題はリアクティブ問題です。

ストーリー展開

Yukicoder は、Santa Claus からプレゼントを貰おうとした。
しかし、Santa Claus はいたずら者だったので、以下のような条件をもとにプレゼントを渡すことにした。

  • あそこにダンジョンがある。その最後の部屋まで追い詰め、この部屋であなたが勝利したら、プレゼントを渡す。

順調に戦いを行った結果、最後の部屋まで Santa Claus を追い詰めることが出来た。しかし・・・
yukicoder 「なんだこれは、、、鍵が、鍵が、100 個もあるのではないか!?」


これが開けられれば勝ちなのに、ここで諦めるわけにはいかない。

問題

最後のダンジョンを開けるためには、$100$ 個の鍵の暗号を入力する必要があります。ただしその暗号の答えは以下の条件を満たします。
  • 全ての暗号の答えは、$00$ 以上 $99$ 以下の $2$ 桁の $10$ 進整数である。
  • 全ての暗号の答えは違う。つまり、$i$ 個目の暗号を $a_i$ とした時、$i≠j$ のとき絶対に $a_i≠a_j$ を満たす。

しかし、鍵の暗号をヒントなしで開けることは非常に難しいので、Santa Claus は、下のようなヒントを出すことにしました。
  • Santa Claus は、yukicoder が暗号を全部入力し終え、決定ボタンを押すときに毎回ヒントを出す。
  • 内容は、"0 個の桁が合っている場所の個数"・"1 個の桁が合っている場所の個数"・"2 個 (全部) の桁が合っている場所の個数" を教えてくれるというものである。
  • 但し、一部の暗号の桁を入れずに決定を押すこともでき、入れなかった桁は、「合っていない桁」として判定される。

ただし、「桁が合っている個数」は以下のように定義されます。
  • $A$ $=$ $a_0$$a_1$, $B$ $=$ $b_0$$b_1$ のとき($A$ = 暗号の答え、$B$ = 入力した暗号、とする)
  • $a_0 = b_0$, $a_1 = b_1$, のうち成り立っている個数を「桁が合っている個数」とする。
  • 例えば、$23$ と $53$ は 1 個の桁が合っている。
  • また、$23$ と $5?$ は 0 個の桁が合っている。(下の桁は入力されていないため)

yukicoder は決定ボタンを $Q$ 回まで押すことができます。さもないと、あの扉は永遠に閉まってしまいます。
あなたは優秀なプログラミング能力を持つ、yukicoder と協力して戦う戦士です。できるだけ最適に暗号を入れ、質問し、最後に正しい暗号を入力して扉を開けましょう。

ただし、暗号を、一部の場所の一部の桁に対して、入れないという選択をすることはできます。その桁については '?' として出力してください。(入力例参照)

入力

まず、最初に、以下の値が入力されます。
$Q$
$Q$ は、何回以内に答えを出さなければならないか、を表します。

また、各質問に対しての返答(入力)は、以下のようになります。
$p_0$ $p_1$ $p_2$

それぞれ、左から順に、$0$ 個の桁が合っている場所の個数、$1$ 個の桁が合っている場所の個数、$2$ 個(全部)の桁が合っている桁の個数です。
ただし、入れなかった桁($'?'$ となっている桁)は、「桁が合っていない」として数えます。

出力

質問するときは、以下のように出力してください。
$a_1$ $a_2$ ... $a_{100}$
$a_i$ は、場所 $i$ に入れる暗号を表します。暗号を入れたくない桁がある場合、その桁を $'?'$としてください。最後に改行してください。
なお、正しい数を入れた場合(全ての位置が合っている場合)、正解となり、それ以降質問する必要はありません。
また、$a_i$ は $2$ 文字である、$a_i$ の各文字は $'0'-'9'$ もしくは $'?'$ である、を両方満たすように質問をしてください。同じ暗号を何回入れてもよいです。

制約

  • ケースは全部で $36$ 個ある。
  • $6$ 個 のケースにおいて、$Q = 5500$ を満たす。
  • 別の $6$ 個 のケースにおいて、$Q = 2000$ を満たす。
  • 別の $6$ 個 のケースにおいて、$Q = 750$ を満たす。
  • 別の $6$ 個 のケースにおいて、$Q = 600$ を満たす。
  • 別の $12$ 個のケースにおいて、$Q = 450$ を満たす。
  • 全てのケースにおいて、暗号の答えはランダムに作られたものである。

注意

質問形式を間違えた場合、あるいは質問回数の上限をオーバーした場合の挙動は定義されていません。

サンプル

サンプル1

入出力の例

例えば、鍵 $1$ に隠された答え = "00", 鍵 $2$ に隠された答え = "01", 鍵 $3$ に隠された答え = "02", ... , 鍵 $100$ に隠された答え = "99" の場合:

プログラムからの入力 プログラムの出力
5500
?0 ?1 ?2 ?3 ?4 ?5 ..., ?7 ?8 ?9
0 100 0
99 98 97 96 95 94 ... 02 01 00
100 0 0
00 00 00 00 00 00 ... 00 00 00
81 18 1
01 02 03 04 05 06 ... 98 99 00
10 90 0
10 11 12 13 14 15 ... 07 08 09
0 100 0
00 01 02 03 04 05 ... 97 98 99
0 0 100

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