AT_abc299_d [ABC299D] Find by Query

[problemUrl]: https://atcoder.jp/contests/abc299/tasks/abc299_d 本题是一个**交互式问题**（你的程序需要与评测程序通过标准输入输出进行交互）。 评测程序持有一个仅由 $0$ 和 $1$ 组成、长度为 $N$ 的字符串 $S = S_1S_2\ldots S_N$。字符串 $S$ 满足 $S_1 = 0$ 且 $S_N = 1$。 你只会得到 $S$ 的长度 $N$，但不会直接得到 $S$ 本身。作为替代，你可以最多向评测程序询问 $20$ 次以下问题： - 选择一个满足 $1 \leq i \leq N$ 的整数 $i$，询问 $S_i$ 的值。 请输出一个满足 $1 \leq p \leq N-1$ 且 $S_p \neq S_{p+1}$ 的整数 $p$。 在本题的条件下，保证一定存在这样的整数 $p$。

首先，从标准输入读取字符串 $S$ 的长度 $N$。 > $N$ 接下来，你可以最多进行 $20$ 次如题目描述中的询问。 每次询问，请按照以下格式输出到标准输出。这里 $i$ 是满足 $1 \leq i \leq N$ 的整数。 > ? $i$ 对于每次询问，评测程序会以如下格式返回 $S_i$ 的值： > $S_i$ 其中 $S_i$ 是 $0$ 或 $1$。 当你找到满足条件的整数 $p$ 后，请按照以下格式输出答案，并立即结束程序。 > ! $p$ 如果有多个满足条件的 $p$，输出任意一个都视为正确。

见上文。

### 限制条件 - $2 \leq N \leq 2 \times 10^5$ ### 注意事项 - **每次输出后请在末尾加上换行符并刷新标准输出，否则可能会被判定为 TLE。** - **如果在交互过程中输出了非法内容，或程序中途退出，评测结果将不可预测。** - 输出答案后请立即结束程序，否则评测结果不可预测。 - 字符串 $S$ 在你与评测程序交互开始时已固定，不会因你的询问而改变。 ### 输入输出样例 以下是 $N = 7, S = 0010011$ 时的输入输出示例。 输入 输出 说明 7 $N$ 的值。 ? 1 向评测程序询问 $S_1$ 的值。 0 评测程序返回 $S_1 = 0$。 ? 6 向评测程序询问 $S_6$ 的值。 1 评测程序返回 $S_6 = 1$。 ? 5 向评测程序询问 $S_5$ 的值。 0 评测程序返回 $S_5 = 0$。 ! 5 输出满足条件的整数 $p = 5$ 作为答案。 对于你输出的 $p = 5$，有 $1 \leq p \leq N-1$ 且 $S_p \neq S_{p+1}$。因此，立即结束程序即可被判定为正确。 由 ChatGPT 4.1 翻译