9335: ABC299 —— D - Find by Query
[Creator : ]
Description
### 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 $N$ consisting of $0$ and $1$: $S = S_1S_2\ldots S_N$. Here, $S_1 = 0$ and $S_N = 1$.
You are given the length $N$ of $S$, but not the contents of $S$. Instead, you can ask the judge at most $20$ questions as follows.
- Choose an integer $i$ such that $1 \leq i \leq N$ and ask the value of $S_i$.
Print an integer $p$ such that $1 \leq p \leq N-1$ and $S_p \neq S_{p+1}$.
It can be shown that such $p$ always exists under the settings of this problem.
This is an interactive task, where your program and the judge interact via Standard Input and Output.
The judge has a string of length $N$ consisting of $0$ and $1$: $S = S_1S_2\ldots S_N$. Here, $S_1 = 0$ and $S_N = 1$.
You are given the length $N$ of $S$, but not the contents of $S$. Instead, you can ask the judge at most $20$ questions as follows.
- Choose an integer $i$ such that $1 \leq i \leq N$ and ask the value of $S_i$.
Print an integer $p$ such that $1 \leq p \leq N-1$ and $S_p \neq S_{p+1}$.
It can be shown that such $p$ always exists under the settings of this problem.
Input
### Input and Output
First, receive the length $N$ of the string $S$ from Standard Input:
```
$N$
```
Then, you get to ask the judge at most $20$ questions as described in the problem statement.
Print each question to Standard Output in the following format, where $i$ is an integer satisfying $1 \leq i \leq N$:
```
? $i$
```
In response to this, the value of $S_i$ will be given from Standard Input in the following format:
```
$S_i$
```
Here, $S_i$ is $0$ or $1$.
When you find an integer $p$ 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.
First, receive the length $N$ of the string $S$ from Standard Input:
```
$N$
```
Then, you get to ask the judge at most $20$ questions as described in the problem statement.
Print each question to Standard Output in the following format, where $i$ is an integer satisfying $1 \leq i \leq N$:
```
? $i$
```
In response to this, the value of $S_i$ will be given from Standard Input in the following format:
```
$S_i$
```
Here, $S_i$ is $0$ or $1$.
When you find an integer $p$ 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.
Output
### Sample Input and Output
In the following interaction, $N = 7$ and $S = 0010011$.
For the presented $p = 5$, we have $1 \leq p \leq N-1$ and $S_p \neq S_{p+1}$. Thus, if the program immediately quits here, this case will be judged as correctly solved.
In the following interaction, $N = 7$ and $S = 0010011$.
Input |
Output |
Desc |
7 |
|
$N$ is given. |
|
? 1 |
Ask the value of $S_1$. |
0 |
|
The judge responds with $S_1 = 0$. |
|
? 6 |
Ask the value of $S_6$. |
1 |
|
The judge responds with $S_6 = 1$. |
|
? 5 |
Ask the value of $S_5$. |
0 |
|
The judge responds with $S_5 = 0$. |
|
! 5 |
Present $p = 5$ as an integer satisfying the condition. |
For the presented $p = 5$, we have $1 \leq p \leq N-1$ and $S_p \neq S_{p+1}$. Thus, if the program immediately quits here, this case will be judged as correctly solved.
Constraints
### Constraints
- $2 \leq N \leq 2 \times 10^5$
- $2 \leq N \leq 2 \times 10^5$