1230B.md (1363B)
1 Source: https://codeforces.com/problemset/problem/1230/B 2 3 B. Ania and Minimizing 4 5 time limit per test 6 7 1 second 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 Ania has a large integer $S$. Its decimal representation has length $n$ and doesn't contain any leading zeroes. Ania is allowed to change at most $k$ digits of $S$. She wants to do it in such a way that $S$ still won't contain any leading zeroes and it'll be minimal possible. What integer will Ania finish with? 22 23 Input 24 25 The first line contains two integers $n$ and $k$ ($1 \leq n \leq 200\,000$, $0 \leq k \leq n$) — the number of digits in the decimal representation of $S$ and the maximum allowed number of changed digits. 26 27 The second line contains the integer $S$. It's guaranteed that $S$ has exactly $n$ digits and doesn't contain any leading zeroes. 28 29 Output 30 31 Output the minimal possible value of $S$ which Ania can end with. Note that the resulting integer should also have $n$ digits. 32 33 Examples 34 35 Input 36 37 ``` 38 5 3 39 51528 40 ``` 41 42 Output 43 44 ``` 45 10028 46 ``` 47 48 Input 49 50 ``` 51 3 2 52 102 53 ``` 54 55 Output 56 57 ``` 58 100 59 ``` 60 61 Input 62 63 ``` 64 1 1 65 1 66 ``` 67 68 Output 69 70 ``` 71 0 72 ``` 73 74 Note 75 76 A number has leading zeroes if it consists of at least two digits and its first digit is $0$. For example, numbers $00$, $00069$ and $0101$ have leading zeroes, while $0$, $3000$ and $1010$ don't have leading zeroes.