CF1810B.Candies
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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.
输入格式
Each test contains multiple test cases. The first line contains a single integer t ( 1≤t≤104 ) — the number of test cases. Their description follows.
Each test case contains one line with a single integer n ( 2≤n≤109 ) — the required final number of candies.
输出格式
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≤m≤40 ), representing the total number of spells you use.
In the second print m integers a1,a2,…,am ( ai is 1 or 2 ) separated by spaces, where ai=1 means that you use the first spell in the i -th step, while ai=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.
输入输出样例
输入#1
4 2 3 7 17
输出#1
-1 1 2 2 2 2 4 2 1 1 1
说明/提示
For n=3 , you can just use the second spell once, and then have 2⋅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⋅3+1=7 candies.