Banknotes (Codeforces 1606C)
Tags: Greedy, number theory

In Berland, $$$n$$$ different types of banknotes are used. Banknotes of the $$$i$$$-th type have denomination $$$10^{a_i}$$$ burles (burles are the currency used in Berland); the denomination of banknotes of the first type is exactly $$$1$$$.Let's denote $$$f(s)$$$ as the minimum number of banknotes required to represent exactly $$$s$$$ burles. For example, if the denominations of banknotes used in Berland are $$$1$$$, $$$10$$$ and $$$100$$$, then $$$f(59) = 14$$$: $$$9$$$ banknotes with denomination of $$$1$$$ burle and $$$5$$$ banknotes with denomination of $$$10$$$ burles can be used to represent exactly $$$9 \cdot 1 + 5 \cdot 10 = 59$$$ burles, and there's no way to do it with fewer banknotes.For a given integer $$$k$$$, find the minimum positive number of burles $$$s$$$ that cannot be represented with $$$k$$$ or fewer banknotes (that is, $$$f(s) > k$$$).

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10; 1 \le k \le 10^9$$$).The next line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 = a_1 < a_2 < \dots < a_n \le 9$$$).

Output: For each test case, print one integer — the minimum positive number of burles $$$s$$$ that cannot be represented with $$$k$$$ or fewer banknotes.


Sample Inputs:
4
3 13
0 1 2
2 777
0 4
3 255
0 1 3
10 1000000000
0 1 2 3 4 5 6 7 8 9

Sample Outputs:
59
778
148999
999999920999999999

Solution (Python):
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

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

def lli(rows):
    return [li() for _ in range(rows)]

def si():
    return input()

def ii():
    return int(input())

def ins():
    return input().split()

def merge(a, b, l1, l2):
    ans = []
    i = j = 0
    while i < l1 and j < l2:
        if a[i] < b[j]:
            ans.append(a[i])
            i += 1
        else:
            ans.append(b[j])
            j += 1
    if i != l1:
        ans += a[i:]
    if j != l2:
        ans += b[j:]
    return ans

def msort(a, n):
    if n == 1:
        return a
    if n == 2:
        return [min(a), max(a)]
    return merge(msort(a[:n // 2], n // 2), msort(a[n // 2:n], n - n // 2), n // 2, n - n // 2)
import bisect
mod = 10 ** 9 + 7

def solve():
    (n, m) = LI()
    a = LI()
    m += 1
    limit = 0
    if n == 1:
        return m
    for i in range(1, n):
        limit += 10 ** (a[i] - a[i - 1]) - 1
        if limit == m:
            return 10 ** a[i] - 1
        elif limit > m:
            x = limit - (10 ** (a[i] - a[i - 1]) - 1)
            return (m - x) * 10 ** a[i - 1] + (10 ** a[i - 1] - 1)
    return (m - limit) * 10 ** a[-1] + (10 ** a[-1] - 1)

def main():
    for _ in range(II()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
import sys

def get_ans(n, banknotes, denominations):
    banknotes += 1
    ans = 0
    for i in range(n - 1):
        can_use = ten_powers[denominations[i + 1] - denominations[i]] - 1
        notes_using = min(banknotes, can_use)
        banknotes -= notes_using
        ans += ten_powers[denominations[i]] * notes_using
        if banknotes == 0:
            break
    if banknotes > 0:
        ans += ten_powers[denominations[n - 1]] * banknotes
    return ans
input = lambda : sys.stdin.readline().rstrip('\r\n')
ten_powers = [1 for i in range(10)]
temp = 1
for i in range(1, 10):
    temp = temp * 10
    ten_powers[i] = temp
t = int(input())
for i in range(t):
    (n, banknotes) = input().split()
    (n, banknotes) = (int(n), int(banknotes))
    denominations = map(int, input().split())
    denominations = sorted(denominations)
    print(get_ans(n, banknotes, denominations))

Solution (Python):
import sys
input = sys.stdin.readline

def read_int():
    return int(input())

def int_list():
    return list(map(int, input().split()))

def str_list():
    return list(input())

def test_case():
    (n, k) = int_list()
    x = int_list()
    mn_denom = k + 1
    cur_denom_count = 0
    s = 0
    for idx in range(len(x)):
        cur_pw = x[idx]
        cur_denom = 10 ** cur_pw
        if idx < len(x) - 1:
            next_pw = x[idx + 1]
            next_denom = 10 ** next_pw
            pw_lag = next_pw - cur_pw
            to_add_limit = int('9' * pw_lag)
            if to_add_limit < mn_denom - cur_denom_count:
                s += to_add_limit * cur_denom
                cur_denom_count += to_add_limit
            else:
                s += (mn_denom - cur_denom_count) * cur_denom
                cur_denom_count += mn_denom - cur_denom_count
        else:
            to_add_count = mn_denom - cur_denom_count
            s += to_add_count * cur_denom
    print(s)

def main():
    t = read_int()
    for _ in range(t):
        test_case()
if __name__ == '__main__':
    main()