Проверка орфографии
(Время: 1 сек. Память: 16 Мб Сложность: 56%)
Профессор Далл разработал новую систему проверки и исправления орфографии. Расстоянием между двумя английскими буквами в одинаковом регистре называется кратчайшее расстояние между ними по алфавиту, записанному по кругу. Например, d(B, G) = 5, а d(Z, A) = 1. Расстояние между буквами разных регистров равно расстоянию между соответствующими буквами одного регистра. Например, d(a, A) = 0, d(Z, a) = 1.
Расстоянием между двумя строками одинаковой длины называется сумма расстояний между соответствующими буквами. Метод профессора основывается на словаре правильных слов и представляет введенную последовательность в виде конкатенации слов из словаря таким образом, чтобы расстояние между заданным текстом и результатом было наименьшим. Регистр букв в тексте сохраняется. Реализуйте метод Далла.
Слово из словаря может использоваться более одного раза.
Входные данные
В первой строке входного файла INPUT.TXT содержится N (1 ≤ N ≤ 100), обозначающее количество слов в словаре. Далее, в N строках содержатся слова из словаря. Длины слов от 1 до 32 символов включительно.
Последняя строка файла содержит текст. Текст состоит из английских букв, длина текста не менее 1 символа и не более 1000. Возможно, словарь содержит одинаковые слова. Слова в словаре записываются буквами произвольного регистра.
Выходные данные
В выходной файл OUTPUT.TXT выведите результат. Если решений несколько, выведите любое. Если решения не существует, выведите -1.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
SaratoV
StaTe
The
University
SaratofStataUniversitI | SaratovStateUniversitY |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
