No.2848 Birthday Hit and Blow
タグ : / 解いたユーザー数 21
作問者 : 👑
tko919
torisasami4
Problem Statement
This is an interactive problem (a problem in which your program and the judge program interact through standard input and output).
The MMDD format is a way of representing a date, consisting of a month and a day, as a string of $4$ digit characters in the following manner.
- Write the $2$-digit number representing the month followed by the $2$-digit number representing the day, in this order, and regard the result as a string of $4$ digit characters.
- If the number representing the month or the day has only $1$ digit, add a $0$ in front of it.
- For example, month $1$ day $2$, month $12$ day $13$, and month $8$ day $22$ are represented in MMDD format as
0102,1213, and0822, respectively.
Alice wants to give a birthday present to her friend Bob.
Alice knows that in Bob's birthday, "the digits in the MMDD format are pairwise distinct", but she does not know his exact birthday, so she does not know when to give the present.
Alice therefore decided to ask Bob for his birthday. However, Bob will not tell her his birthday directly. So she decided to try to determine it by asking the following kind of question.
- Tell Bob a string $S_Q$ of $4$ digit characters whose digits are pairwise distinct. Letting $S_A$ be the MMDD format of Bob's birthday, Bob then tells her each of the following values.
- $H$, the number of digits that appear in both $S_Q$ and $S_A$ at the same position. Specifically, the number of integers $i(1 \leq i \leq 4)$ such that the $i$-th character of $S_Q$ and the $i$-th character of $S_A$ are equal.
- $B$, the number of digits that appear in both $S_Q$ and $S_A$ but at different positions. Specifically, the number of integer pairs $(i, j)(1 \leq i, j \leq 4)$ such that the $i$-th character of $S_Q$ and the $j$-th character of $S_A$ are equal and $i \neq j$ holds.
- Note the following.
- It is guaranteed that the digits of $S_A$ are pairwise distinct.
- $S_A$ is the MMDD format of a date that exists in the Gregorian calendar, but $S_Q$ does not need to be the MMDD format of a date that exists in the Gregorian calendar.
However, because Bob would feel awkward, he will answer at most $6$ questions.
Taking the role of Alice, determine Bob's birthday by asking him at most $6$ questions.
Note that $S_A$ is determined before the interaction between your program and the judge system begins.
You are given $T$ test cases; solve each of them.
What is a date that exists in the Gregorian calendar?
A date that exists in the Gregorian calendar is a date expressed as "month $i$, day $j$" with $1 \leq i \leq 12$ and $1 \leq j \leq d_j$, for $d = (31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)$.
Constraints
- $T$ is an integer.
- $1 \leq T \leq 200$
- $S_A$ is the MMDD format of a date that exists in the Gregorian calendar.
- The digits of $S_A$ are pairwise distinct.
Input and Output
This is an interactive problem (a problem in which your program and the judge program interact through standard input and output).
Your program takes the role of Alice, and the judge program takes the role of Bob.
First, the number of test cases $T$ is given.
$T$
Then, $T$ test cases follow.
To ask Bob a question, output in the following format. Here, $S_Q$ must be a string of $4$ digit characters whose digits are pairwise distinct.
? $S_Q$
The response to this question is given from standard input in the following format.
$H$ $B$
Here, $H$ represents the number of digits that appear in both $S_Q$ and $S_A$ at the same position, and $B$ represents the number of digits that appear in both $S_Q$ and $S_A$ but at different positions.
If you make an input that violates the constraints, or if the number of questions exceeds $6$, then $H = -1, B = -1$ is given as input. In this case, your submission has already been judged as incorrect, so terminate your program immediately.
To answer with Bob's birthday, output in the following format. Here, $S_A$ is the $4$-character string representing Bob's birthday in MMDD format.
! $S_A$
After that, a value $a$ representing the result of that answer is given from standard input in the following format.
$a$
If you output Bob's birthday correctly, $a = 0$ is given as input. In this case, continue processing the next test case if there is one; otherwise, terminate your program immediately.
If your output is not correct, $a = -1$ is given as input. In this case as well, your submission has already been judged as incorrect, so terminate your program immediately.
Notes
- Be sure to flush standard output after every output. Otherwise, you may get TLE.
- If an invalid output is made, the judge result is undefined.
- If your program does not terminate immediately after $H = -1, B = -1$ or $a = -1$ is given as input, the judge result is undefined.
- After answering all test cases, terminate your program immediately. Otherwise, the judge result is undefined.
- The output answering Bob's birthday is not counted toward the number of questions.
Sample
| Input | Output | Explanation |
|---|---|---|
1 |
$T = 1$. | |
? 1234 |
Ask a question with $S_Q = $ 1234. Month $12$ day $34$ is a date that does not exist, but such a question is allowed. |
|
0 2 |
For $S_Q = $ 1234, the result was $H = 0, B = 2$. |
|
? 9810 |
Ask a question with $S_Q = $ 9810. |
|
1 1 |
For $S_Q = $ 9810, the result was $H = 1, B = 1$. |
|
? 0123 |
Ask a question with $S_Q = $ 0123. |
|
3 0 |
For $S_Q = $ 0123, the result was $H = 3, B = 0$. |
|
! 0823 |
From the information so far, we know that $S_A = $ 0823, so we answer with it. This output is not counted toward the number of questions. |
|
0 |
Since $a = 0$ is given as input, the answer was correct. All test cases have been answered, so the program terminates here. |
The following figure illustrates this sequence of steps.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。