eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Шоколад

Шоколад

Шоколад, который производит кондитерская компания <<Ням & Ням>>, имеет вид длинной плитки \textbf{1х}\textit{\textbf{N}}, состоящей из \textit{N} квадратиков. На каждом квадратике изображен один из \textit{\textbf{N}} известных кондитеров, причем на разных шоколадках, которые производит компания, изображены одни и те же \textit{\textbf{N}} кондитеров, только в разном порядке. \textbf{Задание} Напишите программу, которая для заданного порядка портретов на двух плитках шоколада определяет, на какое наименьшее количество частей придется разломать первую плитку, чтобы путем переставления частей из нее можно было образовать вторую. Ломать плитку разрешается только по границам квадратиков, а переворачивать плитку или ее части нельзя. \textbf{Входные данные} Первая строка входного файла содержит натуральное число \textit{\textbf{N}}\textbf{ (2 ≤ }\textit{\textbf{N }}\textbf{≤ 10^5)}, задающее размер плитки шоколада, то есть количество квадратиков в ней. Все кондитеры пронумерованы числами от 1 до \textit{N}. Вторая и третья строки файла содержат по \textit{\textbf{N}} разных натуральных чисел каждая (все числа не превосходят \textit{N}) --- порядок портретов на первой и второй плитках соответственно. Известно, что эти порядки различны. \OutputFile В\textbf{ }выходной файл следует вывести одно число --- наименьшее количество частей, на которые придется разломать первую плитку так, чтобы, каким-то образом переставив эти части местами, получить порядок портретов на второй плитке. \Scoring Набор тестов состоит из 4 блоков, для которых дополнительно выполняются такие условия: \begin{enumerate} \item 20 баллов: 2 ≤ \textit{N} ≤ 3 \item 20 баллов: 3 < \textit{N} ≤ 6 \item 30 баллов: 6 < \textit{N} ≤ 1000 \item 30 баллов: 1000 < \textit{N} ≤ 10^5 \end{enumerate} \textbf{Пояснение. }Первую плитку можно разломать на такие четыре части: квадратик 4, квадратик 3, два квадратика 2 и 5, квадратик 1. Переставив эти части местами нужным образом, получим такой же порядок портретов, как и на второй плитке. В то же время ни один из способов разламывания на три или две части не позволит получить такой же порядок портретов, как на второй плитке.
Лимит времени 0.2 секунд
Лимит использования памяти 256 MiB
Входные данные #1
5
4 3 2 5 1
1 2 5 3 4
Выходные данные #1
4
Автор Данило Мисак
Источник XXVII Всеукраинская ученическая олимпиада по информатике (2014) Днепропетровск