codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.