102993: [Atcoder]ABC299 D - Find by Query
Description
Score : $400$ 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 $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.
Constraints
- $2 \leq N \leq 2 \times 10^5$
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.
Notes
- Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE
Input
题意翻译
## 简述题意 - 交互库内有一个长度为 $n$ 的 $01$ 串 $S=S_1S_2S_3\ldots S_n$，其中 $S_1=0$，$S_n=1$。 - 最多询问交互库 $20$ 个问题，每次询问一个数 $x$，交互库返回 $S_x$ 的值。 - 目标寻找到一个数 $id$ ，使得 $S_{id}\neq S_{id+1}$。 - $1\leq n \leq 2e5$。 ## 交互格式 具体地，交互库会先给出一个数 $n$。 若询问交互库 $S_x$ 的值，应当以 $\verb|? x|$ 的格式进行询问，交互库会给出 $S_x$ 的值。 若给出答案 $id$，应当以 $\verb|! id|$ 的格式给出答案，若 $S_{id}\neq S_{id+1}$ 则获得该测试点分数。你不应该在此之后输出任何字符。 Translated by [yujinning](https://www.luogu.com.cn/user/601224)。Output
题目描述
这是一个交互式任务，你的程序需要通过标准输入和输出与裁判交互。
裁判有一个由0和1组成的长度为$N$的字符串$S$：$S = S_1S_2\ldots S_N$。其中，$S_1 = 0$且$S_N = 1$。
你将获得字符串$S$的长度$N$，但不会获得$S$的内容。取而代之的是，你最多可以向裁判提出以下20个问题。
- 选择一个满足$1 \leq i \leq N$的整数$i$，并询问$S_i$的值。
打印一个整数$p$，满足$1 \leq p \leq N-1$且$S_p \neq S_{p+1}$。
可以证明，在本题的设置下，这样的$p$总是存在的。
限制条件
- $2 \leq N \leq 2 \times 10^5$
输入和输出
首先，从标准输入接收字符串$S$的长度$N$：
$N$
然后，你可以按照题目描述中所述，向裁判提出最多20个问题。
将每个问题打印到标准输出，格式如下，其中$i$是满足$1 \leq i \leq N$的整数：
? $i$
对此，裁判将从标准输入给出以下格式的$S_i$的值：
$S_i$
其中，$S_i$为0或1。
当你找到满足题目描述中条件的整数$p$时，按照以下格式打印它，并立即退出程序：
! $p$
如果有多个解决方案，你可以打印其中的任何一个。
注意事项
- 在每个消息的末尾打印一个换行符并刷新标准输出。否则，你可能会得到一个