Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 48921. Пазл
Темы: Паросочетания    Жадный алгоритм    Динамическое программирование    Динамическое программирование   

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

Школьники Алиса и Ибрагим — лучшие друзья. У Ибрагима скоро день рождения, и по этому поводу Алиса решила подарить ему новый пазл. Пазл можно представить в виде матрицы из \(2\) строк и \(n\) столбцов, каждый элемент которой \(0\) или \(1\). За один ход можно поменять местами два элемента, стоящие в соседних клетках.

Более формально, будем считать, что строки матриц пронумерованы сверху вниз от \(1\) до \(2\), а столбцы — слева направо от \(1\) до \(n\). Обозначим клетку на пересечении строки \(x\) и столбца \(y\) за \((x, y)\). Будем считать две клетки \((x_1, y_1)\) и \((x_2, y_2)\) соседними, если \(|x_1 - x_2| + |y_1 - y_2| = 1\).

Алисе не нравится, какой рисунок образуют клетки пазла в данный момент. Она придумала свой рисунок, с которым и планирует подарить Ибрагиму новый пазл, но для этого нужно привести пазл в соответствующее состояние.

В конце учебного года у Алисы очень плотное расписание, и она не хочет тратить на эту задачу много времени. Помогите Алисе найти минимальное количество ходов, за которое она может получить свой рисунок, или скажите, что это невозможно.

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(1 \leq n \leq 200\,000\)) — количество столбцов в пазле.

Следующие две строки описывают рисунок, образованный пазлом в данный момент. В каждой строке вводятся \(n\) целых чисел, каждое из которых равно \(0\) или \(1\).

Следующие две строки описывают желаемый рисунок Алисы в том же формате.

Формат выходных данных
Если Алиса не ошиблась и её рисунок можно получить, найдите и выведите минимальное необходимое количество ходов, иначе выведите \(-1\).

 

В первом примере из условия подойдет следующая последовательность обменов:

\((2, 1), (1, 1)\)

\((1, 2), (1, 3)\)

\((2, 2), (2, 3)\)

\((1, 4), (1, 5)\)

\((2, 5), (2, 4)\)

Можно показать, что меньшим числом обменов обойтись нельзя, поэтому ответ равен \(5\).

Во втором примере из условия никакая последовательность ходов не приводит пазл к нужному виду.