← 返回题目列表

Codeforces · 1152/B

B. Neko 进行猫毛皮变换

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

Cat Furrier Transform 是猫程序员中用于创建长猫的流行算法。作为有史以来最伟大的猫程序员之一,Neko 希望利用这种算法来创建完美的长猫。

假设我们有一只猫,编号为$$$x$$$。完美的长猫是一只猫,对于某个非负整数 $$$m$$$,其数字等于 $$$2^m - 1$$$。例如,数字 $$$0$$$、$$$1$$$、$$$3$$$、$$$7$$$、$$$15$$$ 等都适合完美的长猫。

在 Cat Furrier 变换中,可以对 $$$x$$$ 执行以下操作:

- (操作 A):选择任何非负整数 $$$n$$$ 并将 $$$x$$$ 替换为 $$$x \oplus (2^n - 1)$$$,其中 $$$\oplus$$$ 是按位异或运算符。
-(操作 B):将 $$$x$$$ 替换为 $$$x + 1$$$。

第一个应用的操作必须是类型 A,第二个应用的操作必须是类型 B,第三个应用的操作必须是类型 A,依此类推。形式上,如果我们按照执行顺序从一开始对操作进行编号,则奇数编号的操作必须是 A 类型,偶数编号的操作必须是 B 类型。

Neko 希望以工业规模生产完美的长猫,因此对于每只猫 Neko 只想执行最多 $$$40$$$ 操作。你能帮 Neko 写一份转型计划吗?

请注意,不需要最小化操作数量。您只需要使用不超过 $$$40$$$ 操作。

输入

唯一一行包含单个整数 $$$x$$$ ($$$1 \le x \le 10^6$$$)。

输出

第一行应包含一个整数 $$$t$$$ ($$$0 \le t \le 40$$$) — 要应用的操作数。

然后对于每个奇数操作打印其中相应的数字$$$n_i$$$。也就是说,打印 $$$\lceil \frac{t}{2} \rceil$$$ 整数 $$$n_i$$$ ($$$0 \le n_i \le 30$$$),表示在相应步骤中用 $$$x \oplus (2^{n_i} - 1)$$$ 替换 $$$x$$$。

如果有多个可能的答案,您可以打印其中任何一个。可以证明,在这个问题的约束中至少有一个答案。

示例

输入 #1

39

输出 #1

4
5 3

输入 #2

1

输出 #2

0

输入 #3

7

输出 #3

0

注意

在第一个测试中,其中一个转换可能如下:$$$39 \to 56 \to 57 \to 62 \to 63$$$。或者更准确地说:

1. 选择 $$$n = 5$$$。 $$$x$$$ 转换为 $$$39 \oplus 31$$$ 或 $$$56$$$。
2. 将 $$$x$$$ 增加 $$$1$$$,将其值更改为 $$$57$$$。
3. 选择 $$$n = 3$$$。 $$$x$$$ 转换为 $$$57 \oplus 7$$$ 或 $$$62$$$。
4. 将 $$$x$$$ 增加 $$$1$$$,将其值更改为 $$$63 = 2^6 - 1$$$。

在第二次和第三次测试中,数量已经满足目标要求。