Background

Translated from ROI 2019 D1T4.

This is an interactive IO problem.

Scientists plan to measure the radiation level of a series of black holes. A black hole’s radiation level is represented by an integer from $1$ to $n$. To measure each black hole’s radiation level, a special orbital probe equipped with a radiation sensor is used. The sensor mounted on the probe can answer the following query: given a value $x$, determine whether the radiation level is greater than or equal to $x$. Unfortunately, due to a software bug, the sensor’s reply may be incorrect. However, after the first incorrect reply, the probe’s state changes, and for all subsequent queries it gives only correct replies.

The scientists want to determine the radiation level of several black holes by asking the probe as few queries as possible.

Problem Description

Write a program that interacts with the simulation library of the probe sensor and determines the radiation level of each black hole.

For each run of the solution program, you must solve the problem for multiple black holes with the same $n$ (that is, you need to determine the radiation levels of multiple black holes, and each radiation level is between $1$ and $n$). The number of black holes in each run is at most $100$.

For each test, the interactive library stores a value $q$, the maximum number of queries allowed for one black hole. It is guaranteed that no matter how the interactive library chooses to answer, $q$ queries are enough to solve the problem. This number will not be given to your program. If your program performs more than $q$ queries for a black hole, the test will receive WA.

Note: In the WA case described above, the test may appear as TLE, possibly because the interactive library has already terminated and returned, but the program is still waiting for a reply to that query. When TLE happens, you can check the detailed information returned for that test to confirm whether it is a real timeout or caused by exceeding the query limit.

Input Format

First, read an integer $n$, the maximum possible radiation level of a black hole. This number is the same for all black holes in this run. After reading $n$, your program should interact with the library and gradually determine the radiation level of one or more black holes.

After outputting your answer for one black hole’s radiation level, the program should read one more line. If you need to continue studying the next black hole, the string read from the library will be Correct; if all black holes have been finished, the string will be Done.

Output Format

To make a query, the program must output a string in the format ? x, where $x$ is a positive integer. As a reply, the interactive library will give your program a string, either Yes (if the sensor’s reply is not wrong, it means the black hole’s radiation level is greater than or equal to $x$), or No (if the sensor’s reply is not wrong, it means the black hole’s radiation level is less than $x$).

If your program determines the answer, it should output a line ! x, where $x$ is the radiation level of the black hole you found. This answer is considered correct if $x$ is the only radiation level value that contradicts no more than one reply from the interactive library. If an incorrect answer is given, the program will be terminated immediately, and the result of that test will become WA.

2

Yes

No

Yes

Correct

No

No

Done

? 2

? 2

? 2

! 2

? 2

? 2

! 1

3

Yes

Yes

No

Yes

No

Done

? 2

? 2

? 3

? 3

? 3

! 2

Hint

Sample explanation:

In the first example, for the first black hole, after the first two queries it is unknown which one of the sensor’s answers is wrong, so a third query is needed.

In the second example, one possible interaction for $n = 3$ is shown, where the program can find the answer within $5$ queries. It can be proven that the answer cannot be determined within $4$ queries.

In both examples, the interactive library sets $q=30$, and clearly neither example exceeds the limit.

Please note that the interactive library may give different answers even if your program outputs exactly the same queries as in the samples.

Constraints:

For $100\%$ of the data, $n\le30000$. In each test, the value of $q$ is guaranteed to be sufficient to solve the problem, no matter how the interactive library answers.

It is guaranteed that after each answer given by the interactive library, there always exists a radiation level value that satisfies all previous query answers (except the one wrong answer). The interactive library may adjust its behavior, including choosing which known answer is wrong, and determining the radiation level of the black hole being studied based on the queries asked by the solution program.

Translated by ChatGPT 5