e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

Генетичні алгоритми

Генетичні алгоритми

Генетичні алгоритми — один з сучасних методів штучного інтелекту. Вони базуються на принципі природного відбору, який був запропонований Чарльзом Дарвіном, і є одним з різновидів еволюційних обчислень.

У процесі роботи генетичного алгоритму підтримується деяка множина допустимих розв'язків задачі, яка називається поколінням. Робота алгоритму полягає в генерації чергового покоління. Для цього використовуються так звані операції "мутації" та "зхрещування". Як правило, операція мутації складається у невеликій зміні розв'язкау, а операція зхрещування — у побудові з двох розв'язків одного чи двох нових.

Одним із застосувань генетичних алгоритмів є розв'язання задачі комівояжера. Допустимими розв'язками у цій задачі є перестановки чисел від 1 до n — такі послідовності довжинм n, у яких кожне з цих чисел зустрічається рівно один раз.

Деякі генетичні а0лгоритми, які розв'язують задачу комівояжера, використовують операції зхрещування, які генерують лише так звані узгоджені перестановки. Нехай задано дві перестановки. Назвемо третю перестановку узгодженою з першими двома, якщо для довільної пари чисел (i, j) такої, що в обох перестановках число i йде раніше, ніж число j, і у новій перестановці i йде раніше j.

Для аналізу таких алгоритмів корисно вміти визначати кількість перестановок, узгоджених з заданими двома. Ваша задача полягає у тому, щоб написати програму, яка буде обчислювати цю кількість.

Вхідні дані

Перший рядок вхідного файлу містить число n (1n20). Другий рядок вхідного файлу містить n чисел — першу перестановку, а третій рядок містить другу перестановку.

Вихідні дані

У вихідний файл виведіть відповідь до задачі.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
2
1 2
1 2
Вихідні дані #1
1

Пояснення: У першому прикладі немає жодно пари чисел (i, j) такої, що в обох перестановках i йде раніше, ніж j. Тому з ними узгоджені обидві можливі перестановки з двох чисел.