Задача G. Древний обряд

Задачу добавил: alef

Успешно сдано решений: 1

Задача G. Древний обряд

А пока подданные господина Маллока празднуют его свадьбу, первая фрейлина Ос-Вин, исполняя древний обряд Ин-Сталл, водит невесту по Большому Замку. Прежде чем она станет женой господина Маллока, фрейлина должна ее представить пятерым главным вельможам. Бабушка Тини рассказала ребятам, что их называют служителями Регистра, и никто не знает их имен – известны лишь их инициалы: H.K.C.R., H.K.C.U., H.K.L.M., H.K.U. и H.K.C.C.

Большой Замок Ксеон, как уже говорилось выше, имеет форму параллелепипеда. В нем K этажей, на каждом этаже вдоль стен располагаются комнаты, а в центре – большая зала. Угловых комнат в замке нет (вдоль стен помещаются соответственно N–2 и M–2 комнаты (см. рис.)), в каждом углу – лестница, соединяющая этажи (от первого до последнего). Фрейлина приводит невесту в замок через вход на первом (нижнем) этаже, обозначенный на рисунке точкой. Фрейлина и невеста могут двигаться через комнаты как по часовой, так и против часовой стрелки, переходя за единицу времени из одной комнаты (или с лестничной клетки) в соседнюю с ней (или на лестничную клетку), а также подниматься и спускаться по лестницам. Переход с этажа на этаж также занимает у них 1 единицу времени. Что же касается вельмож, то они тоже могут перемещаться по замку, и тоже могут пройти через комнату за единицу времени. Однако после единицы времени, в которую они двигаются, им нужна единица времени для отдыха. Подъем или спуск по лестнице также потребует у них больше времени (единица времени – движение, единица времени – отдых на лестничной клетке, итого – 2 единицы).

Фрейлине известно, где находится каждый из вельмож в данный – начальный – момент времени. Она выбирает ближайшего из них (того, до которого можно быстрее всего дойти из точки, где находятся фрейлина с невестой) и ведет невесту сначала к нему (точнее, к той точке, в которой находился вельможа в анализируемый момент). Если в какой-либо комнате по дороге они встретят какого-то другого вельможу, фрейлина представит невесту ему, если она еще не сделала этого раньше. В тот же момент, как только фрейлина представила невесту кому-либо из вельмож или если они добираются до искомой точки, так никого и не встретив, она вновь анализирует, кто из тех вельмож, кому невеста еще не была представлена, является ближайшим, и ведет невесту уже к нему. Так продолжается до тех пор, пока невеста не будет представлена всем вельможам.

Когда фрейлина выбирает ближайшего из вельмож, то

– при равных расстояниях до двух и более вельмож она выберет того, чьи инициалы в списке H.K.C.R., H.K.C.U., H.K.L.M, H.K.U и H.K.C.C. стоят раньше.

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

– при прочих равных она будет двигаться против часовой стрелки.

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

Перемещения вельмож задаются командами:

— L (перемещение против часовой стрелки в соседнюю комнату),

— R (перемещение по часовой стрелке в соседнюю комнату),

— U (подъем вверх на один этаж),

— D (спуск вниз на один этаж),

— TS, где S – целое число (например, T5 или T108), обозначающее дополнительный отдых (не включающий единицу времени после перемещения) в течение N единиц времени.

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

Первая строка – целые числа K, N, M (1 <= K <= 100, 3 <= N, M <= 1000) через пробел – количество этажей в Большом Замке, количество комнат (с учетом лестничных клеток), вдоль стен замка (см. рис.).

Строки со второй по шестую включительно задают начальное положение вельмож H.K.C.R., H.K.C.U., H.K.L.M, H.K.U и H.K.C.C. соответственно как два целых числа: Xj (1<=Xj<=K) и Y (1 <= Yj <= 2N+2M–4) через пробел, где Xj – номер этажа, а Yj – номер комнаты, если считать по часовой стрелке от левого верхнего угла (лестничные клетки включаются в нумерацию).

Строки с седьмой по одиннадцатую включительно описывают маршруты вельмож H.K.C.R., H.K.C.U., H.K.L.M, H.K.U и H.K.C.C. соответственно. Маршрут задается перечислением через пробел описанных в условии команд L, R, U, D и TS через пробел (1 <= S <=1000). После последней команды через пробел указывается символ E – признак окончания маршрута. Ни для одного вельможи количество команд не превышает 1000.

Примечание. Гарантируется, что все команды для вельмож корректны и не приводят к выходу за пределы замка. Если маршрут вельможи завершен, он может оставаться на месте бесконечно долгое время.

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

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

Пример входного файла

2 5 3

1 5

2 6

2 11

1 8

2 12

U L T3 L L L L R D T2 L R R R R R R R U L L L T8 L E

R D R R R R T8 L L L L U L L L L L L R T12 R E

R R R T5 R R R D E

T4 E E

L R L R L R L R E

Пример выходного файла

H.K.L.M. H.K.C.C. H.K.C.R. H.K.C.U. H.K.U.

Сдать задачу

Задать вопрос жюри по этой задаче