CF1807E Interview

这是一个交互题。如果你不熟悉交互题的工作方式，建议阅读[参赛者指南](https://codeforces.com/blog/entry/45307)。 在考试的最后阶段之前，主任进行了一次面试。他给了 Gon $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 的任务是找出包含特殊石子的那一堆。然而，主任很忙。请你帮助 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$ 互不相同）——表示要查询的堆的编号。 每次操作后，你应读取一行，包含一个整数 $x$——所选堆的总重量。（形式化地，$x = m_{p_1} + m_{p_2} + \dots + m_{p_k}$。） 当你确定特殊石子所在的堆的编号时，输出一行，格式如下：$\texttt{!}\ m$（$1 \leq m \leq n$）。 之后，进入下一组测试用例，或者如果没有更多测试用例则终止程序。 如果你的程序对某组测试用例进行了超过 $30$ 次操作，或进行了非法的查询，你可能会收到 Wrong Answer 判决。 每次输出查询或答案后，请记得输出换行并刷新输出缓冲区。否则，你可能会收到 Idleness limit exceeded 或其他判决。为此，请使用以下方法： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请参见相关文档。 强烈建议阅读[交互题参赛者指南](https://codeforces.com/blog/entry/45307)。 Hack 制作 Hack 时，请使用以下格式。 第一行包含一个整数 $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$）——表示每堆石子的数量。 注意，交互器是非自适应的，这意味着答案在选手发起询问前就已确定，并不会根据选手的询问而改变。

在第一组样例中，重量为二的石子位于第 $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$ 堆包含特殊石子，因此输出 $7$ 并结束交互。 由 ChatGPT 4.1 翻译