Задача F. Повар
Задачу добавил: alef
Успешно сдано решений: 0
Задача F. Повар
Главный повар господина Маллока Феоф – чрезвычайно скрытный человек. Он захотел зашифровать рецепты, по которым готовятся главные блюда свадебного стола. Все рецепты у него записаны чрезвычайно тщательно и подробно: какие действия и в какой последовательности надо выполнять. Он заметил, что некоторые последовательности действий повторяются, и решил поступить следующим образом.
Он просматривает рецепты блюд попарно и отыскивает самые длинные последовательности одинаковых действий для каждой пары рецептов. Затем он выбирает самую длинную из них и придумывает для нее секретное обозначение, которое записывает в свой блокнот (с «расшифровкой»), а в рецептах использует секретное обозначение. После этого он вновь просматривает все рецепты попарно, вновь определяет самую длинную последовательность одинаковых действий, и вновь придумывает обозначение.
Если он обнаружил две (или больше) последовательности одинаковых действий равной длины, он выбирает ту из них, которая лексикографически является первой. Секретные обозначения считаются лексикографически упорядоченными по мере их введения – т.е. то, которое было придумано первым, является первым лексикографически, придуманное вторым – лексикографически второе и т.д. Все изначально описанные в рецептах действия считаются лексикографически предшествующим секретным обозначениям.
Если самая длинная последовательность одинаковых действий встречается более чем в двух рецептах, она заменяется секретным обозначением во всех рецептах. Если самая длинная последовательность одинаковых действий встречается в одном или более рецептах несколько раз, она также везде заменяется секретным обозначением.
Процесс повторяется до тех пор, пока длина самой длинной последовательности повторяющихся действий не станет равной единице.
Ваша задача – написать программу, которая определит, сколько секретных обозначений придется придумать главному повару господина Маллока. Так же необходимо посчитать, сколько различных действий в рецептах останется незашифрованными.
Формат входного файла input.txt
Первая строка – целое число N (2 <= N <= 10) – количество рецептов блюд свадебного стола.
Следующие строки содержат информацию о рецептах. Каждый рецепт начинается строкой «begin_recipe», после которой через пробел указывается название блюда. Затем, начиная со следующей строки, записывается последовательность действий, которая позволяет приготовить блюдо – по одному в строке. Эта последовательность состоит из строчных латинских букв, цифр и символов подчеркивания (заменяющих пробелы), и всегда начинается с буквы. Признаком окончания рецепта служит строчка «end_recipe». В каждом рецепте содержится не менее одного и не более 100 действий, каждое действие описывается строкой длиной не более 250 символов.
Формат выходного файла output.txt
Первая строка – два целых числа S и C через пробел. Число S – количество секретных обозначений, которые нужно придумать главному повару господина Маллока, число C – количество действий, которые останутся незашифрованными.
Пример входного файла
3
begin_recipe buterbrod
rezhem_bulku
mazhem_maslom
vykladyvaem_buterbrod_na_tarelku
end_recipe
begin_recipe buterbrod s syrom
rezhem_bulku
mazhem_maslom
rezhem_syr
kladem_na_maslo_syr
vykladyvaem_buterbrod_na_tarelku
end_recipe
begin_recipe buterbrod s kolbasoy
rezhem_bulku
mazhem_maslom
rezhem_kolbasu
kladem_na_maslo_kolbasu
vykladyvaem_buterbrod_na_tarelku
end_recipe
Пример выходного файла
1 5