XVIII всероссийская олимпиада школьников по информатике в Кисловодске.

Назад

Задача 2.Файловый менеджер

Имя входного файла: fur.in
Имя выходного файла: fur.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта
Максимальная оценка: 100 баллов

       Петя работает над очень большим проектом. Проект содержит N файлов. В процессе работы Пете часто приходится просматривать и редактировать файлы. Для ускорения работы Петя использует файловый менеджер Fur Manager, который отображает список имен
       файлов проекта в некотором порядке. В текущей версии Fur Manager’a для перемещения по списку имен файлов есть следующие возможности:
  1. можно нажать клавишу вниз, при этом курсор перемещается на следующий файл в списке, для последнего файла следующим считается первый;
  2. можно нажать клавишу вверх, при этом курсор перемещается на предыдущий файл в списке, для первого файла предыдущим считается последний;
  3. можно нажать клавишу Alt и, удерживая ее, набрать последовательность латинских букв. После этого клавишу Alt следует отпустить, и в этот момент курсор переместится на ближайший файл, имя которого начинается c заданной последовательности символов. Ближайший файл — это файл, на который можно переместиться за наименьшее количество нажатий клавиши вниз. Если заданная последовательность является началом имени текущего файла, или файла, имя которого начинается с этой последовательности, не существует, то курсор останется на месте.
       Первая и вторая из описанных возможностей файлового менеджера требуют по одному нажатию клавиши, а третья — одного нажатия (нажатие клавиши Alt) плюс количество нажатий, равное длине набранной последовательности латинских букв.
       Файлы пронумерованы от 1 до N в порядке их следования. После загрузки Fur Manager’а курсор находится на первом файле.
       Петя знает, что ему сначала придется редактировать файл с номером a1, затем с номером a2 и так далее, а последним — файл с номером ak. В последовательности a1, a2, ..., ak один и тот же номер может встречаться несколько раз. При каждом перемещении от одного файла к другому Петя хочет нажимать как можно меньше клавиш.
       Требуется написать программу, которая выдает искомую последовательность нажатий клавиш.

Формат входных данных

       В первой строке входного файла записано целое число N (1 <= N <= 1000) — количество файлов в проекте.
       В следующих N строках записаны имена файлов, по одному в каждой строке. Файлы перечислены в том порядке, в котором они отображаются файловым менеджером. Имена состоят только из строчных латинских букв. Длина каждого имени не превосходит 2000 символов. Все имена файлов различны.
       Далее в следующей строке записано целое число k (1 <= k <= 10).
       Последняя строка входного файла содержит k целых чисел a1, a2, ..., ak (1 <= ai <= N) — номера редактируемых файлов. Редактирование файлов выполняется в том порядке, в котором они встречаются в последовательности a1, a2, ..., ak.

Формат выходных данных

       Выходной файл должен содержать описание искомой последовательности нажатий клавиш в виде k блоков информации:
  • первый блок информации описывает перемещение от файла с номером 1 к файлу с номером a1;
  • второй блок информации описывает перемещение от файла с номером a1 к файлу с номером a2;
  • …
  • k-ый блок информации описывает перемещение от файла с номером ak–1 к файлу с номером ak.
       Каждый блок информации выглядит следующим образом.
       В первой строке блока записывается число L — наименьшее количество нажатий клавиш, необходимое для перемещения от очередного файла последовательности к следующему.
       Следующие L строк блока описывают нажимаемые клавиши. Каждая из строк содержит описание одной клавиши:
  • если нажимается клавиша вниз, то в строке записывается слово down;
  • если нажимается клавиша вверх, то в строке записывается слово up;
  • если нажимается клавиша Alt, то в строке записывается слово Alt;
  • при нажатии клавиши с латинской буквой выводится соответствующая ей латинская буква.
       Если существует несколько оптимальных способов перемещения, то требуется вывести любой из них.

Примеры:

fur.in fur.out
6
submit
monitor
monitorx
monyator
subversion
sub
5
6 3 3 5 2 		1
up
3
Alt
m
down
0
2
down
down
2
Alt
m
8
abc
abv
abba
auto
test
auvto
ioi
olympiad
2
4 6 		3
Alt
a
u
2
down
down
Личный сайт им. РОССОМАХи ICQ: 229654802 e-mail: poc.leb@mail.ru design by: POCCOMAXA
Сайт создан в системе uCoz