← 返回题目列表

Codeforces · 1634/D

D. 找零

中文机器翻译题面 查看原题

这是一个交互问题。

我们选择了一个整数数组 $$$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$$$ 后立即终止,你将得到一个错误的答案。否则你可能会得到任何结论,因为程序将继续从关闭的流中读取。请注意,如果查询正确,答案将永远不会是 $$$-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$$$ 查询的限制。之后,您的程序必须继续解决剩余的测试用例,或者如果所有测试用例都已解决则退出。

打印查询后,不要忘记输出换行并刷新输出缓冲区。否则,您将得到超出空闲限制的判决。要刷新缓冲区,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 阅读其他语言的文档。

黑客

第一行必须包含一个整数 $$$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

1

4

2

3

3

2

输出 #1

? 1 2 3

? 2 3 4

? 3 4 1

? 4 1 2

! 2 3

注意

样本数组:$$$[1, 2, 0, 3]$$$。