← 返回题目列表

Codeforces · 1807/E

E. 采访

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

这是一个交互问题。如果您不确定交互式问题如何运作,建议您阅读参与者指南。

最后一阶段考试前,主任进行了面试。他给了小杰 $$$n$$$ 堆石头,第 $$$i$$$ 堆有 $$$a_i$$$ 石头。

每块石头都是相同的,重 $$$1$$$ 克,除了一颗特殊的石头,它是未知堆的一部分,重 $$$2$$$ 克。

第一个测试用例的图片。堆$$$2$$$有特殊的石头。这些桩的重量分别为 $$$1,3,3,4,5$$$。

Gon只能问导演一种问题:他可以选择$$$k$$$堆,然后导演会告诉他所选择的堆的总重量。更正式地说,Gon 可以选择一个整数 $$$k$$$ ($$$1 \leq k \leq n$$$) 和 $$$k$$$ 唯一桩 $$$p_1, p_2, \dots, p_k$$$ ($$$1 \leq p_i \leq n$$$),导演将返回总权重 $$$m_{p_1} + m_{p_2} + \dots + m_{p_k}$$$,其中$$$m_i$$$表示堆$$$i$$$的重量。

小杰的任务是找到包含特殊石头的一堆石头。不过,导演很忙。帮助 Gon 在最多 $$$\mathbf{30}$$$ 查询中找到这一堆。

输入

输入数据包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) - 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 堆的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \leq a_i \leq 10^4$$$) — 每堆石子的数量。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

读取每个测试用例的输入后,继续进行如下交互。

互动

您最多可以执行 $$$\mathbf{30}$$$ 次操作来猜测一堆。

要进行猜测,请按以下格式打印一行:

- $$$\texttt{?}\ k \ p_1 \ p_2 \ p_3 \ ... \ p_{k-1}\ p_k$$$ ($$$1 \leq k \leq n$$$; $$$1 \leq p_i \leq n$$$; 所有 $$$p_i$$$ 都是不同的) — 桩的索引。

当你知道带有特殊石头的堆的索引时,按以下格式打印一行:$$$\texttt{!}\ m$$$ ($$$1 \leq m \leq n$$$)。

之后,继续进行下一个测试用例,或者如果没有剩余的测试用例则终止程序。

如果您的程序对一个测试用例执行超过 $$$30$$$ 操作或进行无效查询,您可能会收到错误答案判决。

打印查询或答案后,请记住输出行尾并刷新输出。否则,您可能会得到超出空闲限制或其他一些判决。为此,请使用以下命令:

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

另外建议参与者阅读互动问题指南。

黑客

要进行破解,请使用以下格式。

第一行应包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的第一行应包含两个整数 $$$n, m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) – 堆的数量和带有特殊石头的堆。

每个测试用例的第二行应包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \leq a_i \leq 10^4$$$) — 每堆石头的数量。

请注意,交互器不是自适应的,这意味着答案在参与者提出查询之前就已知,并且不依赖于参与者提出的查询。

示例

输入 #1

2
5
1 2 3 4 5

11

6

3

7
1 2 3 5 3 4 2

12

6

输出 #1

? 4 1 2 3 4

? 2 2 3

? 1 2

! 2

? 4 2 3 5 6

? 2 1 4

! 7

注意

在第一个测试用例中,重量为 2 的石头位于 $$$2$$$ 堆中,如图所示。我们执行以下交互:

- $$$\texttt{? 4 1 2 3 4}$$$ — 询问堆的总重量 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$4$$$。我们收到的总重量为$$$1+3+3+4=11$$$。
- $$$\texttt{? 2 2 3}$$$ — 询问堆的总重量 $$$2$$$ 和 $$$3$$$。我们收到的总重量为$$$3+3=6$$$。
- $$$\texttt{? 1 2}$$$ —询问堆的总重量$$$2$$$。我们收到的总重量为 $$$3$$$。
- $$$\texttt{! 2}$$$ - 我们已经发现堆 $$$2$$$ 包含特殊石头,因此我们输出它并继续下一个测试用例。

在第二个测试用例中,重量为 2 的石子位于索引 $$$7$$$ 上。我们执行以下交互:

- $$$\texttt{? 4 2 3 5 6}$$$ — 询问堆的总重量 $$$2$$$、$$$3$$$、$$$5$$$ 和 $$$6$$$。我们收到的总重量为$$$2+3+3+4=12$$$。
- $$$\texttt{? 2 1 4}$$$ — 询问堆的总重量 $$$1$$$ 和 $$$4$$$。我们收到的总重量为$$$1+5=6$$$。
- $$$\texttt{! 7}$$$ — 我们以某种方式发现堆 $$$7$$$ 包含特殊石头,因此我们将其输出并结束交互。