시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 5 | 1 | 1 | 20.000% |
Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: $A = [a_1, a_2, \ldots, a_n]$ длины $n$ и $B = [b_1, b_2, \ldots, b_m]$ длины $m$.
Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как $A'$ и $B'$, а их длину как $k$. Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как $C = [c_1, c_2, \ldots, c_k]$.
Пусть, например, $n = 5$, $A = [4, 3, 3, 2, 1]$, $m = 6$, $B = [4, 1, 5, 1, 3, 2]$, от массива $A$ отбрасывается первый и последний элемент, от массива $B$ три первых. После этого массивы имеют вид $A' = [3, 3, 2]$, $B' = [1, 3, 2]$, результат их поэлементного суммирования $C = [4, 6, 4]$.
Задача Кая заключается в том, чтобы получать такие $C$, которые являются массивами-палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех $i$ числа на позициях $i$ и $k - i + 1$ совпадают.
Помогите Каю понять, какой максимальный по длине массив-палиндром он может получить в результате эксперимента.
В первой строке ввода даны два целых числа $n$ и $m$ --- количество элементов в первом и во втором массиве, соответственно ($1 \leqslant n, m \leqslant 100\,000$).
Во второй строке ввода даны $n$ целых чисел $a_{i}$ --- массив $A$ ($1 \leqslant a_i \leqslant 100$).
В третьей строке ввода даны $m$ целых чисел $b_{j}$ --- массив $B$ ($1 \leqslant b_j \leqslant 100$).
Выведите единственное целое число --- максимальное $k$, что Кай в результате эксперимента может получить массив-палиндром длины $k$.
번호 | 배점 | 제한 |
---|---|---|
1 | 13 | $n, m \le 300$ |
2 | 33 | все элементы массива $B$ одинаковые |
3 | 16 | $n \le 500$, $m \le 10^5$ |
4 | 38 |
5 6 4 3 3 2 1 4 1 5 1 3 2
3
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2022 4번