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