310287: CF1810B. Candies
Description
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.
InputEach 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.
OutputFor 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.
ExampleInput4 2 3 7 17Output
-1 1 2 2 2 2 4 2 1 1 1Note
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.
Input
题意翻译
### 题目描述 起初，你只有 $ 1 $ 颗糖，而你想要**恰好** $ n $ 颗糖。 你可以念以下两种咒语，但你所念的咒语的总数不能超过 $ 40 $ 句： * 假设你现在有 $ x $ 颗糖。如果你念咒语一，那么你的 $ x $ 颗糖就变成了 $ 2x - 1 $ 颗糖。 * 假设你现在有 $ x $ 颗糖。如果你念咒语二，那么你的 $ x $ 颗糖就变成了 $ 2x + 1 $ 颗糖。 如果可以念不超过 $ 40 $ 句咒语就能获得**恰好** $ n $ 颗糖，则你需要构造一个可能的咒语序列，否则你应判断这样的咒语序列不存在。 ### 输入格式 每个测试点包含多组测试数据。每组测试数据的第一行包含一个整数 $ t \text{ } (1 \le t \le 10 ^ 4) $，代表测试数据组数。 每组测试数据只有一行，该行包含一个整数 $ n \text{ } (2 \le n \le 10 ^ 9) $，代表你需要获得**恰好** $ n $ 颗糖。 ### 输出格式 对于每组测试数据，输出以下内容。 如果可以念不超过 $ 40 $ 句咒语就能获得**恰好** $ n $ 颗糖，那么在第一行输出一个整数 $ m $，代表你所念的咒语的总数。 在第二行输出 $ m $ 个由空格隔开的整数 $ a_1, a_2,..., a_m $ $ (a_i = 1 \text{ or } a_i = 2) $，其中 $ a_i = 1 $ 代表你的第 $ i $ 句咒语是咒语一，$ a_i = 2 $ 代表你的第 $ i $ 句咒语是咒语二。 注意，你的答案**不需要**使得 $ m $ 最小，如果有多种可能的答案，输出**任意一种**即可。 如果不可能获得**恰好** $ n $ 颗糖，在该行单独输出 $ -1 $。 ### 说明/提示 对于 $ n = 3 $，你只需要念一句咒语二，你就有了 $ 2 \times 1 + 1 = 3 $ 颗糖。 对于 $ n = 7 $，你只需要念两句咒语二。第一步后，你就有了 $ 3 $ 颗糖。而第二步后，你就有了 $ 2 \times 3 + 1 = 7 $ 颗糖。Output
这个问题是关于糖果的。最初，你只有1个糖果，你想要拥有正好n个糖果。
你可以最多总共使用40次以下两种咒语，可以使用任何顺序。
1. 假设你现在有x个糖果。如果你使用第一个咒语，那么x个糖果将变成2x-1个糖果。
2. 假设你现在有x个糖果。如果你使用第二个咒语，那么x个糖果将变成2x+1个糖果。
构造一个咒语序列，使得按顺序使用它们后，你将正好有n个糖果，或者确定这是不可能的。
输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是t个测试用例的描述。
每个测试用例包含一行，有一个整数n（2≤n≤10^9）——需要的糖果的最终数量。
输出数据格式：
对于每个测试用例，输出以下内容。
如果可以在40个咒语内最终拥有n个糖果，那么在第一行打印一个整数m（1≤m≤40），表示你使用的咒语总数。
在第二行打印m个整数a[1],a[2],…,a[m]（a[i]是1或2），由空格分隔，其中a[i]=1表示你在第i步使用第一个咒语，而a[i]=2表示你在第i步使用第二个咒语。
注意，你不需要最小化m，如果存在多个解，你可以输出其中任何一个。
如果不可能，在一行中输出-1。
例：
输入：
4
2
3
7
17
输出：
-1
1
2
2
2 2
4
2 1 1 1
对于n=3，你可以只使用第二个咒语一次，然后有2*1+1=3个糖果。
对于n=7，你可以使用第二个咒语两次。第一步后，你会有3个糖果。第二步后，你会有2*3+1=7个糖果。题目大意： 这个问题是关于糖果的。最初，你只有1个糖果，你想要拥有正好n个糖果。 你可以最多总共使用40次以下两种咒语，可以使用任何顺序。 1. 假设你现在有x个糖果。如果你使用第一个咒语，那么x个糖果将变成2x-1个糖果。 2. 假设你现在有x个糖果。如果你使用第二个咒语，那么x个糖果将变成2x+1个糖果。 构造一个咒语序列，使得按顺序使用它们后，你将正好有n个糖果，或者确定这是不可能的。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是t个测试用例的描述。 每个测试用例包含一行，有一个整数n（2≤n≤10^9）——需要的糖果的最终数量。 输出数据格式： 对于每个测试用例，输出以下内容。 如果可以在40个咒语内最终拥有n个糖果，那么在第一行打印一个整数m（1≤m≤40），表示你使用的咒语总数。 在第二行打印m个整数a[1],a[2],…,a[m]（a[i]是1或2），由空格分隔，其中a[i]=1表示你在第i步使用第一个咒语，而a[i]=2表示你在第i步使用第二个咒语。 注意，你不需要最小化m，如果存在多个解，你可以输出其中任何一个。 如果不可能，在一行中输出-1。 例： 输入： 4 2 3 7 17 输出： -1 1 2 2 2 2 4 2 1 1 1 对于n=3，你可以只使用第二个咒语一次，然后有2*1+1=3个糖果。 对于n=7，你可以使用第二个咒语两次。第一步后，你会有3个糖果。第二步后，你会有2*3+1=7个糖果。