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





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

Сдать задачу

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