AT_abc299_d [ABC299D] Find by Query

题目描述

本题是一个交互式问题（你的程序需要与评测程序通过标准输入输出进行交互）。

评测程序持有一个仅由 $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 翻译