k-th equality (Codeforces 1836C)
Tags: Math, brute force

Consider all equalities of form $$$a + b = c$$$, where $$$a$$$ has $$$A$$$ digits, $$$b$$$ has $$$B$$$ digits, and $$$c$$$ has $$$C$$$ digits. All the numbers are positive integers and are written without leading zeroes. Find the $$$k$$$-th lexicographically smallest equality when written as a string like above or determine that it does not exist.For example, the first three equalities satisfying $$$A = 1$$$, $$$B = 1$$$, $$$C = 2$$$ are   $$$1 + 9 = 10$$$,  $$$2 + 8 = 10$$$,  $$$2 + 9 = 11$$$. An equality $$$s$$$ is lexicographically smaller than an equality $$$t$$$ with the same lengths of the numbers if and only if the following holds:   in the first position where $$$s$$$ and $$$t$$$ differ, the equality $$$s$$$ has a smaller digit than the corresponding digit in $$$t$$$. 

Input: Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains integers $$$A$$$, $$$B$$$, $$$C$$$, $$$k$$$ ($$$1 \leq A, B, C \leq 6$$$, $$$1 \leq k \leq 10^{12}$$$).Each input file has at most $$$5$$$ test cases which do not satisfy $$$A, B, C \leq 3$$$.

Output: For each test case, if there are strictly less than $$$k$$$ valid equalities, output $$$-1$$$.Otherwise, output the $$$k$$$-th equality as a string of form $$$a + b = c$$$.

Note: In the first test case, the first $$$9$$$ solutions are: $$$\langle 1, 1, 2 \rangle, \langle 1, 2, 3 \rangle, \langle 1, 3, 4 \rangle, \langle 1, 4, 5 \rangle, \langle 1, 5, 6 \rangle, \langle 1, 6, 7 \rangle, \langle 1, 7, 8 \rangle, \langle 1, 8, 9 \rangle, \langle 2, 1, 3 \rangle$$$.Int the third test case, there are no solutions as the smallest possible values for $$$a$$$ and $$$b$$$ are larger than the maximal possible value of $$$c$$$ — $$$10 + 10 = 20 > 9$$$.Please note that whitespaces in the output matter.

Sample Inputs:
7
1 1 1 9
2 2 3 1
2 2 1 1
1 5 6 42
1 6 6 10000000
5 5 6 3031568815
6 6 6 1000000000000

Sample Outputs:
2 + 1 = 3
10 + 90 = 100
-1
9 + 99996 = 100005
-1
78506 + 28543 = 107049
-1

Solution (Python):
def solve(A, B, C, k):
    if max(A, B) > C:
        return -1
    (al, ar) = (10 ** (A - 1), 10 ** A - 1)
    (bl, br) = (10 ** (B - 1), 10 ** B - 1)
    (cl, cr) = (10 ** (C - 1), 10 ** C - 1)
    for a in range(al, ar + 1):
        b1 = max(bl, cl - a)
        b2 = min(br, cr - a)
        if b1 <= b2:
            if k <= b2 - b1 + 1:
                b = b1 + k - 1
                c = a + b
                return f'{a} + {b} = {c}'
            else:
                k -= b2 - b1 + 1
    return -1

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        arr = readIntArr()
        ans = solve(*arr)
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
    (a, b, c, k) = M()
    a1 = b1 = -1
    if max(a, b) > c:
        print(-1)
        continue
    x1 = 10 ** (a - 1)
    x2 = 10 ** a
    y1 = 10 ** (b - 1)
    y2 = 10 ** b
    z1 = 10 ** (c - 1)
    z2 = 10 ** c
    i = x1
    while i < x2:
        if i + y1 < z1:
            t = z1 - i
            if len(str(t)) != b:
                i += 1
                continue
            else:
                p = min(z2 - i, y2)
                if k <= p - t:
                    a1 = i
                    b1 = t + (k - 1)
                    break
                k -= p - t
        elif z1 <= i + y1 < z2:
            t = y1
            p = min(z2 - i, y2)
            if k <= p - t:
                a1 = i
                b1 = t + (k - 1)
                break
            k -= p - t
        else:
            break
        i += 1
    if a1 == -1:
        print(-1)
    else:
        print(str(a1) + ' + ' + str(b1) + ' = ' + str(a1 + b1))

Solution (Python):
import sys
rd = sys.stdin.readline
t = int(rd())
for _ in range(t):
    (a, b, c, k) = list(map(int, rd().split()))
    minc = 10 ** (c - 1)
    maxc = 10 ** c - 1
    minb = 10 ** (b - 1)
    maxb = 10 ** b - 1
    n = 0
    ansa = -1
    for i in range(10 ** (a - 1), 10 ** a):
        (m1b, m2b) = (minc - i, maxc - i)
        m1b = max(m1b, minb)
        m2b = min(m2b, maxb)
        num = max(0, m2b - m1b + 1)
        if n + num >= k:
            ansa = i
            ansb = m1b + (k - n) - 1
            ansc = ansa + ansb
            break
        else:
            n += num
    if ansa == -1:
        print(-1)
    else:
        print(str(ansa) + ' + ' + str(ansb) + ' = ' + str(ansc))