No.624 Santa Claus and The Last Dungeon
問題文最終更新日: 2018-08-23 23:20:51
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
e869120
紙ぺーぱー