题目描述

题目译自 Ukrainian Olympiads in Informatics 2023 Stage 4 Day1 T2. Масив монет і запити зважування

这是一个交互题。

有 $n$ 枚硬币，排成一排，从左到右编号为 $1$ 到 $n$。

其中恰好有 $k$ $(k < n)$ 枚硬币是假的，其余 $(n - k)$ 枚是真硬币。假硬币比真硬币轻。所有真硬币的重量相同，而假硬币的重量可能不同。已知假硬币是连续排列的，即它们的编号为 $p, p+1, \ldots, (p+k-1)$。

你的任务是找到最左边假硬币的编号。你可以通过称重操作来实现，这类似于使用双盘天平：选择两个不相交的硬币集合，比较它们的重量，判断哪个集合更重，或者两集合重量相等。

输入格式

输入的第一行包含三个整数 $n, k, g$ $(1 \le k < n \le 10^4, 0 \le g \le 6)$，分别表示硬币总数、假硬币数量和子任务编号。

交互方式

要执行称重查询，输出 $\texttt{?}\ s_1\ s_2\ a_1\ a_2\ \dots\ a_{s_1}\ b_1\ b_2\ \dots\ b_{s_2}$，其中 $s_1$ 和 $s_2$ 表示两个称重集合的大小，数组 $a$ 和 $b$ 分别表示属于第一个和第二个集合的硬币编号。

作为查询响应，评测程序将返回一个整数 $x$ $(x \in \{0, 1, 2\})$。如果 $x = 1$，则第一个集合比第二个集合重；如果 $x = 2$，则第二个集合比第一个集合重；如果 $x = 0$，则两个集合重量相等。

如果查询无效（即超过最大查询次数或查询参数无效），评测程序将输出 -1 并终止运行。在这种情况下，请结束程序以获得「答案错误」的评测结果。

请确保在输出每行后调用 flush 方法。可以使用以下方式：

• C++ 中使用 fflush(stdout)、cout << endl 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 sys.stdout.flush()；
• 其他编程语言请参考相关文档。

输出格式

要提交答案，输出单行 $\texttt{!}\ p$，其中 $p$ $(1 \leq p \leq n)$ 是最左边假硬币的编号。

4 1 0

0

0

2

? 1 1 1 2

? 1 1 2 4

? 1 1 3 4

! 3

数据范围与提示

定义 $q$ 为在某个子任务中你可以执行的最大称重查询次数。

详细子任务附加限制及分值如下表所示：

对于最后一个子任务，设最大使用的称重次数为 $c$。如果 $c \le 9$，得 $54$ 分；否则得 $\lfloor 54 \cdot \max(-0.0004 \cdot c + 0.3134, 0.018 + \frac{9.0773}{c}) \rfloor$ 分

C++ 代码计算最后一个子任务的分数：

((c <= 9) ? 54 : int(54 * (max((-0.0004 * c + 0.3134), (0.018 + 9.0773 / c)))))

分数分布表