Phoenix and Science
Contest: Codeforces Round 638 (Div. 2)
Difficulty rating: 1900
Tags: binary search, constructive algorithms, greedy, implementation, math

Phoenix has decided to become a scientist! He is currently investigating the growth of bacteria.

Initially, on day $$$1$$$, there is one bacterium with mass $$$1$$$.

Every day, some number of bacteria will split (possibly zero or all). When a bacterium of mass $$$m$$$ splits, it becomes two bacteria of mass $$$\frac{m}{2}$$$ each. For example, a bacterium of mass $$$3$$$ can split into two bacteria of mass $$$1.5$$$.

Also, every night, the mass of every bacteria will increase by one.

Phoenix is wondering if it is possible for the total mass of all the bacteria to be exactly $$$n$$$. If it is possible, he is interested in the way to obtain that mass using the minimum possible number of nights. Help him become the best scientist!

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^9$$$) — the sum of bacteria masses that Phoenix is interested in.

Output format:
For each test case, if there is no way for the bacteria to exactly achieve total mass $$$n$$$, print -1. Otherwise, print two lines.

The first line should contain an integer $$$d$$$  — the minimum number of nights needed.

The next line should contain $$$d$$$ integers, with the $$$i$$$-th integer representing the number of bacteria that should split on the $$$i$$$-th day.

If there are multiple solutions, print any.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the following process results in bacteria with total mass $$$9$$$:

- Day $$$1$$$: The bacterium with mass $$$1$$$ splits. There are now two bacteria with mass $$$0.5$$$ each.
- Night $$$1$$$: All bacteria's mass increases by one. There are now two bacteria with mass $$$1.5$$$.
- Day $$$2$$$: None split.
- Night $$$2$$$: There are now two bacteria with mass $$$2.5$$$.
- Day $$$3$$$: Both bacteria split. There are now four bacteria with mass $$$1.25$$$.
- Night $$$3$$$: There are now four bacteria with mass $$$2.25$$$.

$$$ $$$

In the second test case, the following process results in bacteria with total mass $$$11$$$:

- Day $$$1$$$: The bacterium with mass $$$1$$$ splits. There are now two bacteria with mass $$$0.5$$$.
- Night $$$1$$$: There are now two bacteria with mass $$$1.5$$$.
- Day $$$2$$$: One bacterium splits. There are now three bacteria with masses $$$0.75$$$, $$$0.75$$$, and $$$1.5$$$.
- Night $$$2$$$: There are now three bacteria with masses $$$1.75$$$, $$$1.75$$$, and $$$2.5$$$.
- Day $$$3$$$: The bacteria with mass $$$1.75$$$ and the bacteria with mass $$$2.5$$$ split. There are now five bacteria with masses $$$0.875$$$, $$$0.875$$$, $$$1.25$$$, $$$1.25$$$, and $$$1.75$$$.
- Night $$$3$$$: There are now five bacteria with masses $$$1.875$$$, $$$1.875$$$, $$$2.25$$$, $$$2.25$$$, and $$$2.75$$$.

$$$ $$$

In the third test case, the bacterium does not split on day $$$1$$$, and then grows to mass $$$2$$$ during night $$$1$$$.

Example input:
3
9
11
2

Example output:
3
1 0 2 
3
1 1 2
1
0

Editorial:
There exists many constructive solutions, here is one I think is very elegant. We will try to approach the problem by considering how much the total mass increases every night. If there are $$$x$$$ bacteria some day before the splitting, that night can have a mass increase between $$$x$$$ and $$$2x$$$ inclusive (depending on how many bacteria split that day).
Therefore, we can reword the problem as follows: construct a sequence $$$a$$$ of minimal length $$$a_0=1, a_1, \dots, a_k$$$ such that $$$a_i \le a_{i+1} \le 2a_i$$$ and the sum of $$$a_i$$$ is $$$n$$$. To minimize the length of sequence $$$a$$$, we will start building our sequence with $$$1, 2, \dots, 2^x$$$ such that the total sum $$$s$$$ is less than or equal to $$$n$$$. If the total sum is $$$n$$$, we are done. Otherwise, we insert $$$n-s$$$ into our sequence and sort. This gives a valid sequence of minimal length.
To transform our sequence $$$a$$$ into the answer, we can just print the differences $$$a_i-a_{i-1}$$$ because the number of bacteria that split during the day is equal to how much the mass increase changes.
Time complexity for each test case: $$$O(\log{n})$$$, if you sort by insertion