codeforces-scrape

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

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 ```