1765N.md (1435B)
1 Source: https://codeforces.com/problemset/problem/1765/N 2 3 N. Number Reduction 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a positive integer $x$. 22 23 You can apply the following operation to the number: remove one occurrence of any digit in such a way that the resulting number does not contain any leading zeroes and is still a positive integer. For example, $10142$ can be converted to $1142$, $1042$, $1012$ or $1014$ (note that $0142$ is not a valid outcome); $10$ can be converted to $1$ (but not to $0$ since it is not positive). 24 25 Your task is to find the minimum positive integer that you can obtain from $x$ if you can apply the aforementioned operation exactly $k$ times. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. 30 31 The first line of each test case contains a single integer $x$ ($1 \le x \lt 10^{500000}$). 32 33 The second line contains a single integer $k$ ($0 \le k \lt |x|$), where $|x|$ is the length of the number $x$. 34 35 The sum of $|x|$ over all test cases does not exceed $5 \cdot 10^5$. 36 37 Output 38 39 For each test case, print one integer — the minimum positive number that you can obtain from $x$ if you can apply the operation exactly $k$ times. 40 41 Example 42 43 Input 44 45 ``` 46 5 47 48 10000 49 50 4 51 52 1337 53 54 0 55 56 987654321 57 58 6 59 60 66837494128 61 62 5 63 64 7808652 65 66 3 67 ``` 68 69 Output 70 71 ``` 72 1 73 1337 74 321 75 344128 76 7052 77 ```