Марковский цикл
(Время: 1 сек. Память: 16 Мб Сложность: 58%)
Ограниченный алгоритм Маркова состоит из последовательности предложений
s1s2...sN –> d1d2...dN,
где si и di – символы из алфавита A, B, C. Подстрока s1s2...sN называется левой частью, а d1d2...dN – правой частью предложения.
Алгоритм выполняется над исходной текстовой строкой, состоящей из прописных английских букв A, B, C, следующим образом: перебираются все предложения, начиная с первого. Если левая часть предложения входит в текстовую строку, то самое левое вхождение заменяется правой частью этого предложения, и поиск вновь начинается с первого предложения. Если ни одно предложение не может быть применено, алгоритм останавливается.
При выполнении алгоритма возможны два результата: либо остановка, либо бесконечный цикл с определенным периодом. По данной строке и набору предложений алгоритма Маркова определить количество «ациклических» (выполненных до начала цикла) шагов и длину самого цикла. Если алгоритм останавливается, то длина цикла считается нулевой, а все выполненные шаги – ациклическими.
Входные данные
В первой строке входного файла INPUT.TXT находится исходная текстовая строка, а в следующих строках – предложения, по одному в строке. Строки могут содержать произвольное количество незначащих пробелов. Длина исходной строки и левых частей предложений – от 1 до 12 букв, количество предложений – от 1 до 50.
Выходные данные
В выходной файл OUTPUT.TXT выведите два целых числа, разделённых пробелом – количество ациклических шагов и длину цикла.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | ABABC
C ->A
AB ->BA
BAA->ABC | 3 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|