| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 67 | 18 | 15 | 28.846% |
Дано целое неотрицательное число $x,ドル состоящее из $n$ десятичных цифр. В нём можно произвольное число раз поменять местами две соседние цифры. За каждый обмен начисляется штраф равный $y$. После выполнения обменов начисляется бонус, равный получившемуся из $x$ числу $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$ и может содержать ведущие нули.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 27 | $n \le 9,ドル $y \le 10^8$ |
| 2 | 13 | $n \le 20,ドル $y \le 10^8$ |
| 3 | 19 | $n \le 10^5,ドル $y = 1$ |
| 4 | 25 | $n \le 10^5,ドル $y \le 10^8,ドル все цифры $x$ равны 1ドル$ или 2ドル$ |
| 5 | 8 | $n \le 10^5$ & $y \le 10^8$ |
| 6 | 8 | $n \le 10^5$ & $y \le 10^{16}$ |
170 15
710
170 600
170
314599 17713
931459
001 1000
001
В первом примере после обмена цифр 1ドル$ и 7ドル$ получается число 710ドル,ドル выигрыш равен 710ドル-15=695$.
Во втором примере менять цифры местами не выгодно, если оставить число как есть, выигрыш равен 170ドル,ドル а если поменять, то выигрыш будет равен 710ドル-600=110 < 170$.