k-th equality (Codeforces 1835A)
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):
import collections
import heapq
import sys
import math
import itertools
import bisect
from io import BytesIO, IOBase
import os
import copy

def vsInput():
    sys.stdin = open('inputf.in', 'r')
    sys.stdout = open('outputf.out', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
    return sys.stdin.readline().rstrip('\r\n')

def value():
    return tuple(map(int, input().split()))

def inlt():
    return [int(i) for i in input().split()]

def inp():
    return int(input())

def insr():
    return input()

def stlt():
    return [i for i in input().split()]

def SieveOfEratosthenes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    l = []
    while p * p <= n:
        if prime[p] == True:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    for p in range(2, n + 1):
        if prime[p]:
            l.append(p)
        else:
            continue
    return l

def isPrime(n):
    prime_flag = 0
    if n > 1:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                prime_flag = 1
                break
        if prime_flag == 0:
            return True
        else:
            return False
    else:
        return False

def gcdofarray(a):
    x = 0
    for p in a:
        x = math.gcd(x, p)
    return x

def printDivisors(n):
    i = 1
    ans = []
    while i <= math.sqrt(n):
        if n % i == 0:
            if n / i == i:
                ans.append(i)
            else:
                ans.append(i)
                ans.append(n // i)
        i = i + 1
    ans.sort()
    return ans

def binaryToDecimal(n):
    return int(n, 2)

def countTriplets(a, n):
    s = set()
    for i in range(n):
        s.add(a[i])
    count = 0
    for i in range(n):
        for j in range(i + 1, n, 1):
            xr = a[i] ^ a[j]
            if xr in s and xr != a[i] and (xr != a[j]):
                count += 1
    return int(count // 3)

def countOdd(L, R):
    N = (R - L) // 2
    if R % 2 != 0 or L % 2 != 0:
        N += 1
    return N

def isPalindrome(s):
    return s == s[::-1]

def sufsum(a):
    test_list = a.copy()
    test_list.reverse()
    n = len(test_list)
    for i in range(1, n):
        test_list[i] = test_list[i] + test_list[i - 1]
    return test_list

def prsum(b):
    a = b.copy()
    for i in range(1, len(a)):
        a[i] += a[i - 1]
    return a

def badachotabadachota(nums):
    nums.sort()
    i = 0
    j = len(nums) - 1
    ans = []
    cc = 0
    while len(ans) != len(nums):
        if cc % 2 == 0:
            ans.append(nums[j])
            j -= 1
        else:
            ans.append(nums[i])
            i += 1
        cc += 1
    return ans

def chotabadachotabada(nums):
    nums.sort()
    i = 0
    j = len(nums) - 1
    ans = []
    cc = 0
    while len(ans) != len(nums):
        if cc % 2 == 1:
            ans.append(nums[j])
            j -= 1
        else:
            ans.append(nums[i])
            i += 1
        cc += 1
    return ans

def primeFactors(n):
    ans = []
    while n % 2 == 0:
        ans.append(2)
        n = n // 2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            ans.append(i)
            n = n // i
    if n > 2:
        ans.append(n)
    return ans

def closestMultiple(n, x):
    if x > n:
        return x
    z = int(x / 2)
    n = n + z
    n = n - n % x
    return n

def getPairsCount(arr, n, sum):
    m = [0] * 1000
    for i in range(0, n):
        m[arr[i]] += 1
    twice_count = 0
    for i in range(0, n):
        twice_count += m[int(sum - arr[i])]
        if int(sum - arr[i]) == arr[i]:
            twice_count -= 1
    return int(twice_count / 2)

def remove_consec_duplicates(test_list):
    res = [i[0] for i in itertools.groupby(test_list)]
    return res

def BigPower(x, y, p):
    res = 1
    x = x % p
    if x == 0:
        return 0
    while y > 0:
        if y & 1 == 1:
            res = res * x % p
        y = y >> 1
        x = x * x % p
    return res % p

def nextPowerOf2(n):
    count = 0
    if n and (not n & n - 1):
        return n
    while n != 0:
        n >>= 1
        count += 1
    return 1 << count

def multiply(x, res, res_size):
    carry = 0
    i = 0
    while i < res_size:
        prod = res[i] * x + carry
        res[i] = prod % 10
        carry = prod // 10
        i = i + 1
    while carry:
        res[res_size] = carry % 10
        carry = carry // 10
        res_size = res_size + 1
    return res_size

def Kadane(a, size):
    max_so_far = -1e+18 - 1
    max_ending_here = 0
    for i in range(0, size):
        max_ending_here = max_ending_here + a[i]
        if max_so_far < max_ending_here:
            max_so_far = max_ending_here
        if max_ending_here < 0:
            max_ending_here = 0
    return max_so_far

def highestPowerof2(n):
    res = 0
    for i in range(n, 0, -1):
        if i & i - 1 == 0:
            res = i
            break
    return res

def MEX(nList, start):
    nList = set(nList)
    mex = start
    while mex in nList:
        mex += 1
    return mex

def getClosest(val1, val2, target):
    if target - val1 >= val2 - target:
        return val2
    else:
        return val1

def tobinary(a):
    return bin(a).replace('0b', '')

def nextPerfectSquare(N):
    nextN = math.floor(math.sqrt(N)) + 1
    return nextN * nextN

def modFact(n, p):
    result = 1
    for i in range(1, n + 1):
        result *= i
        result %= p
    return result

def maxsubarrayproduct(arr):
    n = len(arr)
    max_ending_here = 1
    min_ending_here = 1
    max_so_far = 0
    flag = 0
    for i in range(0, n):
        if arr[i] > 0:
            max_ending_here = max_ending_here * arr[i]
            min_ending_here = min(min_ending_here * arr[i], 1)
            flag = 1
        elif arr[i] == 0:
            max_ending_here = 1
            min_ending_here = 1
        else:
            temp = max_ending_here
            max_ending_here = max(min_ending_here * arr[i], 1)
            min_ending_here = temp * arr[i]
        if max_so_far < max_ending_here:
            max_so_far = max_ending_here
    if flag == 0 and max_so_far == 0:
        return 0
    return max_so_far

def ncr(n, r, p):
    num = den = 1
    for i in range(r):
        num = num * (n - i) % p
        den = den * (i + 1) % p
    return num * pow(den, p - 2, p) % p

def sqrtl(x):
    if x == 0 or x == 1:
        return x
    start = 1
    end = x // 2
    while start <= end:
        mid = (start + end) // 2
        if mid * mid == x:
            return mid
        if mid * mid < x:
            start = mid + 1
            ans = mid
        else:
            end = mid - 1
    return ans

def ceill(a, b):
    return a // b + int(a % b != 0)

def LcmOfArray(arr, idx):
    if idx == len(arr) - 1:
        return arr[idx]
    a = arr[idx]
    b = LcmOfArray(arr, idx + 1)
    return int(a * b / math.gcd(a, b))

def inv(i, m):
    if i <= 1:
        return i
    else:
        return m - m / i * inv(m % i, m) % m
alphabets = list('abcdefghijklmnopqrstuvwxyz')
vowels = list('aeiou')
MOD1 = int(1000000000.0 + 7)
MOD2 = 998244353
INF = 1000000000
testcases = 1
testcases = inp()
for _ in range(testcases):
    (a, b, c, k) = inlt()
    minA = 10 ** (a - 1)
    maxA = 10 ** a - 1
    buu = 1
    for A in range(minA, maxA + 1):
        minB = max(10 ** (b - 1), 10 ** (c - 1) - A)
        maxB = min(10 ** b - 1, 10 ** c - A - 1)
        if minB > maxB:
            continue
        if k <= maxB - minB + 1:
            print('{} + {} = {}'.format(A, minB + k - 1, A + minB + k - 1))
            buu = 0
            break
        k -= maxB - minB + 1
    if buu:
        print(-1)

Solution (Python):
def k_th_equality(A: int, B: int, C: int, k: int) -> str:
    (start_a, end_a) = (10 ** (A - 1), 10 ** A - 1)
    (start_b, end_d) = (10 ** (B - 1), 10 ** B - 1)
    (start_c, end_c) = (10 ** (C - 1), 10 ** C - 1)
    for a in range(start_a, end_a + 1):
        lo = max(start_b, start_c - a)
        hi = min(end_d, end_c - a)
        cnt = max(0, hi - lo + 1)
        if k <= cnt:
            return f'{a} + {lo + k - 1} = {a + lo + k - 1}'
        k -= cnt
    else:
        return '-1'
for _ in range(int(input())):
    (A, B, C, k) = list(map(int, input().split()))
    print(k_th_equality(A, B, C, k))

Solution (Python):
t = int(input())
for _ in range(t):
    (a, b, c, k) = map(int, input().split())
    good = False
    for i in range(10 ** (a - 1), 10 ** a):
        left = max(pow(10, b - 1), pow(10, c - 1) - i)
        right = min(pow(10, b) - 1, pow(10, c) - i - 1)
        if left > right:
            continue
        have = right - left + 1
        if k <= have:
            good = True
            print(str(i) + ' + ' + str(left + k - 1) + ' = ' + str(i + left + k - 1))
            break
        else:
            k -= have
    if not good:
        print(-1)