問題一覧 > 通常問題

No.2848 Birthday Hit and Blow

レベル : / AI推定難易度 : 1725 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 21
作問者 : 👑 AngrySadEight / テスター : tko919 torisasami4
お気に入りにしたユーザー ProblemId : 11011 / 自分の提出
問題文最終更新日: 2024-07-17 02:37:48
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
yukicoder contest 441 (順位表) の他の問題:

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, and 0822, 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.
If you are not familiar with reactive problems, please also see the summary of reactive-format problems.

Sample

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