Задача №114764. Максимизация выигрыша
Дано целое неотрицательное число \(x\), состоящее из \(n\) десятичных цифр. В нём можно произвольное число раз поменять местами две соседние цифры. За каждый обмен начисляется штраф равный \(y\). После выполнения обменов начисляется бонус, равный итоговому числу \(x_{new}\).
Таким образом, если результате \(k\) обменов получено число \(x_{new}\), выигрыш равен величине \(x_{new} - ky\). Будем называть число \(x_{new}\) оптимальным, если его можно получить из \(x\) в результате обменов, добившись таким образом максимального возможного выигрыша.
По заданным \(x\) и \(y\) определите наибольшее среди оптимальных чисел.
В первой строке дано одно целое число \(x\), состоящее из \(n\) десятичных цифр (\(1 \le n \le 100\,000\)). Число \(x\) может иметь ведущие нули.
Во второй строке дано одно целое число \(y\) — штраф за один обмен цифр (\(1 \le y \le 10^{16}\)).
Выведите единственное целое число \(x_{new}\) — наибольшее среди оптимальных чисел. Число \(x_{new}\) должно иметь длину \(n\) и может содержать ведущие нули.
| p{3.0cm}|c|c|} | Ограничения | |||||
| Подзадача | Баллы | \(n\) | \(y\) | дополнительно | Необх. подзадачи | Информация о проверке |
| 1 | 14 | \(n \le 9\) | \(y \le 10^8\) | У | первая ошибка | |
| 2 | 20 | \(n \le 20\) | \(y \le 10^8\) | У, 1 | первая ошибка | |
| 3 | 17 | \(n \le 10^5\) | \(y = 1\) | первая ошибка | ||
| 4 | 21 | \(n \le 10^5\) | \(y \le 10^8\) | все цифры \(x\) равны \(1\) или \(2\) | первая ошибка | |
| 5 | 19 | \(n \le 10^5\) | \(y \le 10^8\) | У, 1–4 | первая ошибка | |
| 6 | 9 | \(n \le 10^5\) | \(y \le 10^{16}\) | У, 1–5 | первая ошибка | |
В первом примере после обмена цифр \(1\) и \(7\) получается число \(710\), выигрыш равен \(710-15=695\).
Во втором примере менять цифры местами не выгодно, если оставить число как есть, выигрыш равен \(170\), а если поменять, то выигрыш будет равен \(710-600=110 < 170\).
170 15
710
170 600
170
314599 17713
931459
001 1000
001