P13533 [OOI 2023] 寻找假币

**这是一个交互式问题。** 你面前有一批 $n$ 枚金币，其中有 $k$ 枚是假币。所有金币排成一行。第 $i$ 枚金币的理论重量为 $i$ 克。如果某枚金币是假币，它的重量为 $0$ 克。 禁止触碰金币，你唯一能进行的操作是选择某个 $1 \leq p \leq n$，称为称重操作，对前 $p$ 枚金币进行称重。你将得到这 $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$ 枚金币。你将获得一个整数 $a$。如果 $a = -1$，说明你已经超过了本局允许的最大称重次数，你的程序必须立即终止。每局最多允许 $3500$ 次称重。若 $a \geq 0$，则 $a$ 是金币 $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 的 `writeln`，C++ 的 `cout

无

无

### 样例解释 在第一局中，金币 $1$ 和 $3$ 是假币，因此实际重量为 $[0, 2, 0]$。只需一次称重即可得到总重量 $2$，据此可以唯一确定假币的位置。 在第二局中，金币 $2, 6, 8, 10$ 是假币，实际重量为 $[1, 0, 3, 4, 5, 0, 7, 0, 9, 0]$。通过称重结果可以唯一确定假币集合。 ### 评分说明 本题测试点分为 6 组。设 $q$ 为你在一局中称重的次数。 前 5 组，每组有一个 $maxQ$，如果你在一局中 $q \leq maxQ$，则该测试点通过。只有通过某组全部测试点，且通过部分之前组全部测试点，才能获得该组分数。 第 6 组为部分分，单局得分为 $\min\left(50, \left\lfloor 50 \sqrt{\frac{k + 30}{q}} \right\rfloor\right)$。该组的总分为所有测试中单局得分的最小值。 注意：如果你在所有测试的所有局中都能做到 $q \leq k + 30$，则可获得 $100$ 分。 | 组别 | 分值 | $n$ | $k$ | $maxQ$ | 必须通过的组 | 备注 | |:----:|:----:|:---:|:---:|:------:|:------------:|:----:| | 0 | 0 | -- | -- | $3500$ | -- | 样例测试点 | | 1 | 5 | $n \leq 1000$ | -- | $1000$ | 0 | | | 2 | 9 | $n \leq 1000$ | -- | $600$ | 0, 1 | | | 3 | 10 | -- | $k \leq 30$ | $1000$ | 0 | | | 4 | 13 | -- | $k = 3$ | $33$ | -- | | | 5 | 13 | -- | $k = 4$ | $34$ | -- | | | 6 | $\leq 50$ | -- | -- | $3500$ | -- | 部分分数 |