Description

The judge will choose an integer in the range $[1,10^9]$. You should write a program to guess it. You may ask at most $50$ questions.

For each query, you may ask the judge about one integer in $[1,10^9]$. The judge returns:

• $0$, if it is the answer (i.e., the number chosen by the judge), after which the program must stop querying.
• $-1$, if it is less than the answer.
• $1$, if it is greater than the answer.

For each query, you must print to standard output an integer in $[1,10^9]$, then print a newline and flush the output buffer.

You can flush the buffer using:

• For C/C++: fflush(stdout).
• For C++: std::cout << std::flush.
• For Java: System.out.flush().
• For Python: stdout.flush().
• For Pascal: flush(output).
• For other languages, please refer to the corresponding documentation.

In particular, for C++, if you use std::endl instead of '\n' when printing a newline, the buffer will also be flushed automatically. It is recommended to use std::endl to avoid forgetting the newline.

Then you need to read an integer from standard input, which represents the judge’s response.

Output Format

Hint

Constraints

Let $n$ be the answer.

• For $50\%$ of the testdata, it is guaranteed that $n \leq 51$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^9$.

Interactive library for this problem.

Hint

Constraints

Let $n$ be the answer.

• For $50\%$ of the testdata, it is guaranteed that $n \leq 51$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^9$.

Interactive library for this problem.

Hint

Reference program for this problem:

#include <cstdio>
#include <iostream>

int main() {
  for (int l = 1, r = 1000000000, mid = (l + r) >> 1, res; l <= r; mid = (l + r) >> 1) {
    std::cout << mid << std::endl;
    std::cin >> res;
    if (res == 0) {
      return 0;
    } else if (res == -1) {
      l = mid + 1;
    } else if (res == 1) {
      r = mid - 1;
    } else {
      puts("OvO, I AK IOI"); // this statement will never be executed.
    }
  }
  return 0;
}

Translated by ChatGPT 5