P16457 [UOI 2026] Guess the Number

An integer $n$ is hidden ($1 \le n < 10^8$), and it is not divisible by $10$. Your task is to find this number. You may ask queries of the following form: choose an integer $x$ ($1 \le x \le 10^9$). In response, you will receive the first digit of the number $n \cdot x$. The first digit of a positive integer is its most significant digit in decimal notation. For example, the first digit of the numbers $7$, $42$, $123456$ is respectively $7$, $4$, $1$. You need to find the hidden number $n$. You can use at most $28$ queries for each testcase.

The first line contains two integers $t$ and $q$ ($1 \le t \le 10^3, q=28$) --- the number of testcases and the maximum number of queries that can be used in each testcase. ### Interaction In each testcase, a separate number $n$ is hidden. To make a query, print $$\texttt{? } x$$, where $1 \le x \le 10^9$. In response to a query, the jury program will print one integer $d$ ($1 \le d \le 9$) --- the first digit of the number $n \cdot x$. After printing a query, do not forget to print a newline and flush the output buffer. Otherwise, you will receive the verdict $\tt{Time limit exceeded}$. To flush the buffer, use: - $\tt{fflush(stdout)}$ or $\tt{cout.flush()}$ in C++; - $\tt{System.out.flush()}$ in Java; - $\tt{flush(output)}$ in Pascal; - $\tt{stdout.flush()}$ in Python. When you have determined the hidden number $n$, print $$\texttt{! } n$$. After that, if this was the last testcase, you must terminate your program. Otherwise, you should continue the interaction with the next testcase. $q$ is the maximum number of $\texttt{?}$ queries that your program may use in one testcase. Printing an answer of the form $\texttt{!}$ does not count as a query. Note that if your query is invalid, the interactor will print $\texttt{-1}$ and terminate. A query is considered invalid if: - $x$ does not satisfy the constraint $1 \le x \le 10^9$; - the number of queries in the current testcase exceeded $q$; - the answer $\texttt{! } n$ is incorrect. If you read $\texttt{-1}$, immediately terminate your program to receive the verdict $\tt{Wrong answer}$ instead of an arbitrary verdict.

N/A

Consider the example. Suppose that in this example it is additionally known that the hidden number is less than $100$. After the query $x = 1$ and the answer $1$, we understand that the first digit of the hidden number is $1$. After the query $x = 59$ and the answer $6$, we understand that the first digit of the product of the hidden number and $59$ is $6$. Among all numbers less than $100$ that are not divisible by $10$, only the number $11$ satisfies both conditions. Therefore, the answer in the example is $11$. ### Scoring - ($2$ points): $n \le 10$; - ($6$ points): $n \le 100$; - ($7$ points): $n \le 1000$; - ($8$ points): $n \le 10000$; - ($10$ points): $n$ is a perfect square; - ($10$ points): $n \le 10^5$; - ($11$ points): $n \le 10^6$; - ($12$ points): $n \le 10^7$; - ($14$ points): $n \le 5 \cdot 10^7$; - ($20$ points): no additional constraints. A solution passes a subtask only if it correctly finds the number $n$ for every testcase of that subtask, using no more than $q$ queries in each one.