- Описание
- Отправленные решения
24. Достопримечательности
Тур по городу N для Кати, Маши и Наташи будет удачным, если они посмотрят самые ожидаемые достопримечательности в нужном порядке. Составьте кратчайшую последовательность достопримечательностей для посещения, чтобы пожелания были выполнены.
Даны три последовательности чисел. В любой из последовательностей числа могут повторяться.
Вам нужно найти супер-последовательность. Супер-последовательность — это последовательность минимальной длины, чтобы в ней были все три последовательности непрерывными фрагментами.
Формат ввода
Ввод состоит из трёх строк. Первый элемент каждой строки () -- число элементов в -й последовательности. Далее идут положительных чисел, не превосходящих 100, -- элементы последовательности. Все числа в строках разделены пробелами.
Формат вывода
Первая строка вывода содержит одно число -- длина супер-последовательности.
Вторая строка содержит разделенных пробелами чисел -- элементы супер-последовательности.
Примечание
Заметим, что в первом примере сначала можно удовлетворить потребность Кати (посетить достопримечательности 1 и 2). Затем удовлетворить потребность Маши (2 и 3 достопримечательности). При этом, так как 2-ая достопримечательность была посещена последней, то мы можем продолжить осмотр и посетить только 3 достопримечательность). Аналогично для Наташи.
Во втором примере можно пойти по плану Наташи, тогда Маша и Катя автоматически пройдут предполагаемый маршрут.
Ограничения
Ограничение времени
1 с
Ограничение памяти
256 МБ
Пример 1
2 1 2
2 2 3
2 3 1
4
1 2 3 1
Пример 2
1 2
2 1 2
3 3 1 2
3
3 1 2
Пример 3
5 1 2 3 4 5
4 9 10 11 12
5 5 6 7 8 9
12
1 2 3 4 5 6 7 8 9 10 11 12