|
SMS - 2
(Время: 1 сек. Память: 16 Мб Сложность: 50%)
В наше время непросто найти человека, который ни разу в жизни не использовал мобильный телефон для отправления текстовых сообщений. Старые телефоны поддерживали только один способ набора текста, упрощенно описывающийся следующими правилами: Каждой из восьми кнопок от «2» до «9» ставится в соответствие несколько букв, а кнопка «1» отводится для знаков препинания. Пробел ставится нажатием кнопки «0». Для ввода первого из соответствующих кнопке символов, ее надо нажать один раз, для ввода второго - два раза и так далее. Если два подряд идущие символа (кроме пробела) сопоставлены одной кнопке, то после ввода первого из них можно, либо подождать, либо нажать на кнопку перемещения курсора (второй вариант оказывается быстрее). Для переключения регистра букв используется кнопка «#». Кроме того, для удобства, после ввода вопросительного и восклицательного знаков, а так же точки (если на этот момент включен нижний регистр), активируется режим «первой заглавной буквы». При этом следующая буква автоматически печатается заглавной, после чего опять включается нижний регистр. В начале набора включен режим «первой заглавной буквы».
В последнее время в Интернете стали появляться результаты различных исследований, доказывающих неэффективность обычной раскладки телефонной клавиатуры, в которой буквы сопоставляются цифрам в алфавитном порядке. Составьте программу, которая по заданному сопоставлению букв кнопкам, будет находить минимальное количество нажатий, необходимых для максимально быстрого ввода данного текста при условии, что на каждое нажатие уходит одинаковое количество времени.
Входные данные
Строки с первой по девятую входного файла INPUT.TXT задают символы, сопоставленные соответствующим кнопкам. Следующая строка содержит сообщение длиной от 1 до 1000 символов. Гарантируется, что в первой строке находятся символы «?», «!» и «.», заданные в определенном порядке; в последующих 8 строках расположены все строчные английские символы от «a» до «z» без повторов, не менее одной буквы в строке. Текст сообщения содержит только те символы, которые возможно напечатать.
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число - минимальное количество нажатий на кнопки, требующееся для наискорейшего ввода сообщения.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | .?!
abc
def
ghi
jkl
mno
pqrs
tuv
wxyz
Hello. How do you do? i hope everything is fine See ya! | 120 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
