| Олимпиада 1С 2025, предметный тур |
|---|
| Finished |
Дана строка $$$s$$$. Пусть $$$t$$$ — анаграмма$$$^{\text{∗}}$$$ строки $$$s$$$.
Определим стоимость $$$t$$$ как количество строчных латинских букв $$$a, b, \ldots, z$$$, таких, что эта буква встречается в строке $$$s$$$ (тогда она встречается и в $$$t$$$), и индекс её самого левого вхождения этой буквы в строку $$$t$$$ меньше индекса самого левого вхождения в строку $$$s$$$. Для примера расчёта стоимости анаграммы обратитесь к примечанию.
Ваша задача — по заданной строке $$$s$$$ и числу $$$k$$$ найти лексикографически минимальную$$$^{\text{†}}$$$ анаграмму со стоимостью не более $$$k$$$.
$$$^{\text{∗}}$$$Строка $$$t$$$ является анаграммой строки $$$s$$$, если $$$t$$$ можно получить из $$$s$$$ перестановкой символов. Иными словами, каждая буква входит в строку $$$s$$$ и строку $$$t$$$ одинаковое число раз.
$$$^{\text{†}}$$$Строка $$$a$$$ лексикографически меньше строки $$$b$$$ ($$$a$$$ идёт раньше $$$b$$$ в алфавитном порядке), если и только если выполняется одно из двух условий:
В первой строке содержится одно число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина строки $$$s$$$.
Во второй строке содержится строка $$$s$$$ длины $$$n$$$, состоящая из строчных латинских букв.
В третьей строке содержится одно число $$$k$$$ ($$$0 \le k \le 26$$$) — ограничение на стоимость анаграммы.
Выведите одну строку — лексикографически минимальную анаграмму строки $$$s$$$ со стоимостью не более $$$k$$$.
В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие, когда строка $$$s$$$ состоит только из символов a и b, наберут не менее $$$30$$$ баллов.
Решения, корректно работающие при $$$n \le 8$$$, наберут не менее $$$30$$$ баллов.
Решения, корректно работающие при $$$n \le 1000$$$, наберут не менее $$$50$$$ баллов.
Решения, корректно работающие при $$$k=0$$$, наберут не менее $$$30$$$ баллов.
6banana1
aaabnn
6banana0
baaann
8bbaabbaa0
bbaaaabb
В первом примере s="banana", а t="aaabnn". Строка $$$t$$$ является анаграммой $$$s$$$, так как её можно получить перестановкой символов. Стоимость $$$t$$$ определяется так:
Итого, стоимость такой анаграммы равна $$$1$$$.
Во втором и третьем примере анаграммы имеют стоимость $$$0$$$.
| Name |
|---|


