Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача 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

Сдать задачу

Задать вопрос жюри по этой задаче