codeforces-scrape

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

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.