A16738. Intercepting Butterflies
编程题
省选/NOI-
知识点
题目描述
本题是一道运行两次（通信）类题目。
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}$）。
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}$）。
输入格式
无
输出格式
无
输入输出样例
输入 #1
first 4 1 20 50 32768
输出 #1
0 3 13 4 9 4 1 7 4 2 10 14 17 1 6 2 19 20 8 7 18
说明/提示
第一次运行：输入包含四个测试用例，$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 的集合中删除。
对于第三组测试用例，集合未被更改。
第二次运行：注意本次四组测试用例顺序被打乱，为 $[20, 32\,768, 1, 50]$。
对于第一组测试用例，$5$ 被添加进了 Alice 的集合。虽然 Alice 发的是 $S=\{13,4,9\}$，但 Bob 收到的是已经排好序的集合。
对于第二组测试用例，$20$ 被从 Alice 的集合中删除。
对于第三组测试用例，集合未被更改。