Задача F. Код вируса
Задачу добавил: alef
Успешно сдано решений: 0
В лабораториях НИИЧАВО проводятся исследования с органическим материалом, извлеченного из метеорита. Уже удалось выяснить, что ДНК материала состоит из N различных нуклеотидов. Стало также известно, что существует цепочка из K (>2) нуклеотидов, которая кодирует чрезвычайно опасный вирус. Поэтому экспериментаторам приходится проявлять особую осторожность, и не допускать образования такой цепочки ни самой по себе, ни в составе какой-либо другой цепочки. В экспериментах над цепочками нуклеотидов выполняются две операции: сшивки двух цепочек в одну и разрезания одной цепочки на две.
Каждому концу цепочки присваиваются индексы потенциальной опасности: DH и DT. Эти индексы вычисляются как длина максимальной цепочки нуклеотидов, которая является подцепочкой вируса, если рассматривать ее с начала (DH) и с конца (DT) соответственно. По мнению исследователей, реальная опасность возникает, если в одном наборе цепочек найдутся две разные цепочки, у которых сумма индексов DH и DT для каких-либо их концов станет равной K. Один из экспериментов состоит в следующем. Исследователи планируют получить все возможные цепочки нуклеотидов длины L. Они хотят узнать, сколько у них получится разных цепочек при следующем подходе.
Сначала рассматривают все нуклеотиды как цепочки длины 1 и пробуют образовать все возможные цепочки из двух нуклеотидов. Таким образом, получается набор, состоящий из цепочек длин 1 и 2. Затем опасные пары цепочек убирают. Рассмотрение цепочек при удалении происходит в лексикографическом порядке, сначала выполняется проверка для DH.
Получившийся набор из цепочек длин 1 и 2 используют для генерации цепочек длины 3, собирая все возможные комбинации из двух цепочек (это выполняется при генерации цепочек любой длины: в образовании новой цепочки должно участвовать ровно две из имеющегося набора). Затем из нового набора опять убирают опасные пары цепочек. Процесс продолжается до тех пор, пока не будут получены цепочки длины L (или не будет установлено, что таких цепочек получено быть не может).
Примечание
При сшивании конец одной цепочки присоединяется к началу другой. Сшиваются только различные цепочки. Вирусом считается только заданная цепочка, ее зеркальное отражение вирусом не является.
Пояснение.
Приведем пример вычисления индексов DH и DT. Допустим, вирус определяется как cba. В этом случае для цепочки badc индекс DH равен 1, индекс DT равен 2.
Формат входного файла input.txt
Первая строка содержит целые числа N (3 <= N <= 10), L (1 <= L <= 20) и K (2 < K <= 20) через пробел. N – количество нуклеотидов в ДНК, L – желаемая исследователями длина цепочки, K – длина цепочки, кодирующей вирус. Нуклеотиды обозначаются строчными буквами латинского алфавита: a, b, c, … Вторая строка содержит кодовую последовательность вируса – K строчных букв латинского алфавита без пробелов.
Формат выходного файла output.txt
Первая строка содержит целое число – количество различных цепочек длины L, которые могут быть получены в описанном эксперименте.
Пример входного файла
3 2 3
bbb
Пример выходного файла
6