eolymp
bolt
Try our new interface for solving problems
Problems

Тетрис

Тетрис

Тинки-Винки играет в модулярный тетрис. Поле состоит из \textbf{N} столбиков, в каждом из которых может находится от нуля до трех кубиков. После того, как в столбике оказывается четвертый кубик, все четыре кубика исчезают. За один ход игрок может выбрать произвольное количество от \textbf{1} до \textbf{N} последовательных столбиков, на которые упадет по одному кубику, как изображено на рисунке. Тинки-Винки хочет, начиная с имеющейся конфигурации кубиков на поле, как можно быстрее достичь определенной целевой конфигурации. \includegraphics{https://static.e-olymp.com/content/f3/f399924fecb18a35fbc7699ecce0d64bae71459e.jpg} Напишите программу, которая по информации о количестве столбиков на поле, начальной и целевой конфигурации кубиков определит наименьшее количество ходов, которые должен сделать Тинки-Винки. \InputFile В первой строке содержится целое число \textbf{N }(\textbf{1 }≤ \textbf{N }≤ \textbf{1000}) - количество столбиков на поле тетриса. Во сторой строке содержится \textbf{N }целых чисел от \textbf{0 }до \textbf{3}, которые задают начальную конфигурацию кубиков на поле. В третьей строке содержится \textbf{N} целых чисел от \textbf{0 }до \textbf{3}, которые задают конечную конфигурацию кубиков. Начальная и конечная конфигурации не совпадают. \OutputFile Вывести одно целое число - минимальное возможное количество ходов Тинки-Винки для достижения целевой конфигурации.
Time limit 0.5 seconds
Memory limit 256 MiB
Input example #1
5
2 1 3 0 3
2 2 0 1 0
Output example #1
1
Author Sergey Nagin
Source 2013 XXVI All-Ukrainian Informatics Olympiad, Lugansk, March 17 - 21, Round 2