問題一覧 > 通常問題

No.3212 SUPER Guess the Number

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 55
作問者 : yuusaan / テスター : 👑 loop0919 lif4635 Cafe1942
お気に入りにしたユーザー ProblemId : 12257 / 自分の提出
問題文最終更新日: 2025-07-25 21:11:33
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 475 (ゆるCafe) (順位表) の他の問題:

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
? 4Query the judge with $x_1 = 4$.
? 10Query 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.
? -5Query 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.
! 7Answer 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もしくは右上の雲マークをクリックしてアカウントを作成してください。