[AdditionalFile5375.zip](file://AdditionalFile5375.zip?type=additional_file)

#5375. 「OOI 2023 Day 2」寻找假币

标签: 交互 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2023 Day2 T3 「Поиск фальшивых монет」。

这是一个交互题。

你面前有一批包含 $n$ 枚金币，其中有 $k$ 枚是假币。所有金币排成一排。第 $i$ 枚金币的预期重量为 $i$ 克。如果金币是假的，则其重量为 $0$ 克。

你不能直接触碰金币，唯一可用的操作是选择一个 $1 \leq p \leq n$，并称量前 $p$ 枚金币的重量。操作后，你将得到这些金币的实际总重量。

请使用尽可能少的操作，找出哪些 $k$ 枚金币是假的。你的得分将取决于程序进行的查询次数，具体详情请参见评分规则。

交互方式

每个测试包含 $t$ 局游戏，在每局游戏中你需要找出哪些金币是假的。第一行包含一个整数 $t$ $(1 \leq t \leq 50)$，表示游戏局数。每局游戏按照以下描述的格式进行交互。所有游戏结束后，你的程序应终止运行。

在每局游戏开始时，你会收到两个整数 $n$ 和 $k$ $(1 \leq n \leq 10^{9}, 1 \leq k \leq \min(100, n))$。之后，你可以进行若干次称量查询。

要进行称量查询，请输出 $?\ p$，其中 $p$ 是你要称量的前 $p$ 枚金币。之后，你将收到一个整数 $a$。如果 $a = -1$，表示你的程序已超过每局游戏允许的称量查询次数限制，必须立即终止运行。每局游戏最多允许进行 $3500$ 次称量查询。否则，$a \geq 0$，表示金币 $1, 2, \ldots, p$ 的实际总重量。

要提交猜测的假币集合，请输出 $!\ i_1\ i_2\ \ldots\ i_k$，其中 $1 \leq i_1, i_2, \ldots, i_k \leq n$ 是不同假币的编号，可以按任意顺序排列。之后，你将收到一个整数 $a$。如果 $a = -1$，表示你的答案错误，程序必须立即终止运行。否则，$a = 1$，表示答案正确，你的程序应继续下一局游戏，或在这是最后一局游戏时终止运行。

请注意，交互程序是自适应的。不保证假币集合在游戏开始前已固定。唯一保证的是，在任何时刻，游戏过程中给出的回答都至少与一个假币集合相符。你的答案被认为是正确的，当且仅当它与游戏过程中给出的所有查询回答一致，并且不存在其他假币集合也与所有回答一致。

每次输出操作后，请换行。每次输出操作后，请刷新输出流。

如果你在 Pascal 中使用 $\texttt{writeln}$，在 C++ 中使用 $\texttt{cout << ... << endl}$，在 Java 中使用 $\texttt{System.out.println}$，在 Python 中使用 $\texttt{print}$，在 C# 中使用 $\texttt{Console.WriteLine}$，则输出流会自动刷新，无需额外操作。如果使用其他输出方式，建议手动刷新输出流。无论如何，都需要输出换行符。

样例

输入

2
3 2

2

1
10 4

13

13

20

29

1

输出

? 3

! 1 3


? 5

? 6

? 8

? 10

! 10 8 6 2

在第一局游戏中，金币 $1$ 和 $3$ 是假的。因此，金币的实际重量为 $[0, 2, 0]$。通过一次查询，我们得知它们的总重量为 $2$，之后可以唯一确定假币集合。

在第二局游戏中，金币 $2, 6, 8, 10$ 是假的。因此，金币的实际重量为 $[1, 0, 3, 4, 5, 0, 7, 0, 9, 0]$。通过称量查询的回答，可以唯一确定假币集合。

数据范围与提示

设 $q$ 为程序在一局游戏中进行的称量查询次数。

对于前 $5$ 个子任务，只有在通过该子任务及必要前置子任务的所有测试点时才会获得分数。对于前 $5$ 个子任务，每个子任务固定了一个值 $maxQ$。如果 $q \leq maxQ$，则该测试点通过。

对于最后一个子任务，每局游戏的得分为 $\min\left(50, \left\lfloor 50 \sqrt{\frac{k + 30}{q}} \right\rfloor\right)$。每个测试的总得分为所有游戏中的最低得分。最后一组子任务的总得分为所有测试中的最低得分。

注意，如果程序在所有测试的所有游戏中进行的称量查询次数 $\leq k + 30$，则可以获得 $100$ 分。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。