codeforces-scrape

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

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