- Описание
- Отправленные решения
6. НОП с восстановлением ответа
Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.
Напомним:
Последовательность $x$ называется подпоследовательностью последовательности $y$, если $x$ получается из $𝑦$ удалением нескольких (возможно, нуля или всех) элементов.
Наибольшая общая подпоследовательность - последовательность наибольшей длины, которая является подпоследовательностью обеих последовательностей.
Формат ввода
В первой строке входных данных содержится число N – длина первой последовательности (1 $\le$ N $\le$ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.
В третьей строке записано число M – длина второй последовательности (1 $\le$ M $\le$ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.
Формат вывода
Требуется вывести наибольшую общую подпоследовательность данных последовательностей, через пробел. Если таких подпоследовательностей несколько, то можно вывести любую.
Примечание
В примере 2 существует сразу три наибольшие общие подпоследовательности.
1) 1
2) 2
3) 3
Любая из них будет правильным ответом.
Ограничения
Ограничение времени
1 с
Ограничение памяти
64 МБ
Пример 1
3
1 2 3
3
2 3 1
2 3
Пример 2
3
1 2 3
3
3 2 1
1