e-olymp
Məsələlər

Генетические алгоритмы

Генетические алгоритмы

Генетические алгоритмы — один из современных методов искусственного интеллекта. Они основаны на принципе естественного отбора, который был предложен Чарльзом Дарвином, и являются одной из разновидностей эволюционных вычислений.

В процессе работы генетического алгоритма поддерживается некоторое множество допустимых решений задачи, называемое поколением. Работа алгоритма состоит в генерации очередного поколения. Для этого используются так называемые операции "мутации" и "скрещивания". Как правило, операция мутации состоит в небольшом изменении решения, а операция скрещивания — в построении из двух решений одного или двух новых.

Одним из применений генетических алгоритмов является решение задачи коммивояжера. Допустимыми решениями в этой задаче являются перестановки чисел от 1 до n — такие последовательности длины n, в которых каждое их этих чисел встречается ровно один раз.

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

Для анализа таких алгоритмов полезно уметь определять число перестановок, согласованных с данными двумя. Ваша задача состоит в том, чтобы написать программу, которая будет вычислять это число.

Входные данные

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

Выходные данные

В выходной файл выведите ответ на задачу.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
Sample 1
2
1 2
2 1

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

Sample 2
14

Şərh: В первом примере нет ни одной пары чисел (i, j) такой, что в обеих перестановках i идет раньше, чем j. Поэтому с ними согласованы обе возможные перестановки из двух чисел.