27417번 - Interactive Number Guessing 다국어인터랙티브

This is an interactive problem.

Your task is to write a program that guesses a secret number through repetitive queries and responses. The secret number is a non-negative integer less than $10^{18}$.

Let $x$ be the secret number. In a query, you specify a non-negative integer $a$. In response to this, the digit sum of $(x + a)$ will be returned. Here, the digit sum of a number means the sum of all the digits in its decimal notation. For example, the digit sum of $4096$ is $4 + 0 + 9 + 6 = 19$.

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.

query $a$

Here, $a$ is an integer between $0$ and $10^{18}-1$, inclusive. In response to this query, the digit sum of $(x + a)$, where $x$ is the secret number, is sent back to the standard input, followed by a newline.

You should send your answer to the standard output in the following format, followed by a newline.

answer $y$

Here, $y$ is the secret number you have identified, an integer between $0$ and $10^{18} - 1$, inclusive.

You can send the answer only once, so you have to become sure of your guess through repeated interactions before sending the answer. However, you can send no more than $75$ queries, and thus you have to choose your queries cleverly. After sending the answer, your program should terminate without any extra output.

When your output violates any of the conditions above (invalid format, $a$ or $y$ being out of the range, too many queries, an extra output after sending your answer, and so on), your submission will be judged as a wrong answer. As some environments require flushing the output buffers, make sure that your outputs are actually sent. Otherwise, your outputs will never reach the judge.

In this example, the secret number $x$ is $75$. In response to the first query, $15$ is returned because $x + a = 75 + 3 = 78$ and its digit sum is $7 + 8 = 15$. After the second response, you can conclude that the only possible secret number is $75$.