| Author: | Антон Карабанов | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
On the board, a natural number is written. Timofey wants to maximize this number, meaning he wants all nines to be at the beginning, followed by eights, and so on. In one operation, he can swap any two adjacent digits of the number. Determine the minimum number of operations he needs to achieve this goal.
A single line of input contains a natural number n.
Output a single non-negative integer, the answer to the problem.
1 ≤ n ≤ 10100000.
Initial string: 2023.
1) 2032.
2) 2302.
3) 3202.
4) 3220.
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|
Решим сперва задачу для девяток. Первая из встреченных девяток должна занять первое место в новой строке, вторая - второе, и так далее.
Заведём счетчик не-девяток count. Пройдём по строке, если встречаем не-девятку, увеличиваем счетчик на 1 и приписываем эту цифру к концу новой строки, если встречаем девятку, увеличиваем ответ на текущее значение счетчика.
В получившейся новой строке остались цифры от 0 до 8, причём они следует в том же порядке, что и в исходной строке.
Решим для этой строки задачу для восьмерки и так далее.