Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2357. Потерянная строка
Задачи на идеюОлимпиадные задачи на русском языке
| 14/10/2017 | Открытые личные соревнования по спортивному программированию (I) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
