loj#P3332. 「BalticOI 2020」色彩

「BalticOI 2020」色彩

Description

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 11 to NN 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(1CN)C (1 \le C \le N) for which Archie will notice color difference between the current color colornew and the previous color colorprev if $|{\rm color}_{\rm new} − {\rm color}_{\rm prev}| \ge C$ and will not if $|{\rm color}_{\rm new} − {\rm color}_{\rm prev}| < C$.

Now she has bought N sets of hair dye from the new series—one for each of the colors from 11 to NN, 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 CC in a limited number of dyes. Write a program which finds the value of CC by experimenting with the given NN colors and observing Archie’s reactions to color changes.

Communication

This is an interactive task. At the beginning the input contains a single integer—the value of N(1<N1018)N (1 < N \le 10^{18}). The value of CC is kept secret by the grading system.

Then your program should make queries writing output in the following format: “? P\texttt{?}\ P”, where PP is an integer (1PN)(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 11 if Archie notices the color difference between the last two colors and 00 otherwise. No two queries should have the same PP value.

When your program determines CC, it should output its value in the following format: “= C\texttt{=}\ C” and stop the execution. The grading system will not respond to this output and will not accept further queries.

Notes

To establish proper communication between your program and the grading system, you should flush the output stream after each query (As the following table shows).

Language Command
C++ std::cout << std::endl;\texttt{std::cout << std::endl;}
Java System.out.flush();\texttt{System.out.flush();}
Python sys.stdout.flush()\texttt{sys.stdout.flush()}

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 “N CN\ C” on a single line.

Example

Input Output Comments
7\texttt{7} N=7N=7
? 2\texttt{? 2}
1\texttt{1} Answer to the first query is meaningless (can also be 0\texttt{0})
? 7\texttt{? 7}
1\texttt{1} C5C \le 5
? 4\texttt{? 4}
0\texttt{0} 3<C53 < C \le 5^*
? 1\texttt{? 1}
0\texttt{0} 3<C53 < C \le 5
? 5\texttt{? 5}
1\texttt{1} 3<C43 < C \le 4. Therefore, C=4C=4.
= 4\texttt{= 4}

^*It would be wise to check difference 44. However, this can not be done in the next query since 4+4=84 + 4 = 8 and 44=04 − 4 = 0 both are outside the allowed interval 1P71 \le P \le 7.

Grading

Your program may use at most 64 queries “?\texttt{?}” to find the correct value of CC.

Subtasks:

  1. (99 points) N64N \le 64
  2. (1313 points) N125N \le 125
  3. (2121 points) N1000N \le 1000
  4. (2424 points) N109N \le 10^9
  5. (3333 points) No further constraints