Отборочный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"E" Объединение массивов
Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

Рассмотрим два массива натуральных чисел A = [a1, a2, ..., an] и B = [b1, b2, ..., bm]. Будем называть их k-объединением лексикографически минимальный массив чисел R длиной k, который разбивается на две непустые подпоследовательности, первая из которых является подпоследовательностью массива A, а вторая — подпоследовательностью массива B.

Формально говоря, необходимо найти лексикографически минимальный массив R = [r1, r2, ..., rk], для которого существуют непустые наборы индексов 1 ≤ i1, 1 < i1, 2 < ... < i1, t ≤ n и 1 < j1, 1 < j1, 2 < ... < j1, k - t ≤ m в исходных массивах, а также наборы индексов 1 ≤ i2, 1 < i2, 2 < ... < i2, t ≤ k и 1 ≤ j2, 1 < j2, 1 < ... < j2, k - t ≤ k, такие что:

  • Для любых 1 ≤ p ≤ t, 1 ≤ q ≤ k - t выполнено i2, p ≠ j2, q;
  • Для любого 1 ≤ p ≤ t выполнено ai1, p = ri1, p;
  • Для любого 1 ≤ p ≤ k - t выполнено bj1, p = rj1, p.

Например, если A = [1, 2, 1, 3, 1, 2, 1], B = [1, 2, 3, 1], а k = 9, то их k-объеднением будет R = [1, 1, 1, 1, 2, 1, 2, 3, 1] (подпоследовательность из первого массива — [1, 1, 1, 2, 1], подпоследовательность из второго массива — [1, 2, 3, 1]).

По двум данным массивам A и B, а также числу k найдите их k-объединение R.

Формат входных данных

В первой строке ввода содержится число n — размер массива A (1 ≤ n ≤ 3000).

Во второй строке содержится n чисел ai — массив A (1 ≤ ai ≤ 3000).

В третьей строке содержится число m — размер массива B (1 ≤ m ≤ 3000).

Во четвертой строке содержится m чисел bi — массив B (1 ≤ bi ≤ 3000).

В последней строке содержится число k (2 ≤ k ≤ n + m).

Формат выходных данных

Выведите k-объединение заданных во входном файле массивов.

Примеры
Входные данные
7
1 2 1 3 1 2 1
4
1 2 3 1
9
Выходные данные
1 1 1 1 2 1 2 3 1 
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.