P6682 [BalticOI 2020] Coloring (Day1)

Linda likes to change her hair color from time to time. If her boyfriend Archie notices that her hair color has changed, Linda will be very happy. Archie will comment on Linda’s new hair color if and only if he notices that Linda’s hair color has changed. This means Linda can always know whether Archie noticed a change in her hair color. Now there is a new series of hair dyes on the market. This series has $N$ colors, numbered from $1$ to $N$. How close two colors are depends on the difference of their numbers: the smaller the difference, the closer they are. Linda finds that for this series of hair dyes, there exists a color-difference threshold $C$ ($1 \leq C \leq N$). Specifically, suppose the color number Linda used before is $color_{prew}$, and the color number she plans to use next is $color_{new}$. Then Archie will notice the difference in Linda’s hair color if and only if $\left | color_{new}-color_{prew}\right | \geq C$. Now Linda buys a whole set of this series of hair dyes and plans to do an experiment. She will keep changing her hair color and observe whether Archie notices that the hair color has changed. Since the amount of dye is limited, each color can be used at most once. Before the experiment starts, Linda is using a different series of hair dyes, so it is meaningless to discuss Archie’s reaction after the first dyeing. Now Linda wants to find the threshold $C$ within limited time. Please write a program to help her complete this task. ### Interaction This is an interactive problem. **Different from the original problem, in order to reduce the number of test groups, a single test point will contain multiple test cases.** The first line of input contains an integer $T$, the number of test cases in this test point. For each test case, you will first read an integer $N$, the number of colors in this dye series. Then you may output queries in the following form: `? P`, where $P$ is the color number of the dye Linda will use next. The $P$ you output must satisfy $1 \leq P \leq N$, and the values of $P$ in any two queries must be different. After a query, your program will read an integer. If this integer is $1$, it means Archie noticed the change in Linda’s hair color; if it is $0$, it means he did not notice the change. When you have determined the threshold $C$, output the answer in the following form: `= C`. If the answer is correct, the interaction will immediately proceed to the next test case. If the answer is wrong, the interactor will terminate your program immediately. For each test case, your program may make at most $64$ queries (the final answer output does not count as a query). Please note that in general, your output is stored in a buffer. To ensure your output can be received by the interactive library, flush the buffer after printing each line. - For C++, you can use `std::cout

N/A

N/A

### Sample Explanation To make the interaction process easier to understand, some blank lines are manually added between certain lines. The process of each query is explained below: 1. The result of this query is meaningless. 2. After this query, we have $C \leq 5$. 3. After this query, we have $3 \lt C \leq 5$. At this point, we may consider checking the case where the difference is $4$. But since $4+4=8$ and $4-4=0$ are both invalid, we no longer consider doing this. 4. After this query, we have $3 \lt C \leq 5$. 5. After this query, we have $3 \lt C \leq 4$, that is, $C=4$. ### Subtasks All testdata satisfy: $1 \leq T \leq 1200$, $1 < N \leq 10^{18}$. - Subtask 1 (9 points): $N \leq 64$. - Subtask 2 (13 points): $N \leq 125$. - Subtask 3 (21 points): $N \leq 10^3$. - Subtask 4 (24 points): $N \leq 10^9$. - Subtask 5 (33 points): no special restrictions. Translated by ChatGPT 5