Colors
Contest: Baltic Olympiad in Informatics 2020, Day 1 (IOI, Unofficial Mirror Contest, Unrated)
Difficulty rating: 2700
Tags: *special, binary search, constructive algorithms, interactive

Linda likes to change her hair color from time to time, and would be pleased if her boyfriend Archie would notice the difference between the previous and the new color. Archie always comments on Linda's hair color if and only if he notices a difference — so Linda always knows whether Archie has spotted the difference or not.

There is a new hair dye series in the market where all available colors are numbered by integers from $$$1$$$ to $$$N$$$ such that a smaller difference of the numerical values also means less visual difference.

Linda assumes that for these series there should be some critical color difference $$$C$$$ ($$$1 \le C \le N$$$) for which Archie will notice color difference between the current color $$$\mathrm{color}_{\mathrm{new}}$$$ and the previous color $$$\mathrm{color}_{\mathrm{prev}}$$$ if $$$\left|\mathrm{color}_{\mathrm{new}} - \mathrm{color}_{\mathrm{prev}}\right| \ge C$$$ and will not if $$$\left|\mathrm{color}_{\mathrm{new}} - \mathrm{color}_{\mathrm{prev}}\right| < C$$$.

Now she has bought $$$N$$$ sets of hair dye from the new series — one for each of the colors from $$$1$$$ to $$$N$$$, and is ready to set up an experiment. Linda will change her hair color on a regular basis and will observe Archie's reaction — whether he will notice the color change or not. Since for the proper dye each set should be used completely, each hair color can be obtained no more than once.

Before the experiment, Linda was using a dye from a different series which is not compatible with the new one, so for the clearness of the experiment Archie's reaction to the first used color is meaningless.

Her aim is to find the precise value of $$$C$$$ in a limited number of dyes. Write a program which finds the value of $$$C$$$ by experimenting with the given $$$N$$$ colors and observing Archie's reactions to color changes.

Interaction format:
This is an interactive task. In the beginning you are given a single integer $$$T$$$ ($$$1 \leq T \leq 100$$$), the number of cases in the test.

For each test case, the input first contains a single integer — the value of $$$N$$$ ($$$1 < N \le 10^{18}$$$). The value of $$$C$$$ is kept secret by the grading system.

Then your program should make queries writing output in the following format: "? $$$P$$$", where $$$P$$$ is an integer ($$$1 \le P \le N$$$) denoting the next color used. For each query the grading system gives an answer in the next line of the input. The answer is $$$1$$$ if Archie notices the color difference between the last two colors and $$$0$$$ otherwise. No two queries should have the same $$$P$$$ value.

When your program determines $$$C$$$, it should output its value in the following format: "= $$$C$$$". The grading system will not respond to this output and will proceed with the next test case.

Your program may use at most 64 queries "?" for each test case to find the correct value of $$$C$$$.

To establish proper communication between your program and the grading system, you should flush the output stream after each query.

$$$$$$\begin{array}{ll} \text{Language} & \text{Command} \\ \hline \text{C++} & \texttt{std::cout }\texttt{<}\texttt{<}\texttt{ std::endl;} \\ \text{Java} & \texttt{System.out.flush();} \\ \text{Python} & \texttt{sys.stdout.flush()} \end{array}$$$$$$ Flush commands

Note that std::endl writes a newline and flushes the stream.

It is possible to receive an "Output isn't correct" outcome even after printing a correct answer, if task constraints were violated during the communication. Violating the communication protocol itself may result in an "Execution killed" outcome.

Submitting user tests requires specifying an input file with the testcase parameters. The format of the input file is "$$$T$$$" in the first line, and then "$$$N$$$ $$$C$$$" on a single line for each of the $$$T$$$ cases.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Scoring:
Subtasks:

1. (9 points) $$$N \le 64$$$
2. (13 points) $$$N \le 125$$$
3. (21 points) $$$N \le 1000$$$
4. (24 points) $$$N \le 10^9$$$
5. (33 points) No further constraints.

Comments to the example input line by line:

1. $$$N = 7$$$.
2. Answer to the first query is meaningless (can also be $$$0$$$).
3. $$$C \leq 5$$$.
4. $$$3 < C \leq 5$$$. It would be wise to check difference $$$4$$$. However, this can not be done in the next query since $$$4 + 4 = 8$$$ and $$$4 - 4 = 0$$$ both are outside the allowed interval $$$1 \le P \le 7$$$.
5. $$$3 < C \leq 5$$$.
6. $$$3 < C \leq 4$$$. Therefore, $$$C = 4$$$.

Example input:
1

7

1

1

0

0

1

Example output:
? 2

? 7

? 4

? 1

? 5

= 4

Editorial:
Subtask 1 ($$$N \leq 64$$$)
We will use the colors in this order: $$$1$$$, $$$N$$$, $$$2$$$, $$$N-1$$$, $$$3$$$, $$$N-2$$$, $$$\ldots$$$; this way we will check each difference $$$N-1$$$, $$$N-2$$$, $$$N-3$$$, $$$N-4$$$, $$$\ldots$$$ and the answer is the first difference that is not recognized by Archie.
Complexity: $$$N$$$ queries.
Subtask 2 ($$$N \leq 125$$$)
We can first ask the colors $$$N/2$$$ and $$$1$$$. If Archie recognizes the difference, then $$$C \leq N/2$$$, and as in the Subtask 1, we can ask the queries $$$N/2-1$$$, $$$2$$$, $$$N/2-2$$$, $$$3$$$, $$$N/2-3$$$, $$$4$$$, $$$\ldots$$$, until we find the first difference that Archie does not recognize. Otherwise we ask the queries $$$N$$$, $$$2$$$, $$$N-1$$$, $$$3$$$, $$$N-2$$$, $$$\ldots$$$ until we find the first difference that Archie recognizes.
Complexity: $$$N/2+1$$$ queries.
Subtask 3 ($$$N \leq 1000$$$)
First use $$$\sqrt N$$$ values and try to understand $$$k$$$ value for which it is true that $$$C$$$ is between $$$k \sqrt N$$$ and $$$(k+1) \sqrt N$$$. For example, if $$$N = 100$$$, then use values $$$5$$$, $$$15$$$, $$$25$$$, $$$\ldots$$$, $$$95$$$ and use the Subtask 1 $$$N$$$-query algorithm to find the value of $$$k$$$. And then again use the Subtask 1 $$$N$$$-query algorithm to calculate the precise $$$C$$$ value.
Complexity: $$$2 \sqrt N$$$ queries.
Subtask 4 ($$$N \leq 10^9$$$)
Let assume that we have a correct strategy for all values of $$$N$$$ that do not exceed $$$k$$$.
If $$$k$$$ is even ($$$k = 2 j$$$) we will use the strategy that was used for $$$j$$$ numbers and use only even (or odd) numbers. This way each jump in $$$j$$$ becomes twice as long and in the result (when the strategy for $$$j$$$ has finished) we will know that the answer is $$$1$$$ or $$$2$$$, $$$3$$$ or $$$4$$$, $$$5$$$ or $$$6$$$, and so on. We then know for some $$$x$$$ that Archie recognizes the difference $$$2 x$$$ and we need to understand whether he recognizes the difference $$$2 x - 1$$$. It can be proved that if possible answers are $$$2x-1$$$ and $$$2x$$$, then the last difference that was checked was either $$$2x$$$ or $$$2x-2$$$ and in both cases we will be able to make a jump in the opposite direction with length $$$2x-1$$$.
If $$$k$$$ is odd ($$$k = 2 j + 1$$$) we use the strategy for $$$j$$$ colors and use the numbers $$$2$$$, $$$4$$$, $$$6$$$, $$$8$$$, $$$10$$$, and so on. When the strategy for $$$j$$$ is finished, we know that the answer is $$$1$$$ or $$$2$$$, $$$3$$$ or $$$4$$$, $$$5$$$ or $$$6$$$, $$$\ldots$$$, $$$2j-1$$$ or $$$2j$$$ or $$$2j+1$$$. And then in almost all cases we can calculate the answer with one additional query, but if the possible answer is one of $$$2j-1$$$, $$$2j$$$ or $$$2j+1$$$ then we need to use two additional queries.
Complexity: $$$2 \log_2 N$$$ queries.
For example, for the base cases $$$N = 3$$$ and $$$N = 4$$$ we can use the following algorithms:
Then using our construction, we get the following algorithm for $$$N = 8$$$:
Subtask 5 ($$$N \leq 10^{18}$$$) Let's assume that we have a correct strategy for all values of $$$N$$$ that do not exceed $$$k$$$. We will restrict our strategy even more – consecutive jumps need to be made in the opposite directions.
Suppose that $$$k$$$ is even ($$$k = 2 j$$$) and the first color used in the $$$j$$$ strategy is $$$f$$$. Then we make the first jump from $$$f$$$ to $$$f+j$$$ (or from $$$f+j$$$ to $$$f$$$). With this jump we will understand whether $$$C$$$ is bigger than $$$j$$$ (if the answer is negative) or smaller or equal than $$$j$$$ (if the answer is positive). If the answer is smaller or equal to $$$j$$$ then we use strategy for $$$j$$$ on numbers from $$$1$$$ to $$$j$$$ (we already have the color $$$f$$$). If the answer is bigger than $$$j$$$, then we extend all jumps in the $$$j$$$ strategy by $$$j$$$ (if we had a jump with length $$$p$$$, then now we will make jump with length $$$p + j$$$). As we are always jumping back and forth then we will never jump out of range from $$$1$$$ to $$$n$$$ and will return the answer in the range $$$j+1$$$ to $$$2j$$$. If $$$k$$$ is odd, we can use a similar strategy.
Complexity: $$$\log_2 N+1$$$ queries.
In this case, we get the following algorithm for $$$N = 8$$$: