1606C.md (1598B)
1 Source: https://codeforces.com/problemset/problem/1606/C 2 3 C. Banknotes 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 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. 24 25 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) \gt k$). 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — number of test cases. 30 31 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10; 1 \le k \le 10^9$). 32 33 The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 = a_1 \lt a_2 \lt \dots \lt a_n \le 9$). 34 35 Output 36 37 For each test case, print one integer — the minimum positive number of burles $s$ that cannot be represented with $k$ or fewer banknotes. 38 39 Example 40 41 Input 42 43 ``` 44 4 45 3 13 46 0 1 2 47 2 777 48 0 4 49 3 255 50 0 1 3 51 10 1000000000 52 0 1 2 3 4 5 6 7 8 9 53 ``` 54 55 Output 56 57 ``` 58 59 59 778 60 148999 61 999999920999999999 62 ```