codeforces-scrape

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

2050D.md (1617B)


      1 Source: https://codeforces.com/problemset/problem/2050/D
      2 
      3 D. Digital string maximization
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 are given a string $s$, consisting of digits from $0$ to $9$. In one operation, you can pick any digit in this string, except for $0$ or the leftmost digit, decrease it by $1$, and then swap it with the digit left to the picked.
     22 
     23 For example, in one operation from the string $1023$, you can get $1103$ or $1022$.
     24 
     25 Find the lexicographically maximum string you can obtain after any number of operations.
     26 
     27 Input
     28 
     29 The first line of the input consists of an integer $t$ ($1 \le t \le 10^4$)  — the number of test cases.
     30 
     31 Each test case consists of a single line consisting of a digital string $s$ ($1 \le |s| \le 2\cdot 10^5$), where $|s|$ denotes the length of $s$. The string does not contain leading zeroes.
     32 
     33 It is guaranteed that the sum of $|s|$ of all test cases doesn't exceed $2\cdot 10^5$.
     34 
     35 Output
     36 
     37 For each test case, print the answer on a separate line.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 6
     45 
     46 19
     47 
     48 1709
     49 
     50 11555
     51 
     52 51476
     53 
     54 9876543210
     55 
     56 5891917899
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 81
     63 6710
     64 33311
     65 55431
     66 9876543210
     67 7875567711
     68 ```
     69 
     70 Note
     71 
     72 In the first example, the following sequence of operations is suitable: $19 \rightarrow 81$.
     73 
     74 In the second example, the following sequence of operations is suitable: $1709 \rightarrow 1780 \rightarrow 6180 \rightarrow 6710$.
     75 
     76 In the fourth example, the following sequence of operations is suitable: $51476 \rightarrow 53176 \rightarrow 53616 \rightarrow 53651 \rightarrow 55351 \rightarrow 55431$.