1977B.md (1660B)
1 Source: https://codeforces.com/problemset/problem/1977/B 2 3 B. Binary Colouring 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a positive integer $x$. Find any array of integers $a_0, a_1, \ldots, a_{n-1}$ for which the following holds: 22 23 * $1 \le n \le 32$, 24 * $a_i$ is $1$, $0$, or $-1$ for all $0 \le i \le n - 1$, 25 * $x = \displaystyle{\sum_{i=0}^{n - 1}{a_i \cdot 2^i}}$, 26 * There does not exist an index $0 \le i \le n - 2$ such that both $a_{i} \neq 0$ and $a_{i + 1} \neq 0$. 27 28 It can be proven that under the constraints of the problem, a valid array always exists. 29 30 Input 31 32 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows. 33 34 The only line of each test case contains a single positive integer $x$ ($1 \le x \lt 2^{30}$). 35 36 Output 37 38 For each test case, output two lines. 39 40 On the first line, output an integer $n$ ($1 \le n \le 32$) — the length of the array $a_0, a_1, \ldots, a_{n-1}$. 41 42 On the second line, output the array $a_0, a_1, \ldots, a_{n-1}$. 43 44 If there are multiple valid arrays, you can output any of them. 45 46 Example 47 48 Input 49 50 ``` 51 7 52 53 1 54 55 14 56 57 24 58 59 15 60 61 27 62 63 11 64 65 19 66 ``` 67 68 Output 69 70 ``` 71 1 72 1 73 5 74 0 -1 0 0 1 75 6 76 0 0 0 -1 0 1 77 5 78 -1 0 0 0 1 79 6 80 -1 0 -1 0 0 1 81 5 82 -1 0 -1 0 1 83 5 84 -1 0 1 0 1 85 ``` 86 87 Note 88 89 In the first test case, one valid array is $[1]$, since $(1) \cdot 2^0 = 1$. 90 91 In the second test case, one possible valid array is $[0,-1,0,0,1]$, since $(0) \cdot 2^0 + (-1) \cdot 2^1 + (0) \cdot 2^2 + (0) \cdot 2^3 + (1) \cdot 2^4 = -2 + 16 = 14$.