CF2138A Cake Assignment

Chocola 和 Vanilla 都喜欢蛋糕。今天，一家蛋糕店的经理送给她们总共 $2^{k+1}$ 个蛋糕。这些蛋糕被平均分配，所以她们每人一开始都收到了 $2^k$ 个蛋糕。 然而，Chocola 和 Vanilla 现在想要重新分配蛋糕，使得 Chocola 最终有恰好 $x$ 个蛋糕，Vanilla 拥有剩下的 $2^{k+1}-x$ 个蛋糕。 在每一步操作中，她们可以执行以下两种操作之一，且只能选择其中之一： 1. Chocola 把自己的一半蛋糕给 Vanilla。只有当 Chocola 当前蛋糕数为偶数时，这个操作才允许。 2. Vanilla 把自己的一半蛋糕给 Chocola。只有当 Vanilla 当前蛋糕数为偶数时，这个操作才允许。 你的任务是确定最少需要多少步才能达到目标分配方式，并输出任意一种能达到最少步数的操作序列。 可以保证，在给定的约束条件下，总有合法解，并且最少所需的步数不超过 $120$。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $k$ 和 $x$（$1 \le k \le 60$，$1 \le x \le 2^{k+1}-1$）——每个人一开始都有 $2^k$ 个蛋糕，$x$ 是 Chocola 重新分配后应拥有的蛋糕数。

对于每个测试用例，输出一个整数 $n$（$0 \le n \le 120$），表示至少需要几步操作才能完成蛋糕的重新分配。 下一行输出 $n$ 个整数 $o_1, o_2, \ldots, o_n$（$o_i=1$ 或 $o_i=2$），表示第 $i$ 步执行的操作：$o_i=1$ 代表本步 Chocola 给 Vanilla 一半蛋糕（操作 1），$o_i=2$ 代表本步 Vanilla 给 Chocola 一半蛋糕（操作 2）。

在第一个测试用例中，她们可以用以下步骤使得 Chocola 恰好有 $x=3$ 个蛋糕，Vanilla 有 $2^{k+1}-x=5$ 个蛋糕。用 $\{a, b\}$ 表示当前 Chocola 拥有 $a$ 个蛋糕，Vanilla 拥有 $b$ 个蛋糕。 $$\{4, 4\} \xrightarrow{o_1 = 2} \{6, 2\} \xrightarrow{o_2 = 1} \{3, 5\}$$ 在第二个测试用例中，Chocola 已有恰好 $x=4$ 个蛋糕，Vanilla 已有 $2^{k+1} - x=4$ 个蛋糕，因此无需操作。 在第三个测试用例中，她们可以用以下步骤使得 Chocola 恰好有 $x=7$ 个蛋糕，Vanilla 有 $2^{k+1}-x=9$ 个蛋糕。 $$\{8, 8\} \xrightarrow{o_1 = 2} \{12, 4\} \xrightarrow{o_2 = 2} \{14, 2\} \xrightarrow{o_3 = 1} \{7, 9\}$$ 由 ChatGPT 5 翻译