Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Проверка орфографии

(Время: 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.TXTOUTPUT.TXT
14
SaratoV
StaTe
The
University
SaratofStataUniversitI
SaratovStateUniversitY

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru