atcoder#ABC299D. [ABC299D] Find by Query

[ABC299D] Find by Query

Score : 400400 points

Problem Statement

This is an interactive task, where your program and the judge interact via Standard Input and Output.

The judge has a string of length NN consisting of 00 and 11: S=S1S2SNS = S_1S_2\ldots S_N. Here, S1=0S_1 = 0 and SN=1S_N = 1.

You are given the length NN of SS, but not the contents of SS. Instead, you can ask the judge at most 2020 questions as follows.

  • Choose an integer ii such that 1iN1 \leq i \leq N and ask the value of SiS_i.

Print an integer pp such that 1pN11 \leq p \leq N-1 and SpSp+1S_p \neq S_{p+1}. It can be shown that such pp always exists under the settings of this problem.

Constraints

  • 2N2×1052 \leq N \leq 2 \times 10^5

Input and Output

First, receive the length NN of the string SS from Standard Input:

N

Then, you get to ask the judge at most 2020 questions as described in the problem statement.

Print each question to Standard Output in the following format, where ii is an integer satisfying 1iN1 \leq i \leq N:

? i

In response to this, the value of SiS_i will be given from Standard Input in the following format:

S_i

Here, SiS_i is 00 or 11.

When you find an integer pp satisfying the condition in the problem statement, print it in the following format, and immediately quit the program:

! p

If multiple solutions exist, you may print any of them.

Notes

  • Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE verdict.
  • If there is malformed output during the interaction or your program quits prematurely, the verdict will be indeterminate.
  • After printing the answer, immediately quit the program. Otherwise, the verdict will be indeterminate.
  • The string SS will be fixed at the start of the interaction and will not be changed according to your questions or other factors.

Sample Input and Output

In the following interaction, N=7N = 7 and S=0010011S = 0010011.

Input Output Description
7 NN is given.
? 1 Ask the value of S1S_1.
0 The judge responds with S1=0S_1 = 0.
? 6 Ask the value of S6S_6.
1 The judge responds with S6=1S_6 = 1.
? 5 Ask the value of S5S_5.
0 The judge responds with S5=0S_5 = 0.
! 5 Present p=5p = 5 as an integer satisfying the condition.

For the presented p=5p = 5, we have 1pN11 \leq p \leq N-1 and SpSp+1S_p \neq S_{p+1}. Thus, if the program immediately quits here, this case will be judged as correctly solved.