← 返回题目列表

Codeforces · 2237/G

G. 发送 GCD

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

这是一个运行两次(通信)交互问题。

有两名玩家:Ja the Ghost 和 Quack the Duck。陪审团(也称为该问题的交互者)将首先与 Ja 交互。 Ja结束互动后,陪审团将与Quack进行互动。请注意,Ja 和 Quack 可能不会直接向对方传递信息;两名玩家只能向陪审团发送信息或从陪审团接收信息。

在互动之前,陪审团确定一个整数 $$$n$$$ 和一个由 $$$n$$$ 正整数组成的数组 $$$a_1, a_2, \ldots, a_n$$$。这些价值观对于两名球员来说是一致的。

Ja 从陪审团收到 $$$n$$$ 和一个 $$$n$$$ 正整数数组 $$$a_1, a_2, \ldots, a_n$$$,他想将其发送给 Quack,其中 $$$a_i \le 10^6$$$。为此,Ja 将选择一个整数 $$$k$$$,其中 $$k \le \left\lceil \frac{10n}{9} \right\rceil + 150,$$ 并创建一个正整数数组 $$$b_1, b_2, \ldots, b_k$$$,其中 $$$b_i \le 10^6$$$,并将其发送回陪审团。然后陪审团将给 Quack 整数 $$$n$$$ 和 $$$k$$$。 Quack 最多可以向陪审团提出 $$$180n + 150$$$ 疑问,形式如下:

  • 选择任意两个整数 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le k$$$, $$$i \neq j$$$),陪审团将回答 $$$\mathrm{gcd}(b_i, b_j)$$$。

这里,$$$\gcd(x, y)$$$ 表示整数$$$x$$$ 和$$$y$$$ 的最大公约数(GCD)。

请注意,$$$a$$$ 和 $$$b$$$ 对 Quack 都是隐藏的; Quack 只能从查询中获取信息。

Ja 希望确保 Quack 可以确定原始数组 $$$a$$$。你的任务是扮演两个玩家并确定两个玩家的最佳交互策略,以便 Quack 正确确定原始数组 $$$a$$$。

第一次运行

您的代码将在每个测试中运行两次。第一次运行时,您将成为 Ja。

输入

输入的第一行包含字符串 第一。这样做的目的是让您的程序认识到这是它的第一次运行,并且它应该充当 Ja。

第二行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

第 $$$i$$$ 个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^3$$$) — 第 $$$i$$$ 个测试用例的 $$$a$$$ 的长度。

第 $$$i$$$ 测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 数组 $$$a$$$。

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

输出

对于每个测试用例,首先打印一个整数 $$$k$$$ ($$$1 \le k \le \left\lceil \frac{10n}{9} \right\rceil + 150$$$),表示数组 $$$b$$$ 的长度。然后打印 $$$k$$$ 整数 $$$b_1, b_2, \ldots, b_k$$$ ($$$1 \le b_i \le 10^6$$$),表示 Ja 将发送给陪审团的数组 $$$b$$$。该数组将用于回答第二次运行中的查询。

此后,继续进行下一个测试用例,或者如果是最后一个测试用例则终止程序。

第二次运行

第二次运行时,你是庸医。

输入

输入的第一行包含字符串 第二。这样做的目的是让你的程序认识到这是它的第二次运行,并且它应该充当嘎嘎声。

输入的第二行恰好包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。请注意,该数字等于第一次运行输入中的 $$$t$$$。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le k \le \left\lceil \frac{10n}{9} \right\rceil + 150$$$)。这分别表示 $$$a$$$ 和 $$$b$$$ 的长度。

请注意,第二次运行中的测试用例可能会被打乱。请参阅示例测试用例以获取更多说明。

互动

对于第 $$$i$$$ 个测试用例,请记住,根据上述输入格式,您将首先在陪审团的输入中收到 $$$n$$$ 和 $$$k$$$。收到这些输入后,您最多可以进行 $$$180n + 150$$$ 如下形式的查询:

  • ?我j ($$$1 \leq i, j \leq k$$$, $$$i \neq j$$$)。

每次查询后,陪审团都会以 $$$\mathrm{gcd}(b_i, b_j)$$$ 进行响应,您应该通过输入流读取它。

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

一旦您准备好报告原始数组 $$$a$$$,您可以按照以下格式进行操作:

  • ! $$$a_1, a_2, \ldots,a_n$$$ ($$$1 \leq a_i \leq 10^6$$$)。

然后,您将继续执行下一个测试用例,或者如果您已处理完每个测试用例,则程序必须终止。

交互器是 不 自适应。也就是说,数组 $$$a$$$ 和 $$$b$$$ 在交互过程中都不会改变,并且始终与第一次运行时的数组相同。

打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

$$$^{\text{*}}$$$要刷新,请使用:

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

示例

输入
复制

first
2
6
1 1 4 5 1 4
3
2 6 10

输出
复制

7
20 1 1 4 5 1 4
4
30 2 6 10

输入
复制

second
2
3 4

2

6

10
6 7

1

1

4

5

1

4

输出
复制

? 1 2

? 1 3

? 1 4

! 2 6 10

? 1 2

? 1 3

? 1 4

? 1 5

? 1 6

? 1 7

! 1 1 4 5 1 4

注意

在第一次运行中,有两个测试用例。

对于第一个测试用例,Ja 被赋予 $$$a = [1, 1, 4, 5, 1, 4]$$$。他决定发送 $$$b = [20, 1, 1, 4, 5, 1, 4]$$$。

对于第二个测试用例,Ja 被赋予 $$$a = [2, 6, 10]$$$。他决定发送 $$$b = [30, 2, 6, 10]$$$。

在第二次运行中,测试用例的顺序被打乱。因此,Quack 首先收到 $$$n = 3$$$ 和 $$$k = 4$$$ 的测试用例。他询问 $$$\mathrm{gcd}(b_1, b_i)$$$ $$$i = 2, 3, 4$$$,陪审团回答 $$$2, 6, 10$$$。因此,Quack可以确定原始数组是$$$[2, 6, 10]$$$。

然后 Quack 收到 $$$n = 6$$$ 和 $$$k = 7$$$ 的测试用例。他询问 $$$\mathrm{gcd}(b_1, b_i)$$$ $$$i = 2, 3, 4, 5, 6, 7$$$,陪审团回答 $$$1, 1, 4, 5, 1, 4$$$。由此,Quack可以确定原数组为$$$[1, 1, 4, 5, 1, 4]$$$。

此示例说明,尽管第二次运行中的测试用例可能以不同的顺序出现,但使用了与第一次运行相同的数组 $$$a$$$ 和 $$$b$$$。