Phoenix and Science (Codeforces 1348D)
Tags: Greedy, binary search

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

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$$$.  The total mass is $$$2.25+2.25+2.25+2.25=9$$$. It can be proved that $$$3$$$ is the minimum number of nights needed. There are also other ways to obtain total mass 9 in 3 nights.$$$ $$$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$$$.  The total mass is $$$1.875+1.875+2.25+2.25+2.75=11$$$. It can be proved that $$$3$$$ is the minimum number of nights needed. There are also other ways to obtain total mass 11 in 3 nights.$$$ $$$In the third test case, the bacterium does not split on day $$$1$$$, and then grows to mass $$$2$$$ during night $$$1$$$.

Sample Inputs:
3
9
11
2

Sample Outputs:
3
1 0 2 
3
1 1 2
1
0

Solution (Python):
import bisect
A = [3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911]
B = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456]
C = [[0], [1], [0, 1], [1, 0], [1, 1], [1, 2]]
for _ in range(int(input())):
    a = int(input())
    b = bisect.bisect_left(A, a) - 2
    k = b + 3
    c = 2 ** b
    if a <= 7:
        t = C[a - 2]
    else:
        t = B[:b + 1]
        if (i := (12 * c - 1)) <= a:
            t += [2 * c, a - i]
        elif (i := (10 * c - 1)) <= a:
            t += [c, a - i]
        else:
            t += [0, a - 8 * c + 1]
    print(b + 3)
    print(*t)

Solution (Python):
import bisect
A = [2 ** x - 1 for x in range(2, 30)]
B = [2 ** x for x in range(29)]
C = [[0], [1], [0, 1], [1, 0], [1, 1], [1, 2]]
for _ in range(int(input())):
    a = int(input())
    b = bisect.bisect_left(A, a) - 2
    k = b + 3
    c = 2 ** b
    if a <= 7:
        t = C[a - 2]
    else:
        t = B[:b + 1]
        if (i := (12 * c - 1)) <= a:
            t += [2 * c, a - i]
        elif (i := (10 * c - 1)) <= a:
            t += [c, a - i]
        else:
            t += [0, a - 8 * c + 1]
    print(b + 3)
    print(*t)

Solution (Python):
def solve():
    n = int(input())
    if n == 1:
        print(0)
        return
    n = n - 1
    ans = []
    mi = 2
    now = 2
    day = 1
    while True:
        ans.append(mi)
        if n <= now:
            break
        else:
            mi *= 2
            now += mi
            day += 1
    print(day)
    delta = []
    k = now - n
    day -= 1
    while k != 0:
        if k >= 2 ** day:
            k -= 2 ** day
            delta.append(2 ** day)
        else:
            delta.append(k)
            k = 0
        day -= 1
    j = 0
    for i in range(len(ans) - 1, -1, -1):
        if j == len(delta):
            break
        ans[i] -= delta[j]
        j += 1
    now = 1
    for a in ans:
        print(a - now, end=' ')
        now = a
    print()
tt = int(input())
for _ in range(tt):
    solve()