eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Разбор строки

Разбор строки

При разработке алгоритмов и систем, занимающихся поиском в интернете, важную роль играет часть программы, отвечающая за разбор выражений. За время существования поисковых систем было придумано большое количество различных алгоритмов, решающих задачи этого класса. Они отличаются друг от друга временем работы, сложностью написания и количеством потребляемых ресурсов. Рассмотрим задачу проверки того, состоит ли некоторая строка из слов, принадлежащих к некоторому словарю. Одним из самых простых алгоритмов, решающих эту задачу, является жадный алгоритм. Каждый раз из строки удаляется максимальный ее префикс, присутствующий в словаре как отдельное слово. На достаточно большом множестве строк, являющихся конкатенацией слов из словаря, этот алгоритм успешно завершает свою работу и разбивает строку на слова. Кроме того, этот алгоритм крайне прост в реализации. Однако, существуют и строки, на которых он выдаст неправильный результат. Например, если в качестве словаря взять список всех слов, существующих в английском языке, то строка "\textbf{workingrass}" не будет распознана корректно, так как сначала из нее будет удален префикс "\textbf{working}", а после этого остаток "\textbf{rass}" разбить на нужные слова уже невозможно. В то же время, эту строку можно представить как конкатенацию слов "\textbf{work}", "\textbf{in}" и "\textbf{grass}". При разработке различных программ далеко не всегда приходится иметь дело со словарем английского языка. Иногда словари достаточно специфичны, и описанный алгоритм будет корректно разбивать всевозможные строки, являющиеся конкатенациями слов из словаря. Вам необходимо проверить, является ли набор слов (словарь) таким, и, если не является, привести пример строки, для которой разбиение на слова из словаря существует, но описанным алгоритмом оно не будет найдено. Если таких примеров несколько, необходимо найти кратчайший, то есть тот, длина которого не больше, чем у остальных. Если и таких несколько, выведите любой. \InputFile Первая строка содержит одно целое число \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{250}) - количество слов в словаре. В следующих \textbf{n }строках перечислены слова, лежащие в словаре. Каждое слово непусто и состоит только из строчных букв латинского алфавита. Длина каждого слова не превышает \textbf{500 }символов. \OutputFile Если строки, отвечающие описанным в условии требованиям, существуют, выведите любую из них, длина которой не превышает длины остальных. Выведенная вами строка должна состоять только из строчных символов латинского алфавита. В противном случае выведите "\textbf{Good vocabulary!}".
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
3
ab
cd
abcd
Выходные данные #1
Good vocabulary!
Автор В.Ульянцев, П.Кротков
Источник 2012 Russian Code Cup, Отборочный раунд, Задача E