Candies (Codeforces 1810B)
Tags: Math, number theory

This problem is about candy. Initially, you only have $$$1$$$ candy, and you want to have exactly $$$n$$$ candies.You can use the two following spells in any order at most $$$40$$$ times in total.  Assume you have $$$x$$$ candies now. If you use the first spell, then $$$x$$$ candies become $$$2x-1$$$ candies.  Assume you have $$$x$$$ candies now. If you use the second spell, then $$$x$$$ candies become $$$2x+1$$$ candies. Construct a sequence of spells, such that after using them in order, you will have exactly $$$n$$$ candies, or determine it's impossible.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Their description follows.Each test case contains one line with a single integer $$$n$$$ ($$$2 \le n \le 10^9$$$) — the required final number of candies.

Output: For each test case, output the following.If it's possible to eventually have $$$n$$$ candies within $$$40$$$ spells, in the first line print an integer $$$m$$$ ($$$1 \le m \le 40$$$), representing the total number of spells you use.In the second print $$$m$$$ integers $$$a_{1}, a_{2}, \ldots, a_{m}$$$ ($$$a_{i}$$$ is $$$1$$$ or $$$2$$$) separated by spaces, where $$$a_{i} = 1$$$ means that you use the first spell in the $$$i$$$-th step, while $$$a_{i} = 2$$$ means that you use the second spell in the $$$i$$$-th step.Note that you do not have to minimize $$$m$$$, and if there are multiple solutions, you may output any one of them.If it's impossible, output $$$-1$$$ in one line.

Note: For $$$n=3$$$, you can just use the second spell once, and then have $$$2 \cdot 1 + 1 = 3$$$ candies.For $$$n=7$$$, you can use the second spell twice. After the first step, you will have $$$3$$$ candies. And after the second step, you will have $$$2 \cdot 3 + 1 = 7$$$ candies.

Sample Inputs:
4
2
3
7
17

Sample Outputs:
-1
1
2 
2
2 2 
4
2 1 1 1

Solution (Python):
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
    n = int(input())
    if n % 2 == 0:
        print('-1')
    else:
        x = bin(n)[2:-1]
        ans = ['1' if i == '0' else '2' for i in x]
        print(len(ans))
        print(' '.join(ans))

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    if n % 2 == 0:
        print(-1)
        continue
    b = bin(n)[2:-1]
    print(len(b))
    print(' '.join((chr(ord(e) + 1) for e in b)))

Solution (Python):
n = int(input())
for i in range(n):
    a = int(input())
    if a % 2 == 0:
        print(-1)
    else:
        a //= 2
        s = bin(a).replace('0b', '').replace('1', '2 ').replace('0', '1 ')
        a = len(s) // 2
        print(a)
        print(s)