06/04/2025 18:53:20

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2357. Потерянная строка

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Наибольшей общей подпоследовательностью (LCS) двух строк

$A$ и

$B$ называется строка, которая является подпоследовательностью обеих строк и имеет наибольшую длину среди таких строк. Например, строка "et" является LCS строк "petr"и "best". Может быть несколько различных строк, являющихся LCS.

Петя изучает алгоритм для нахождения LCS. Петя нашел длину LCS двух строк

$A$ и

$B$ , но потом потерял строку

$B$ . Строки

$A$ и

$B$ имели одинаковую длину и состояли из строчных латинских букв. Для заданной строки

$A$ и длины LCS

$K$ помогите Пете подобрать строку

$B$ такую, чтобы длина LCS строк

$A$ и

$B$ была равна

$K$ .

Первая строка ввода содержит два целых числа – длина строка

$N$ (

$1\ ≤\ N\ ≤\ 2000$ ) и длина LCS

$K$ (

$0≤\ K\ ≤2000$ ). Втроая строка ввода содержит

$N$ строчных латинских букв – строку

$A$ .

Вывести возможную строку

$B$ из

$N$ строчных латинских букв. Если Петя ошибся при вычислении длины LCS, то вывести сообщение WRONGANSWER.

Пример ввода 1

4 2
petr

Вывод для примера 1

best

Пример ввода 2

4 5
petr

Вывод для примера 2

WRONGANSWER