Городские олимпиады/1-6 курсы/Межвузовская олимпиада 2019


11. Генерация тестов

Автор задачи: Звигинцев Илья
Ограничение по времени: 1 с.
Ограничение по памяти: 256 МБ

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

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

  • длина каждой строки равна n;

  • строки состоят из строчных букв латинского алфавита;

  • не существует двух рядом стоящих одинаковых букв;

  • не существует префикса, содержащего букву с порядковым номером x и не содержащего букву с порядковым номером (x-1).

Примеры допустимых строк: «a», «abac». Примеры недопустимых строк: «abad» — присутствует символ ‘d’, но отсутствует символ ‘c’; «ba» — в префиксе длины 1 присутствует символ ‘b’, но отсутствует символ ‘a’.

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

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

В единственной строке содержится целое число n (1 \leqslant n \leqslant 14) — длина каждой строки.

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

В единственной строке выведите одно целое число — количество строк, удовлетворяющих условию.

Примеры
Стандартный вводСтандартный вывод
515
Пояснения к примерам

В приведенном примере возможны следующие строки:

  • ababa,

  • ababc,

  • abaca,

  • abacb,

  • abacd,

  • abcab,

  • abcac,

  • abcad,

  • abcba,

  • abcbc,

  • abcbd,

  • abcda,

  • abcdb,

  • abcdc,

  • abcde.