← 返回题目列表

Codeforces · 1977/B

B. 二元着色

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

给你一个正整数 $$$x$$$。查找满足以下条件的任意整数数组 $$$a_0, a_1, \ldots, a_{n-1}$$$:

- $$$1 \le n \le 32$$$,
- $$$a_i$$$ 是 $$$1$$$、$$$0$$$ 或 $$$-1$$$ 对于所有 $$$0 \le i \le n - 1$$$,
- $$$x = \displaystyle{\sum_{i=0}^{n - 1}{a_i \cdot 2^i}}$$$,
- 不存在索引 $$$0 \le i \le n - 2$$$ 使得 $$$a_{i} \neq 0$$$ 和 $$$a_{i + 1} \neq 0$$$ 都成立。

可以证明,在问题的约束下,有效的数组总是存在的。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含一个正整数 $$$x$$$ ($$$1 \le x < 2^{30}$$$)。

输出

对于每个测试用例,输出两行。

在第一行,输出一个整数 $$$n$$$ ($$$1 \le n \le 32$$$) — 数组 $$$a_0, a_1, \ldots, a_{n-1}$$$ 的长度。

在第二行,输出数组$$$a_0, a_1, \ldots, a_{n-1}$$$。

如果有多个有效数组,则可以输出其中任何一个。

示例

输入 #1

7
1
14
24
15
27
11
19

输出 #1

1
1
5
0 -1 0 0 1
6
0 0 0 -1 0 1
5
-1 0 0 0 1
6
-1 0 -1 0 0 1
5
-1 0 -1 0 1
5
-1 0 1 0 1

注意

在第一个测试用例中,一个有效数组是 $$$[1]$$$,因为 $$$(1) \cdot 2^0 = 1$$$。

在第二个测试用例中,一个可能的有效数组是 $$$[0,-1,0,0,1]$$$,因为 $$$(0) \cdot 2^0 + (-1) \cdot 2^1 + (0) \cdot 2^2 + (0) \cdot 2^3 + (1) \cdot 2^4 = -2 + 16 = 14$$$。