← 返回题目列表

Codeforces · 2138/A

A. 蛋糕作业

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

巧克力和香草喜欢蛋糕。今天,一家蛋糕店的经理总共给了他们$$$2^{k+1}$$$蛋糕。蛋糕是均匀分配的,所以他们每个人最初都收到了 $$$2^k$$$ 蛋糕。

然而,Chocola 和 Vanilla 现在想要重新分配蛋糕,以便 Chocola 最终得到 $$$x$$$ 蛋糕,而 Vanilla 得到剩余的 $$$2^{k+1}-x$$$ 蛋糕。

在一个步骤中,他们可以执行以下两项操作之一:

  1. Chocola 把一半的蛋糕给了 Vanilla。仅当 Chocola 当前有偶数个蛋糕时才允许此操作。
  2. 香草把一半的蛋糕给了巧克力。仅当 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 = \mathtt{1}$$$ 或 $$$o_i = \mathtt{2}$$$),其中 $$$o_i = \mathtt{1}$$$ 表示$$$i$$$第步,Chocola 将一半的蛋糕给了 Vanilla(操作 1),$$$o_i = \mathtt{2}$$$ 表示 Vanilla 将一半的蛋糕给了 Chocola(操作 2)。

示例

输入
复制

4
2 3
2 4
3 7
2 5

输出
复制

2
2 1 
0

3
2 2 1 
2
1 2 

注意

在第一个测试用例中,他们可以使用以下步骤,以便 Chocola 正好有 $$$x = 3$$$ 蛋糕,而 Vanilla 正好有 $$$2 ^ {k + 1} - x = 5$$$ 蛋糕。我们使用 $$$\{a, b\}$$$ 来表示 Chocola 目前有 $$$a$$$ 蛋糕,Vanilla 目前有 $$$b$$$ 蛋糕。

$$\{4, 4\} \xrightarrow{o_1 = \mathtt{2}} \{6, 2\} \xrightarrow{o_2 = \mathtt{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 = \mathtt{2}} \{12, 4\} \xrightarrow{o_2 = \mathtt{2}} \{14, 2\} \xrightarrow{o_3 = \mathtt{1}} \{7, 9\}$$