Cute Sequences (Codeforces 1166D)
Tags: Greedy, binary search

Given a positive integer $$$m$$$, we say that a sequence $$$x_1, x_2, \dots, x_n$$$ of positive integers is $$$m$$$-cute if for every index $$$i$$$ such that $$$2 \le i \le n$$$ it holds that $$$x_i = x_{i - 1} + x_{i - 2} + \dots + x_1 + r_i$$$ for some positive integer $$$r_i$$$ satisfying $$$1 \le r_i \le m$$$.You will be given $$$q$$$ queries consisting of three positive integers $$$a$$$, $$$b$$$ and $$$m$$$. For each query you must determine whether or not there exists an $$$m$$$-cute sequence whose first term is $$$a$$$ and whose last term is $$$b$$$. If such a sequence exists, you must additionally find an example of it.

Input: The first line contains an integer number $$$q$$$ ($$$1 \le q \le 10^3$$$) — the number of queries.Each of the following $$$q$$$ lines contains three integers $$$a$$$, $$$b$$$, and $$$m$$$ ($$$1 \le a, b, m \le 10^{14}$$$, $$$a \leq b$$$), describing a single query.

Output: For each query, if no $$$m$$$-cute sequence whose first term is $$$a$$$ and whose last term is $$$b$$$ exists, print $$$-1$$$.Otherwise print an integer $$$k$$$ ($$$1 \le k \leq 50$$$), followed by $$$k$$$ integers $$$x_1, x_2, \dots, x_k$$$ ($$$1 \le x_i \le 10^{14}$$$). These integers must satisfy $$$x_1 = a$$$, $$$x_k = b$$$, and that the sequence $$$x_1, x_2, \dots, x_k$$$ is $$$m$$$-cute.It can be shown that under the problem constraints, for each query either no $$$m$$$-cute sequence exists, or there exists one with at most $$$50$$$ terms.If there are multiple possible sequences, you may print any of them.

Note: Consider the sample. In the first query, the sequence $$$5, 6, 13, 26$$$ is valid since $$$6 = 5 + \bf{\color{blue} 1}$$$, $$$13 = 6 + 5 + {\bf\color{blue} 2}$$$ and $$$26 = 13 + 6 + 5 + {\bf\color{blue} 2}$$$ have the bold values all between $$$1$$$ and $$$2$$$, so the sequence is $$$2$$$-cute. Other valid sequences, such as $$$5, 7, 13, 26$$$ are also accepted.In the second query, the only possible $$$1$$$-cute sequence starting at $$$3$$$ is $$$3, 4, 8, 16, \dots$$$, which does not contain $$$9$$$.

Sample Inputs:
2
5 26 2
3 9 1

Sample Outputs:
4 5 6 13 26
-1

Solution (Python):
for _ in range(int(input())):
    (a, b, m) = [int(i) for i in input().split()]
    if a == b:
        print('1 ' + str(a))
        continue
    l = a + 1
    r = a + m
    cnt = 1
    while r < b:
        l += l
        r += r
        cnt += 1
    if l > b:
        print(-1)
        continue
    ls = [1] * cnt
    p2 = [2 ** (cnt - 2 - i) for i in range(cnt - 1)] + [1]
    for i in range(cnt):
        tmp = min((b - l) // p2[i], m - 1)
        ls[i] += tmp
        l += tmp * p2[i]
    ans = [a]
    ps = a
    for i in ls:
        a = ps + i
        ps += a
        ans += [a]
    print(str(cnt + 1) + ' ' + ' '.join((str(i) for i in ans)))

Solution (Python):
q = int(input())
for u in range(q):
    (a, b, m) = map(int, input().split())
    ranges = [(a, a)]
    bigsum = a
    smlsum = a
    while ranges[-1][1] < b:
        ranges.append((smlsum + 1, bigsum + m))
        smlsum = 2 * smlsum + 1
        bigsum = 2 * bigsum + m
    if b < ranges[-1][0]:
        print(-1)
    else:
        seq = [a]
        leng = len(ranges)
        power = 2 ** (leng - 3)
        curr = (a + 1) * 2 ** (leng - 2)
        sumi = a
        for i in range(leng - 2):
            seq.append(sumi + max(min((b - curr) // power + 1, m), 1))
            power //= 2
            sumi += seq[-1]
            curr = (sumi + 1) * 2 ** (leng - i - 3)
        if b != seq[-1]:
            seq.append(b)
        out = [leng] + seq
        out = [str(guy) for guy in out]
        print(' '.join(out))

Solution (Python):
q = int(input())
for _ in range(q):
    (a, b, m) = map(int, input().split())
    if a == b:
        print(1, a)
        continue
    a1 = a + 1
    am = a + m
    for i in range(49):
        if a1 <= b <= am:
            n = i + 2
            s = 0
            ans = [a, *[0] * (n - 1)]
            for j in range(1, n):
                s += ans[j - 1]
                ans[j] = s + 1
            diff = b - ans[-1]
            sr = 0
            ss = 0
            for j in range(1, n):
                p = int(max(1, 2 ** (n - 2 - j)))
                r = min(diff // p, m - 1)
                ss = sr + r
                sr += ss
                ans[j] += ss
                diff -= r * p
            print(n, ' '.join(map(str, ans)))
            break
        a1 *= 2
        am *= 2
    else:
        print(-1)