← 返回题目列表

Codeforces · 2168/C

C. 拦截蝴蝶

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

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

Alice有一个整数$$$x$$$,其中$$$1 \le x \le 2^{15}$$$,她需要将其发送给Bob(月球上的宇航员),因为这是他们在月球上的秘密项目的重要参数。

幸运的是,Alice 有一个秘密存储设备 $$$S$$$,其中包含 不一定非空 集合 $$$\{1, 2, \ldots, 20\}$$$ 的子集。她计划向 Bob 发送 $$$S$$$。 Bob 的目标是仅使用 $$$S$$$ 恢复 $$$x$$$ 的值。

然而,在爱丽丝在宇宙飞船上发送了$$$S$$$之后,鲍勃收到$$$S$$$之前,魔法蝴蝶已经拦截了宇宙飞船!当 Bob 最终收到 $$$S$$$ 时,发生了以下情况之一:

  • 从 $$$S$$$ 中删除任意元素。仅当 $$$S$$$ 非空时才能执行此操作。
  • 任意元素被添加到$$$S$$$。这仍然应该满足 $$$S \subseteq \{1, 2, \ldots, 20\}$$$。
  • $$$S$$$ 保持不变。

请为 Alice 和 Bob 设计一个策略,以便 Bob 可以确定 $$$x$$$ 的值,无论设置 $$$S$$$ 时发生了什么。准确地说,在这个问题中,您的代码将在每个测试中运行两次。在第一次运行中,您将扮演爱丽丝,在第二次运行中,您将扮演鲍勃。除了 $$$S$$$ 集合之外,没有其他信息可以从 Alice 传输到 Bob。为了得到一个 已接受 结论,第二次运行的代码应该能够准确恢复第一次运行时收到的整数。

首次运行

输入

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

输入的第二行恰好包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

第 $$$i$$$ 测试用例的第一行也是唯一一行包含整数 $$$x$$$ ($$$1 \le x \le 2^{15}$$$)。

输出

对于每个测试用例,通过按以下方式打印两行将 $$$S$$$ 发送给 Bob。

  • 在第一行,输出一个整数 $$$n$$$ ($$$0 \le n \le 20$$$) — $$$S$$$ 的大小。
  • 在第二行,输出 $$$n$$$ 空格分隔的整数 $$$S_1,S_2,\ldots,S_n$$$ ($$$1 \le S_i \le 20$$$)。

特殊情况下,如果 $$$n=0$$$,则可以省略第二行。您可以按任意顺序输出 $$$S$$$ 的元素。然而,它们必须是成对不同的。

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

第二次运行

输入

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

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

每个测试用例的第一行包含一个整数 $$$n'$$$ ($$$0 \leq n' \leq 20$$$) - Bob 收到的集合 $$$S'$$$ 的大小,即可能 已修改 $$$S$$$。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$S'_1, S'_2, \ldots, S'_n$$$ ($$$1 \leq S'_i \leq 20$$$) — Bob 收到的 $$$S'$$$ 的元素。 $$$S'$$$ 的元素按升序排序,即使原始 $$$S$$$ 未按升序排序。

请注意,第二次运行中的测试用例可能会被打乱。请参阅示例输入了解更多详细信息。

输出

对于每个测试用例,打印一行,其值为 $$$x$$$ ($$$1 \leq x \leq 2^{15}$$$)。

示例

输入
复制

first
4
1
20
50
32768

输出
复制

0

3
13 4 9 
4
1 7 4 2
10
14 17 1 6 2 19 20 8 7 18

输入
复制

second
4
4
4 5 9 13
9
1 2 6 7 8 14 17 18 19
0

5
1 2 3 4 7

输出
复制

20
32768
1
50

注意

首次运行:输入包含四个测试用例,$$$x=1, 20, 50, 32\,768$$$。根据事先约定的策略,Alice 将 $$$x=1$$$ 发送给 Bob $$$\varnothing$$$,$$$x=20$$$ 的集合 $$$\{13,4,9\}$$$,$$$x=20$$$ 的集合 $$$\{1,7,4,2\}$$$,$$$x=50$$$ 的集合 $$$\{1,7,4,2\}$$$,以及$$$\{14,17,1,6,2,19,20,8,7,18\}$$$ 为 $$$32\,768$$$。

第二次运行:请注意,第一次运行的测试用例被打乱了。它们按 $$$[20, 32\,768, 1, 50]$$$ 的顺序给出。

对于第一个测试用例,元素 $$$5$$$ 被添加到 Alice 的集合中。请注意,虽然 Alice 给出的初始集合为 $$$\{13,4,9\}$$$,但该集合是按递增顺序给出给 Bob 的。

对于第二个测试用例,数字 $$$20$$$ 已从 Alice 的集合中删除。

对于第三个测试用例,该集合未更改。