P14843 [ICPC 2022 Yokohama R] 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$. ### Interaction 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. $$\text{query} \quad 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. $$\text{answer} \quad 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. ### Notes on interactive judging 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.

N/A

N/A

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$.