Построение пати из 6 героев по правилам

тема: Перебор с возвратом · уровень: средний

Условие

В игре у вас есть ровно 6 разных героев с номерами 1..6. Перед рейдом нужно поставить их в линию слева направо (6 позиций).

Гильдия выдала список правил, и нужно узнать, сколько разных расстановок им удовлетворяют.

Есть 3 вида правил:

B x y — герой x должен стоять левее героя y.
N x y — герои x и y не должны стоять рядом (соседние позиции запрещены).
P x k — герой x должен стоять ровно на позиции k (позиции нумеруются от 1 до 6 слева направо).

Найдите количество расстановок (перестановок героев 1..6), которые удовлетворяют всем правилам.

Формат ввода

Первая строка: целое число r — количество правил. Далее r строк, в каждой правило одного из трёх видов: B x y, N x y или P x k.

Формат вывода

Выведите одно целое число — количество подходящих расстановок.

Ограничения

Всегда используется ровно 6 героев: 1..6.
0 ≤ r ≤ 30
В правилах: 1 ≤ x, y ≤ 6, x ≠ y, 1 ≤ k ≤ 6.

Пример

Ввод:

Вывод:

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

Разберись руками

Есть 6 героев 1..6 и 6 позиций в линии. В примере: герой 1 обязан быть на позиции 1, герой 2 должен стоять левее героя 3, а герои 4 и 5 не могут быть соседями. Нужно руками посчитать, сколько расстановок подходит.

Сначала учтём только правило P 1 1: герой 1 уже стоит первым. Сколькими способами можно расставить оставшихся героев 2,3,4,5,6 по позициям 2..6?
Теперь добавим правило B 2 3 (2 левее 3), но пока забудем про запрет соседства 4 и 5. Сколько из 120 вариантов останется?
Теперь найдём, сколько из этих 60 “плохие” из-за правила N 4 5 (4 и 5 стоят рядом). Считай так: склей 4 и 5 в один блок. Сколько расстановок будет, если (4,5) или (5,4) обязаны быть соседями, и при этом всё ещё 2 левее 3?
Осталось вычесть плохие (где 4 и 5 рядом) из всех, где 2 левее 3. Сколько подходящих расстановок в итоге?

Идея: Сначала считаем варианты без части правил (например, когда один герой уже зафиксирован). Потом аккуратно отсекаем: правило “левее” обычно делит варианты пополам из-за симметрии перестановок, а правило “не рядом” удобно проверять через подсчёт плохих случаев, где пара стоит рядом (склеиваем их в блок), и вычитаем плохие из всех.

Решить задачу с автопроверкой на Python →

Куда дальше

Школьный этап ВсОШ по информатике — как устроен первый этап и план подготовки за четыре недели
Перечневые олимпиады по информатике — олимпиады перечня Минобрнауки, их уровни и что нужно к диплому
БВИ по олимпиадам: в какие вузы берут — правила приёма вузов, разобранные построчно, со ссылкой на приказ у каждой строки