1009B.md (1768B)
1 Source: https://codeforces.com/problemset/problem/1009/B 2 3 B. Minimum Ternary String 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 are given a ternary string (it is a string which consists only of characters '0', '1' and '2'). 22 23 You can swap any two adjacent (consecutive) characters '0' and '1' (i.e. replace "01" with "10" or vice versa) or any two adjacent (consecutive) characters '1' and '2' (i.e. replace "12" with "21" or vice versa). 24 25 For example, for string "010210" we can perform the following moves: 26 27 * "010210" $\rightarrow$ "100210"; 28 * "010210" $\rightarrow$ "001210"; 29 * "010210" $\rightarrow$ "010120"; 30 * "010210" $\rightarrow$ "010201". 31 32 Note than you cannot swap "02" $\rightarrow$ "20" and vice versa. You cannot perform any other operations with the given string excluding described above. 33 34 You task is to obtain the minimum possible (lexicographically) string by using these swaps arbitrary number of times (possibly, zero). 35 36 String $a$ is lexicographically less than string $b$ (if strings $a$ and $b$ have the same length) if there exists some position $i$ ($1 \le i \le |a|$, where $|s|$ is the length of the string $s$) such that for every $j \lt i$ holds $a_j = b_j$, and $a_i \lt b_i$. 37 38 Input 39 40 The first line of the input contains the string $s$ consisting only of characters '0', '1' and '2', its length is between $1$ and $10^5$ (inclusive). 41 42 Output 43 44 Print a single string — the minimum possible (lexicographically) string you can obtain by using the swaps described above arbitrary number of times (possibly, zero). 45 46 Examples 47 48 Input 49 50 ``` 51 100210 52 ``` 53 54 Output 55 56 ``` 57 001120 58 ``` 59 60 Input 61 62 ``` 63 11222121 64 ``` 65 66 Output 67 68 ``` 69 11112222 70 ``` 71 72 Input 73 74 ``` 75 20 76 ``` 77 78 Output 79 80 ``` 81 20 82 ```