codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```