No.3212 SUPER Guess the Number
Credits
The original idea for this problem was provided by chikuwa.
Problem Statement
This is an interactive problem (a problem in which your program and the judge program interact via standard input and output).
The judge has a hidden integer between $1$ and $10^6$, inclusive. Determine what it is using at most $25$ queries.
In the $i$-th $(1\le i \le 25)$ query, you output to the judge an integer $x_i$ satisfying $|x_i| \le 10^9$. In response, the judge answers as follows.
- If $i=1$, the judge gives no answer. If $i\ge 2$, letting $a$ be the judge's hidden value, the judge answers whether $|a-x_{i-1}| \ge |a-x_i|$ holds.
Input and Output
This is an interactive problem (a problem in which your program and the judge program interact via standard input and output).
Initially, no input is given.
You may make $25$ queries. The $i$-th query is made by outputting an integer $x_i$ satisfying $|x_i| \le 10^9$ in the following format. Print a newline at the end and flush standard output.
? $x_i$
Immediately after the $i$-th query, the judge acts as follows.
- If the output is invalid or $i > 25$:
The judge gives the following input to your program. At this point, the judge has already regarded the submission as WA. If you receive this, it is recommended that you terminate your program immediately.
-1
- Otherwise, if $i=1$:
The judge does not give any value as input. Be careful of deadlocks caused by your program mistakenly trying to read input.
- If neither of the above applies, that is, if the output is valid and $2\le i\le 25$:
If $|a-x_{i-1}| \ge |a-x_i|$, the following value is given as input.
1
Otherwise, the following value is given as input.
0
Once the queries have revealed the judge's hidden value, output it in the following format, where $a$ is the hidden value. (This output is not counted as a query.)
Also, print a newline immediately after the output and flush standard output.
! $a$
After that, terminate your program immediately. Then, if the output $a$ is correct as the judge's hidden value, the verdict is AC.
Notes
- Each time you output something, add a newline at the end and flush standard output. Otherwise, the verdict may be TLE.
- If your program produces invalid output during the interaction or terminates midway, the verdict is undefined. In particular, note that if a runtime error occurs during the execution of your program, the verdict may be WA or TLE instead of RE.
- Terminate your program immediately after outputting $a$. Otherwise, the verdict is undefined.
- The judge may be adaptive. That is, depending on your program's output, the judge may change its hidden value as long as it does not contradict the previous queries.
Sample Interaction
In this sample interaction, assume that the judge's hidden value is initially $7$.
| Input from the judge | Output by the program | Explanation |
|---|---|---|
? 4 | Query the judge with $x_1 = 4$. | |
? 10 | Query the judge with $x_2 = 10$. | |
1 | $|a-x_1| = |7-4| = 3,|a-x_2| = |7-10| = 3$. That is, $|a-x_1| \ge |a-x_2|$ holds, so the judge gives $1$ as the answer to the query. | |
? -5 | Query the judge with $x=-5$. | |
0 | $|a-x_2| = |7-10| = 3,|a-x_3| = |7-(-5)| = 12$. That is, $|a-x_2| \ge |a-x_3|$ does not hold, so the judge gives $0$ as the answer to the query. | |
! 7 | Answer the judge that $a=7$. |
The final answer $a=7$ is correct, but $a=9$, for example, would also not contradict the answers to the queries so far.
Therefore, immediately after the program answers $a=7$, the judge may change the value to $a=9$ and make the verdict WA.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Cafe1942