CF1634D Finding Zero

本题为交互题。 我们选取了一个整数数组 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），并且在其中恰好隐藏了一个零！你的目标是找出这个零的位置，即找到 $i$ 使得 $a_i = 0$。 你可以通过多次询问来猜测答案。每次询问，你可以选择三个不同的下标 $i, j, k$，我们会告诉你 $\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)$ 的值。换句话说，我们会告诉你 $a_i, a_j, a_k$ 中最大值与最小值的差。 你最多可以进行 $2 \cdot n - 2$ 次询问，之后你有两次机会猜测零的位置。也就是说，你需要给出两个数 $i$ 和 $j$，只要 $a_i = 0$ 或 $a_j = 0$，你就算猜对了。 你能猜出我们把零藏在哪里吗？ 注意，每个测试用例中的数组在游戏开始前就已经固定，并且在游戏过程中不会改变。换句话说，交互器不是自适应的。

每个测试点包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 500$）。每个测试用例的描述如下。 每个测试用例的第一行包含一个整数 $n$（$4 \le n \le 1000$），表示我们选取的数组长度。 保证所有测试用例中 $n$ 的总和不超过 $3000$。

对于每个测试用例，交互从读取 $n$ 开始。 每次询问时，输出 "? $i$ $j$ $k$"（不含引号，$1 \le i, j, k \le n$，下标必须互不相同）。然后你需要从标准输入读取我们的回应，即 $\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)$。 如果回应为 $-1$，说明你的程序进行了非法询问或已用尽所有机会。你的程序必须在读取到 $-1$ 后立即终止，否则会被判为 Wrong answer。否则你可能会得到其它判定，因为程序会继续从已关闭的流中读取。注意，如果询问合法，答案绝不会是 $-1$，因为 $\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k) \geq 0$。 给出最终答案时，输出 "! $i$ $j$"（不含引号）。允许输出相同的数字两次（即 $i = j$）。注意，给出答案不计入 $2 \cdot n - 2$ 次询问的限制。之后，你的程序应继续解决剩余的测试用例，或在全部测试用例解决后退出。 每次输出询问后，不要忘记输出换行并刷新输出缓冲区，否则会被判为 Idleness limit exceeded。刷新缓冲区的方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hacks 第一行必须包含一个整数 $t$（$1 \le t \le 500$），表示测试用例数量。 每个测试用例的第一行必须包含一个整数 $n$（$4 \le n \le 1000$），表示隐藏数组的长度。 每个测试用例的第二行必须包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），且数组中恰好有一个零。 所有测试用例中 $n$ 的总和不超过 $3000$。

样例数组为 $[1, 2, 0, 3]$。 由 ChatGPT 4.1 翻译