Олимпиадный тренинг

Задача . Тяжелая, вариант-1


Задача

Темы:

Вы разрабатываете систему, одной из задач которой является составление расписания работы над задачами, выполняемыми некоторой организацией, занимающейся разработкой программного обеспечения.

Известно, что организации необходимо выполнить n задач, пронумерованных натуральными числами от одного до n. На выполнение каждой задачи требуется ровно один день, и в каждый день может быть выполнена только одна задача. Таким образом, на выполнение всех задач потребуется n дней, а расписание выполнения задач выглядит как назначение определенного дня на выполнение каждой задачи. Для каждой задачи известно также число ai — номер дня, не позднее которого эта задача должна быть выполнена.

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

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

В первой строке находится натуральное число n (1 ≤ n ≤ 8) — количество задач, которые необходимо выполнить.

Следующая строка содержит n натуральных чисел ai (1 ≤ ai ≤ n) — для каждой работы номер дня, не позднее которого она должна быть выполнена. Числа отделены друг от друга одним пробелом.

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

Выведите одно число — количество различных допустимых расписаний выполнения задач.

Пример входных и выходных данных

Ввод Вывод
5
2 4 4 2 5
4

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python10
С++ Mingw-w6431
Комментарий учителя