P15749 [JAG 2024 Summer Camp #3] Interactive String Guessing

This is an interactive problem. Your task is to write a program that guesses a secret string through repetitive queries and responses. The secret string consists of **a** and **b**, and its length is between $1$ and $1,000$. Let $\mathbf{S}$ be the secret string. In a query, you specify a string $\mathbf{T}$. In response to this, whether $\mathbf{T}$ is a substring of $\mathbf{S}$ or not will be returned. Here, $\mathbf{T}$ is said to be a substring of $\mathbf{S}$ when some contiguous part of $\mathbf{S}$ matches $\mathbf{T}$. For example, **aba** is a substring of **babab** and **aba** but not of **abba**. You can make up to $1,100$ queries. ### Interaction You should start with sending a query to the standard output and receiving the response from the standard input. This interaction can be repeated a number of times. When you have become confident of your guess through these interactions, you can send your answer. A query should be in the following format, followed by a newline. $$\begin{aligned} &? \ T \end{aligned}$$ Here, $\mathbf{T}$ is a non-empty string consisting of **a** and **b**, and its length is between $1$ and $1,000$, inclusive. The response to the query is given from the standard input in the following format followed by a newline. $$\begin{aligned} &R \end{aligned}$$ Here, $\mathbf{R}$ denotes the response to the query. $\mathbf{R}$ is **Yes** when $\mathbf{T}$ is a substring of the secret string $\mathbf{S}$, and $\mathbf{R}$ is **No** when $\mathbf{T}$ is not a substring of the secret string $\mathbf{S}$. However, if $\mathbf{T}$ does not satisfy the constraints, or the number of queries exceeds the limit, then $\mathbf{R}$ is **Invalid**. If the judge returns **Invalid**, your program is already considered incorrect, so terminate the program immediately. You should send your answer to the standard output in the following format, followed by a newline. $$\begin{aligned} &! \ T \end{aligned}$$ Here, $\mathbf{T}$ is the secret string you have identified, its length is between $1$ and $1,000$, inclusive. You can send the answer only once, so you have to become sure of your guess through repeated interactions before sending the answer. After sending the answer, your program should terminate without any extra output. ### Notes on interactive judging The verdict will be indeterminate if there is malformed output during the interaction or your program quits prematurely. Terminate the program immediately after printing the answer, or the verdict will be indeterminate. As some environments require flushing the output buffers, make sure that your outputs are actually sent. Otherwise, your outputs will never reach the judge. The string $\mathbf{S}$ will be fixed before the first interaction and will not be changed according to your questions or other factors.

N/A

N/A