eolymp
bolt
Try our new interface for solving problems
Məsələlər

Шоколад

Шоколад

Zaman məhdudiyyəti 0.2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Шоколад, который производит кондитерская компания «Ням Ням», имеет вид длинной плитки N, состоящей из N квадратиков. На каждом квадратике изображен один из N известных кондитеров, причем на разных шоколадках, которые производит компания, изображены одни и те же N кондитеров, только в разном порядке.

Задание Напишите программу, которая для заданного порядка портретов на двух плитках шоколада определяет, на какое наименьшее количество частей придется разломать первую плитку, чтобы путем переставления частей из нее можно было образовать вторую. Ломать плитку разрешается только по границам квадратиков, а переворачивать плитку или ее части нельзя.

Входные данные Первая строка входного файла содержит натуральное число N (2 ≤ N ≤ 10^5), задающее размер плитки шоколада, то есть количество квадратиков в ней. Все кондитеры пронумерованы числами от 1 доN. Вторая и третья строки файла содержат по N разных натуральных чисел каждая (все числа не превосходят N) — порядок портретов на первой и второй плитках соответственно. Известно, что эти порядки различны.

Çıxış verilənləri

Ввыходной файл следует вывести одно число — наименьшее количество частей, на которые придется разломать первую плитку так, чтобы, каким-то образом переставив эти части местами, получить порядок портретов на второй плитке.

Nümunə

Giriş verilənləri #1
5
4 3 2 5 1
1 2 5 3 4
Çıxış verilənləri #1
4

Qiymətləndirmə

Набор тестов состоит из 4 блоков, для которых дополнительно выполняются такие условия:

  1. 20 баллов: 2 ≤ N ≤ 3

  2. 20 баллов: 3 < N ≤ 6

  3. 30 баллов: 6 < N ≤ 1000

  4. 30 баллов: 1000 < N ≤ 10^5

Пояснение. Первую плитку можно разломать на такие четыре части: квадратик 4, квадратик 3, два квадратика 2 и 5, квадратик 1. Переставив эти части местами нужным образом, получим такой же порядок портретов, как и на второй плитке. В то же время ни один из способов разламывания на три или две части не позволит получить такой же порядок портретов, как на второй плитке.

Müəllif Данило Мисак
Mənbə XXVII Всеукраинская ученическая олимпиада по информатике (2014) Днепропетровск