Find by Query

题目描述

这是一个交互式任务，你的程序与裁判通过标准输入输出进行交互。 裁判有一个长度为 $N$ 的由 $0$ 和 $1$ 组成的字符串：$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$

如果存在多个解，你可以打印其中任意一个。请在每条信息末尾打印换行并刷新标准输出。否则，你可能会得到一个 TLE 判定。 如果在交互过程中输出格式错误或你的程序过早退出，判定将是不确定的。 在打印答案后，立即退出程序。否则，判定将是不确定。 字符串 $S$ 在交互开始时固定，不会根据你的询问或其他因素改变。在下面的交互中，$N = 7$ 且 $S = 0010011$。

Input	Output	Description
$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}$。 因此，如果程序在此立即退出，该测试用例将被判定为正确通过。

标签: AtCoder|abc299D

来源

AtCoder|abc299D