Контрольная

Тут такая задача:

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

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

Пример входных данных:
3
ИВАНОВ
СИДОРОВ
ПЕТРОВ
Пример выходных данных:
3

Технические ограничения:
В классе не более 50 российских учеников, среди которых нет однофамильцев.
Примечание:
Способы считаются различными, если они различаются порядком складывания тетрадей (кто именно клал тетрадь i-м по счету).

Итак. Ну, проблем с сортировкой фамилий нет. Условие понятно, но котелок недоваривает.
Попробовал начиркать в блокноте все варианты - для данного примера оказалось 16 штук (кол-во способов складывания тетрадей (4) * кол-во способов порядка выхода учеников (4) = 4 * 4 = 16).
С ответом сошлось. Но если перебирать все это, когда в классе 50 учеников?!, то...

В общем, буду благодарен за любую полезную идею.

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

Тогда, видимо, можно использовать динамическое программирование, начав с ученика, выходящего последним (таких в общем случае двое -- первый по алфавиту и последний по алфавиту), добавляя к нему учеников справа и слева. В конце для каждого ученика должно получиться количество вариантов, в которых крайний правый ученик выходит первым и в которых крайний левый ученик выходит первым. Их просуммировать

(Способ сводится к подсчету количества вариантов получения заданной рассадки из алфавитного списка по тем же правилам)

Сообщение отредактировано: Visitor - 29.11.03, 23:25