Симметричная последовательность (Python)

Question

Симметричная последовательность (Python)

И Х Знаток (293), закрыт 5 лет назад

Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:

1 2 3 4 5 4 3 2 1;

1 2 1 2 2 1 2 1.

Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.

Формат входных данных
Сначала вводится число n — количество элементов исходной последовательности (1≤n≤100).

Далее идут n чисел - элементы этой последовательности, натуральные числа от 1 до 9, каждое с новой строки.

Формат выходных данных
Выведите сначала число M - минимальное количество элементов, которое надо дописать к последовательности, а потом M чисел (каждое - от 1 до 9 ) - числа, которые надо дописать к последовательности.
Примеры
входные данные выходные данные
9 0
1
2
3
4
5
4
3
2
1

Дополнен 5 лет назад

0 в примере - выходные данные

Answer 1

Для того чтобы решить задачу за линейное время относительно длины входа (иными словами, асимптотика O(n)), нужно использовать алгоритм Кнута-Морриса-Пратта, точнее, его часть.
Здесь же зайдет квадратичное решение.
Будем добавлять по очереди в последовательность на n-ое место сначала первый элемент, затем вставим второй и т. д., пока получившаяся последовательность не станет палиндромом.
То есть:
n = int(input())
arr = []
for i in range(n): arr.append(int(input()))
i = 0
while arr != arr[::-1]:
...arr.insert(n, arr[i])
...i += 1
print(i)
print(*arr[:i][::-1])

Answer 2

# ввод
m = int(input())
arr = []
while len(arr) < m:
~~~~arr.append(int(input()))

# функция для определения палиндрома
is_pal = lambda x: x == x[::-1] if len(x) > 1 else False

# перебираем список в поисках палиндрома
arr_2 = arr[:]
for i in range(len(arr)):
~~~~if is_pal(arr_2[i:]):
~~~~~~~~arr_2 = arr_2[i:]
~~~~~~~~if arr == arr_2:
~~~~~~~~~~~~print('0')
~~~~~~~~else:
~~~~~~~~~~~~print('нужно добавить {:d} эл.: {}'.format(len(arr[:i]),' '.join(list(map(str, arr[:i][::-1])))))
~~~~~~~~break