← 返回题目列表

Codeforces · 2159/A

A. MAD互动问题

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

这是一个交互问题。

有一个秘密序列 $$$a_1, a_2, \ldots, a_{2n-1},a_{2n}$$$,其中包含从 $$$1$$$ 到 $$$n$$$ 的每个整数 正好两次.

您的任务是通过使用以下类型的查询来猜测序列:

  • "? $$$k\;j_1\;j_2\;\ldots\;j_k$$$" — 选择整数 $$$k$$$ ($$$1 \le k \le 2n$$$) 和 $$$k$$$ 不同 索引 $$$j_1, j_2, \ldots, j_k$$$ ($$$1 \le j_1 , j_2 , \ldots , j_k \le 2n$$$)。作为对查询的回应,陪审团将返回 $$$\text{MAD}([a_{j_1}, a_{j_2}, \ldots, a_{j_k}])$$$。

我们将整数序列的 $$$\operatorname{MAD}$$$ (Maximum Appearing Duplicate) 定义为至少出现两次的最大整数。具体来说,如果没有至少出现两次的数字,则 $$$\operatorname{MAD}$$$ 值为 $$$0$$$。一些示例如下:

  • $$$\操作员名称{MAD}([1, 2, 1]) = 1$$$;
  • $$$\操作员名称{MAD}([2, 2, 3, 3]) = 3$$$;
  • $$$\操作员名称{MAD}([1, 2, 3, 4]) = 0$$$。

请识别秘密序列 最多使用 $$$3n$$$ 查询.

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 3000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 300$$$)。

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

阅读此行输入后,交互将从您的第一个查询开始。

互动

要进行查询,请按以下格式输出一行(不带引号):

  • "? $$$k\;j_1\;j_2\;\ldots\;j_k$$$" ($$$1 \le k \le 2n$$$, $$$1 \le j_1 , j_2 , \ldots , j_k \le 2n$$$)

这里,您选择的索引 $$$j_1 , j_2 , \ldots , j_k$$$ 必须是 成对不同.

然后,在每次查询后,读取一个整数——查询的答案。

您最多可以进行 $$$3n$$$ 这种类型的查询。

如果您的程序找到了序列 $$$a$$$,请按以下格式打印该行(不带引号):

  • "! $$$a_1\;a_2\;\ldots\;a_{2n-1}\;a_{2n}$$$" ($$$1 \le a_i \le n$$$)

请注意,这不计入查询限制。

此后,继续进行下一个测试用例,如果这是最后一个测试用例,则退出。

此任务中的交互器是 不自适应。换句话说,序列 $$$a$$$ 在交互过程中不会改变。

如果您在交互过程中进行超过 $$$3n$$$ 查询,您的程序必须立即终止,并且您将收到 错误答案 判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

打印每一行后,不要忘记输出行尾并刷新输出缓冲区。否则,您将收到 超出空闲限制 判决。要冲洗,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • System.out.flush() ;
  • stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

黑客

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

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

每个测试用例的第一行应包含一个整数 $$$n$$$ ($$$2 \leq n \leq 300$$$)。

以下行应包含 $$$2n$$$ 整数 $$$a_1,a_2,\ldots,a_{2n}$$$ ($$$1 \leq a_i \leq n$$$)。从 $$$1$$$ 到 $$$n$$$ 的每个数字必须恰好出现两次。

所有测试用例的 $$$n^2$$$ 总和不应超过 $$$10^5$$$。

例如,示例交互对应的hack格式如下。

2
2
2 2 1 1
2
1 2 1 2

示例

输入
复制

2
2

2

0

1

2

0

1

1

输出
复制


? 2 2 1

? 2 1 3

? 3 1 3 4

! 2 2 1 1

? 2 1 2

? 2 1 3

? 3 1 3 4

! 1 2 1 2

注意

在第一个测试用例中,隐藏序列是 $$$a=[2,2,1,1]$$$。

对于查询“? 2 2 1”,陪审团返回 $$$2$$$,因为 $$$\operatorname{MAD}([a_2, a_1]) = \operatorname{MAD}([2, 2]) = 2$$$。

对于查询“? 2 1 3”,陪审团返回 $$$0$$$,因为 $$$\operatorname{MAD}([a_1, a_3]) = \operatorname{MAD}([2, 1]) = 0$$$。

对于查询“? 3 1 3 4”,陪审团返回 $$$1$$$,因为 $$$\operatorname{MAD}([a_1, a_3, a_4]) = \operatorname{MAD}([2 ,1, 1]) = 1$$$。

请注意,示例交互仅用于理解语句,并且不 不 保证找到唯一的序列$$$a$$$。