27178번 - Максимизация выигрыша 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 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}$ |
예제 입력 1
170 15
예제 출력 1
710
예제 입력 2
170 600
예제 출력 2
170
예제 입력 3
314599 17713
예제 출력 3
931459
예제 입력 4
001 1000
예제 출력 4
001
노트
В первом примере после обмена цифр $1$ и $7$ получается число $710$, выигрыш равен $710-15=695$.
Во втором примере менять цифры местами не выгодно, если оставить число как есть, выигрыш равен $170$, а если поменять, то выигрыш будет равен $710-600=110 < 170$.
채점 및 기타 정보
- 예제는 채점하지 않는다.