CF2168C Intercepting Butterflies

本题是一道运行两次（通信）类题目。 Alice 手中有一个整数 $x$，其中 $1 \le x \le 2^{15}$。她需要将这个整数发送给月球上的 Bob，因为这是他们月球秘密项目的重要参数。 幸运的是，Alice 有一个秘密存储装置 $S$，其中包含集合 $\{1,2,\ldots,20\}$ 的一个（可能为空）子集。她准备将 $S$ 发送给 Bob。Bob 的目标是仅靠 $S$ 恢复出 $x$ 的值。 但在 Alice 发送 $S$ 并在 Bob 接收 $S$ 之前，神奇的蝴蝶劫持了飞船！当 Bob 最终收到 $S$ 时，会发生以下三种情况之一： - 从 $S$ 中任意删除一个元素（只有在 $S$ 非空时才允许）。 - 向 $S$ 中任意添加一个元素（添加元素后 $S$ 仍需满足 $S \subseteq \{1,2,\ldots,20\}$）。 - $S$ 保持不变。 请你为 Alice 和 Bob 设计一个策略，使得无论 $S$ 遭遇了哪种情况，Bob 都能准确还原出 $x$ 的值。具体来说，本题你的代码将在每组数据被运行两次。在第一次运行时，你充当 Alice；第二次运行时，你充当 Bob。除了集合 $S$，Alice 不能向 Bob 传递任何额外信息。只有在第二次运行时你的代码能准确恢复每组的 $x$ 值，才能通过本题。 第一次运行 输入 第一行输入字符串 first，表示现在是第一次运行，你的程序应当模拟 Alice 的行为。 第二行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来，每组测试用例一行，包含一个整数 $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$ 的元素可以任意顺序输出，但必须互不相同。 然后程序将自动进入下一组测试用例，或者已完成所有测试用例则结束。 第二次运行 输入 第一行输入字符串 second，表示现在是第二次运行，你的程序应当模拟 Bob 的行为。 第二行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。注意，该数字和第一次运行中输入的 $t$ 相同。 每组测试用例输入如下两行： 第一行输入一个整数 $n'$（$0 \le n' \le 20$），表示 Bob 实际收到的集合 $S'$ 的大小（$S'$ 可能是被更改过的 $S$）。 第二行输入 $n'$ 个递增排列的整数 $S'_1, S'_2, \ldots, S'_{n'}$（$1 \le S'_i \le 20$），表示 Bob 实际收到的 $S'$ 集合。即使 Alice 输出的 $S$ 未按递增排列，Bob 收到的一定是递增排序好的。 注意：第二次运行中的测试用例顺序可能发生了打乱。详见输入输出样例。 输出 对于每一组测试用例，输出一行，包含 Alice 发来的对应的整数 $x$（$1 \le x \le 2^{15}$）。

无

无

第一次运行：输入包含四个测试用例，$x=1, 20, 50, 32\,768$。根据事先约定的某种策略，Alice 分别为 $x=1$ 发送了 $S=\varnothing$，为 $x=20$ 发送了 $S=\{13,4,9\}$，为 $x=50$ 发送了 $S=\{1,7,4,2\}$，为 $x=32\,768$ 发送了 $S=\{14,17,1,6,2,19,20,8,7,18\}$。 第二次运行：注意本次四组测试用例顺序被打乱，为 $[20, 32\,768, 1, 50]$。 对于第一组测试用例，$5$ 被添加进了 Alice 的集合。虽然 Alice 发的是 $S=\{13,4,9\}$，但 Bob 收到的是已经排好序的集合。 对于第二组测试用例，$20$ 被从 Alice 的集合中删除。 对于第三组测试用例，集合未被更改。 由 ChatGPT 5 翻译