問題一覧 > 通常問題

No.624 Santa Claus and The Last Dungeon

レベル : / AI推定難易度 : 2450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (AC するまで非表示) / 解いたユーザー数 9
作問者 : e869120 / テスター : 紙ぺーぱー
お気に入りにしたユーザー ProblemId : 2040 / 自分の提出
問題文最終更新日: 2018-08-23 23:20:51
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2017 (順位表) の他の問題:

Notice

Important! Only 2 days left in the Advent Calendar Contest!
Please enjoy the last 2 days!

Important Information

This problem is a reactive problem.

Story

Yukicoder tried to get a present from Santa Claus.
However, Santa Claus was a prankster, so he decided to hand over the present under the following condition.

  • There is a dungeon over there. Corner me in its last room, and if you win in that room, I will give you the present.

The battles went smoothly, and Yukicoder managed to corner Santa Claus in the last room. However...
yukicoder: "What is this... keys, there must be as many as 100 keys!?"


Opening this would mean victory, so giving up here is not an option.

Problem Statement

To open the last dungeon, you need to enter the codes of $100$ keys. The answers to the codes satisfy the following conditions.
  • The answer to every code is a $2$-digit base-$10$ integer between $00$ and $99$, inclusive.
  • The answers to all the codes are different. That is, letting $a_i$ be the $i$-th code, $a_i≠a_j$ always holds when $i≠j$.

However, it is very difficult to open the keys' codes without hints, so Santa Claus has decided to give hints as follows.
  • Santa Claus gives a hint each time yukicoder finishes entering all the codes and presses the confirm button.
  • The hint tells "the number of places with 0 matching digits", "the number of places with 1 matching digit", and "the number of places with 2 (all) matching digits".
  • Note that the confirm button can also be pressed with some digits of the codes left unentered, and the unentered digits are judged as "digits that do not match".

Here, the "number of matching digits" is defined as follows.
  • Let $A$ $=$ $a_0$$a_1$, $B$ $=$ $b_0$$b_1$ (where $A$ = the answer to the code, $B$ = the entered code).
  • The number of the conditions $a_0 = b_0$, $a_1 = b_1$, that hold is the "number of matching digits".
  • For example, $23$ and $53$ have 1 matching digit.
  • Also, $23$ and $5?$ have 0 matching digits. (Because the lower digit has not been entered.)

Yukicoder can press the confirm button up to $Q$ times. Otherwise, that door will be closed forever.
You are a warrior with excellent programming skills, fighting together with yukicoder. Enter the codes and ask questions as optimally as possible, and finally enter the correct codes to open the door.

Note that you may choose not to enter some digits of the codes at some places. Output such a digit as '?'. (See the sample.)

Input

First, the following value is given as input.
$Q$
$Q$ represents the number of questions within which you must produce the answer.

The response (input) to each question is as follows.
$p_0$ $p_1$ $p_2$

From left to right, these are the number of places with $0$ matching digits, the number of places with $1$ matching digit, and the number of places with $2$ (all) matching digits.
Here, unentered digits (digits given as $'?'$) are counted as "not matching".

Output

When asking a question, output it as follows.
$a_1$ $a_2$ ... $a_{100}$
$a_i$ represents the code entered at place $i$. If there is a digit you do not want to enter, make that digit $'?'$. Print a newline at the end.
If you enter the correct numbers (all positions match), your answer is correct and you do not need to ask any more questions.
Also, each question must satisfy both of the following: $a_i$ consists of $2$ characters, and each character of $a_i$ is $'0'-'9'$ or $'?'$. You may enter the same code any number of times.

Constraints

  • There are $36$ test cases in total.
  • In $6$ of the cases, $Q = 5500$ holds.
  • In another $6$ cases, $Q = 2000$ holds.
  • In another $6$ cases, $Q = 750$ holds.
  • In another $6$ cases, $Q = 600$ holds.
  • In another $12$ cases, $Q = 450$ holds.
  • In all cases, the answers to the codes are generated randomly.

Notes

The behavior is undefined if you use an incorrect question format or exceed the limit on the number of questions.

Sample

Sample 1

Example of Input and Output

For example, when the answer hidden in key $1$ = "00", the answer hidden in key $2$ = "01", the answer hidden in key $3$ = "02", ... , the answer hidden in key $100$ = "99":

Input to the program Output of the program
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もしくは右上の雲マークをクリックしてアカウントを作成してください。