Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
wordchain
Кот Беня играл сам с собой в цепочку слов.
— Начало должно быть позитивным. Например, МЫШЬ. Следующее слово должно начинаться на ШЬ... пусть будет ШЬЮН. Нет такого слова? А у меня в словаре есть, вот: "шьюн - тот, кто шьёт". Дальше будет ЮНОША - ШАМПУНЬ... Ой, нет, тут тупик. ЮНОША-ШАРФ... точнее, ШАР. Дальше вариантов много...
Разработайте программу, которая делает то же, что Беня: составляет цепочки слов из имеющегося словаря, причём каждое следующее начинается на две последних буквы предыдущего. Слова в цепочке не должны повторяться.
Входные данные. В первой строке - натуральное число N, количество слов в словаре Бени. Далее N строк - слова из словаря Бени, по одному в строке. Слова состоят из прописных букв латиницы, длина слова - от 2 до 10 символов. Слово, с которого следует начать цепочку, вводится первым.
Выходные данные. Два целых числа в одной строке через пробел: длина самой длинной цепочки (под длиной понимается количество слов) и количество различных цепочек этой максимальной длины, которые можно составить из слов словаря. Гарантируется, что произведение этих двух чисел не превосходит 5000.
Для отправки решений необходимо выполнить вход.
|