codeforces-scrape

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

1730C.md (1814B)


      1 Source: https://codeforces.com/problemset/problem/1730/C
      2 
      3 C. Minimum Notation
      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 You have a string $s$ consisting of digits from $0$ to $9$ inclusive. You can perform the following operation any (possibly zero) number of times:
     22 
     23 * You can choose a position $i$ and delete a digit $d$ on the $i$-th position. Then insert the digit $\min{(d + 1, 9)}$ on any position (at the beginning, at the end or in between any two adjacent digits).
     24 
     25 What is the lexicographically smallest string you can get by performing these operations?
     26 
     27 A string $a$ is lexicographically smaller than a string $b$ of the same length if and only if the following holds:
     28 
     29 * in the first position where $a$ and $b$ differ, the string $a$ has a smaller digit than the corresponding digit in $b$.
     30 
     31 Input
     32 
     33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the test cases follow.
     34 
     35 Each test case consists of a single line that contains one string $s$ ($1 \le |s| \le 2 \cdot 10^5$) — the string consisting of digits. Please note that $s$ is just a string consisting of digits, so leading zeros are allowed.
     36 
     37 It is guaranteed that the sum of lengths of $s$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 Print a single string — the minimum string that is possible to obtain.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 4
     49 
     50 04829
     51 
     52 9
     53 
     54 01
     55 
     56 314752277691991
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 02599
     63 9
     64 01
     65 111334567888999
     66 ```
     67 
     68 Note
     69 
     70 In the first test case:
     71 
     72 * Delete $8$ and insert $9$ at the end of the notation. The resulting notation is $04299$.
     73 * Delete $4$ and insert $5$ in the $3$-rd position of the notation. The resulting notation is $02599$.
     74 
     75 Nothing needs to be done in the second and third test cases.