0289. Клавиатура

Имя входного файла: keyboard.in
Имя выходного файла: keyboard.out
Ограничение по времени: 5 s
Ограничение по памяти: 256 megabytes

Наверное, каждый программист считает своим долгом изобрести велосипед и наблюдать, как он работает, так и программист Валера решил изобрести робота, который бы печатал заданный текст на любой клавиатуре. Из-за сложностей реализации распознавания образов клавиш, было решено использовать прямоугольные клавиатуры, которые бы имели вид матрицы 3 *10, каждая ячейка которой – один из символов следующего алфавита: `a', `b', `c', …, `x', `y', `z', `?', `!', `.', `,'. Помимо этого, в тексте могут встречаться пробелы, поэтому каждая клавиатура имеет клавишу пробела шириной 10 ячеек, которая по существу является четвертым нижним рядом клавиш.

Валера пытается сделать из робота профессионала с 10-пальцевой печатью, но так как робот не резиновый, пришлось ввести следующие ограничения на расположение робопальцев:

  1. робот имеет две руки по пять пальцев на каждой,
  2. оба больших пальца рук должны всегда располагаться на клавише пробела и, в случае необходимости, нажимать на неё,
  3. в каждом столбце клавиш (от 1 до 10) может располагаться максимум один палец,
  4. руки не должны перекрещиваться,
  5. пальцы каждой из рук не должны перекрещиваться,
  6. пальцы разных рук не должны перекрещиваться.
Для тестирования своего робота Валера задает клавиатуры с разным расположением символов. На первых порах робот работал довольно медленно и программисту приходилось ждать порядка 20 минут, пока робот наберёт хотя бы 5 символов текста. Проблема заключалась не только в медленном распознавании символов, но и в перемещении пальцев робота по клавиатуре. Пальцы робота перемещаются исключительно параллельно сторонам клавиатуры, то есть, чтобы переместиться из клавиши на позиции (1, 3) в (2, 4), робот двигает палец на один ряд вниз и затем на один столбец вправо, тратя на это 2 минуты. Более формально: при перемещении пальца из позиции (x1, y1) в (x2, y2) робот тратит |x1 - x2| + |y1 - y2| минут, где x1, x2 – номера рядов клавиш, y1, y2 – номера столбцов.

Перед запуском набора текста мизинец, безымянный, средний и указательный пальцы левой руки робота находятся соответственно на следующих позициях: (2, 1), (2, 2), (2, 3), (2, 4), а соответствующие пальцы правой руки находятся на следующих позициях: (2, 7), (2, 8), (2, 9), (2, 10).

Валера решил написать программу, которая бы соблюдала описанные требования к расположению пальцев во время набора текста, а также позволяла набрать текст роботу как можно быстрее.

Формат входного файла

Первые три строки файла содержат по 10 разделенных пробелом символов из описанного в условии алфавита (без пробела). Четвертая строка файла содержит текст, составленный из того же набора символов и пробела длиной не более 20 символов. В данной задаче вы можете считать, что робот тратит одну минуту на распознавание любого символа, даже пробела, несмотря на то, что два больших пальца находятся на них постоянно. %Пятая строка файла содержит время (в минутах) на распознавание каждого непробельного символа на клавиатуре.

Формат выходного файла

В выходной файл выведите целое положительное число – время в минутах, затрачиваемое на набор роботом заданного текста.

Пример:

keyboard.inkeyboard.out
a b c d e f g h i j k l m n o p q r s t u v w x y z , . ! ? some . 9


Источник: Первенство ПетрГУ. Сентябрь 2012.

Обсудить       Отправить решение