| Author: | Антон Карабанов | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 512 Mb | |
| Output file: | Standard output |
The blackboard in the math classroom had number n written on it. There were no zeros anywhere in the number. While passing along, Timofey decided to play a joke and swapped neighboring digits in the number k times. What is the largest possible resulting number?
Input contains integers n and k, one per line.
Output a single integer — problem answer.
11 ≤ n ≤ 10250
k ≤ 109
In the first sample n = 97 and a single swap, giving 79.
In the second sample it is optimal to move three to the first place and get 312
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|
Последовательно будем максимизировать цифры на каждой позиции (перебор), пока хватает ходов-замен. Для каждой позиции слева направо будем искать наибольшую цифру на позиции от текущей до наименьшей из длины строки и количества возможных замен. Осуществив замену, переместим найденную цифру на данную позицию, уменьшим количество замен на расстояние между позициями и перейдем к следующей.