Past: We can only take part in Div.4 contests.

Present: We can only take part in Div.5 contests.

Each number like 1234 should be written as 1000 + 200 + 30 + 4. We ignore any zero digits, so 10203 = 10000 + 200 + 3.

for testcase in range(int(input())):
    s = input()  # input as string
    ans = []
    for i, c in enumerate(s):
        if c != '0':
            ans.append(int(c) * (10 ** (len(s) - 1 - i)))

    print(len(ans))
    print(*ans)

If the task is possible, we should write either: [1, 1, ..., 1, x] or [2, 2, ..., 2, x].

This is because the requirement for the last number is that it has the same parity, and it is positive. The requirement of being positive is the same as the sum of the other numbers being as small as possible. Therefore, we make the requirement strictly easier by decreasing the other numbers by 2 (if possible.)

for testcase in range(int(input())):
    n, k = map(int, input().split())

    # 1, 1, ..., 1, last
    last = n - (k - 1)
    ans = []
    if last > 0 and last & 1 == 1:
        ans = [1] * (k - 1) + [last]

    # 2, 2, ..., 2, last
    last = n - 2 * (k - 1)
    if last > 0 and last & 1 == 0:
        ans = [2] * (k - 1) + [last]

    if ans:
        print("YES")
        print(*ans)
    else:
        print("NO")

There are three possible solutions.

Solution 1 (lifting): Say k >= n. We could remove the first n numbers from contention: k -= n — 1, and now we start counting from n + 1 instead of from n. For example, if n = 10 and k = 15, we know that in the first 10 numbers, there are 9 not divisible by 10, so we start counting from 11 with k = 15 — 9 = 6. If we did this naively, we would get TLE because k could be really big and n really small.

We could scale all the numbers involved to do this faster. For example, let's scale by 1024: if k > n * 1024, we know that in the first n * 1024 numbers, there are (n-1) * 1024 not divisible by 10, so we start counting from 1024 * n + 1 with k -= (n — 1) * 1024.

Solution 2 (binary search): Let f(x) be the number of positive integers <= x that are not divisible by n. This is a monotone increasing function and we want the first x such that f(x) == k. We can binary search for the answer.

Solution 3 (math): Write k = (n — 1) * q + r [with 0 <= q, 0 <= r < n — 1]. The first q groups of n numbers has (n-1) * q not divisible by n. If r > 0, then the k-th number is just q * n + r. If r == 0, then the k-th number is just q * n — 1.

for testcase in range(int(input())):
    n, k = map(int, input().split())

    k -= 1
    ans = 0
    for bit in range(30, -1, -1):
        take = (n - 1) * (1 << bit)
        # Let's look at the first n * (1 << bit) numbers.
        # (n - 1) * (1 << bit) of them are not divisible
        # by n.  If we could take them, then we do so.
        if k >= take:
            k -= take
            ans += n * (1 << bit)
    print(ans + k + 1)

# Alternate Solution
for testcase in range(int(input())):
    n, k = map(int, input().split())

    def f(x):
        # Among {1, 2, ..., x}, how many are
        # not divisible by n?
        return x - x // n

    # f is a monotone increasing function, and
    # we want to know the first x so that f(x) = k.
    lo, hi = 0, 2 * k + 1
    while lo < hi:
        mi = lo + hi >> 1
        if f(x) < k:
            lo = mi + 1
        else:
            hi = mi
    print(lo)

# Alternate Solution
for testcase in range(int(input())):
    n, k = map(int, input().split())
    q, r = divmod(k, n - 1)
    print(n * q + r - (r == 0))

We just simulate each turn of the game carefully. Here, the pointers i and j will represent the next candy that Alice or Bob respectively will eat if given the chance to.

for testcase in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))

    i, j = 0, n - 1
    turns = alice = bob = last = 0
    while i <= j:
        turns += 1
        eat = 0
        if turns & 1:  # Alice's turn
            while i <= j:
                eat += arr[i]; i += 1
                if eat > last: break
            alice += eat
        else:  # Bob's turn
            while i <= j:
                eat += arr[j]; j -= 1
                if eat > last: break
            bob += eat

        last = eat

    print(turns, alice, bob)

We should find all special numbers — numbers that can be written as a sum of two or more consecutive terms in the array. After, for each element of the array, we check if it is a special number.

for testcase in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))

    special = [False] * (n + 1)
    for i in range(n):
        s = arr[i]
        for j in range(i + 1, n):
            s += arr[j]
            if s > n:
                break
            special[s] = True

    print(sum(1 for x in arr if special[x]))

Notice we can replace 0 by 00 to satisfy the n0 requirement, and replace 1 by 11 to satisfy the n2 requirement.

So let's satisfy the n1 requirement: let's write 010101... first. Then replace the first 0 and first 1 with repeated zeros and ones.

For example, say n1 = 3. We write 0101 first. Now n0 = 4 and n2 = 5. We modify this to 00000 111111 0 1 (spaces added for clarity.)

Also, if there is no n1 requirement, then the string must be all zeros or all ones.

for testcase in range(int(input())):
    n0, n1, n2 = map(int, input().split())
    if n1 == 0:
        if n0:
            ans = "0" * (n0 + 1)
        else:
            ans = "1" * (n2 + 1)
    else:
        ans = ["0" * (n0 + 1), "1" * (n2 + 1)]
        for i in range(n1 - 1):
            ans.append(str(i & 1))
        ans = "".join(ans)

    print(ans)

Solution 1 (even/odd walk):

Since we shouldn't walk to adjacent numbers, let's walk along all even and all odd numbers. In general, our walk is going to start with [2, 4, 6, 8, ...] and end with [..., 7, 5, 3, 1], and we just need to handle what happens in between. We can deal with this based on cases where n is even or odd.

Solution 2 (reduce by 5):

Look at the sequence [ 1 4 2 5 3 ][ 6 9 7 10 8 ][ 11 ... ] ( brackets added for clarity ). It repeats every 5 terms. If N is very big, we could write a group of 5 terms in this way first, reducing the problem to a problem about N — 5. Afterwards, it remains to just handle N <= 8 individually.

for testcase in range(int(input())):
    n = int(input())

    if n <= 3:
        ans = [1 if n == 1 else -1]
    else:
        ans = list(range(2, n + 1, 2))
        if n & 1:  # Eg. n = 7, ans = [2, 4, 6]
            ans.append(n - 4)
            ans.append(n)
            ans.append(n - 2)
            ans.extend(range(n - 6, 0, -2))
        else:  # Eg. n = 6, ans = [2, 4, 6]
            ans.append(n - 3)
            ans.append(n - 1)
            ans.extend(range(n - 5, 0, -2))

    print(*ans)


# Alternate Solution

def solve(n):
    answers = {
        1: [1],
        2: [-1],
        3: [-1],
        4: [2, 4, 1, 3],
        5: [2, 4, 1, 3, 5],
        6: [2, 4, 6, 3, 5, 1],
        7: [2, 4, 6, 3, 7, 5, 1],
        8: [2, 4, 6, 8, 5, 7, 3, 1],
    }

    if n <= 8:
        return answers[n]

    ans = []
    floor = 0
    while floor + 8 < n:
        ans.extend(floor + x for x in (1, 4, 2, 5, 3))
        floor += 5
    ans.extend(floor + x for x in solve(n - floor))
    return ans

for testcase in range(int(input())):
    print(*solve(int(input())))