- Описание
- Отправленные решения
478. Сокращение маршрута
Дмитрий участвует в пешеходном квесте, цель которого — дойти из точки А в точку Б. Его друг Георгий уже проходил этот квест и составил краткое описание маршрута с направлениями движения и дистанциями. Однако он неправильно решал некоторые задания и шёл по неверному пути, из-за чего в описании встречаются тупики. Дмитрий очень хочет поскорее пройти маршрут и не тратить на тупики драгоценное время. Он обратился к вам с просьбой, чтобы вы помогли убрать из маршрута тупики и сократить одинаковые направления, если они идут друг за другом.
Маршрутом считается набор действий. Каждое действие задаётся двумя параметрами — направлением и дистанцией. Дистанции бывают только целочисленными.
Тупиком считаются последовательные действия в строго противоположных направлениях движения. Например, если требуется пойти TOP 50
и следующим шагом BOTTOM 50
, то это считается тупиком и такие действия можно полностью сократить (тогда в выводе не должно быть этих строчек). Однако если дистанции не сокращаются полностью, то полностью сократить действия нельзя. Например, если требуется пойти TOP 50
и следующим шагом BOTTOM 40
, то это можно сократить в TOP 10
.
Тупиком не считается возвращение в точку маршрута по другой дороге. Например, если требуется пойти TOP 50
, RIGHT 50
, BOTTOM 50
, LEFT 50
, BOTTOM 10
, то эти действия сократить до BOTTOM 10
нельзя.
Пример одинаковых направлений, идущих друг за другом, — BOTTOM 50
, BOTTOM 50
. Такой набор действий необходимо сократить в BOTTOM 100
.
Формат ввода
На вход подаётся список действий изначального маршрута.
Каждое действие задаётся двумя параметрами — направлением (LEFT
, RIGHT
, TOP
или BOTTOM
) и дистанцией (), разделёнными пробелом.
Количество строк во входных данных не превышает 1000.
Формат вывода
В качестве ответа необходимо вывести сокращённый маршрут. В каждой строке — действие, в том же формате, что и во входных данных.
Ограничения
Ограничение времени
1 с
Ограничение памяти
64 МБ
Пример 1
LEFT 10
TOP 50
BOTTOM 50
TOP 10
LEFT 10
TOP 10
Пример 2
TOP 40
RIGHT 10
LEFT 30
BOTTOM 40
TOP 40
LEFT 20
BOTTOM 40
Пример 3
TOP 42
LEFT 450
TOP 150
BOTTOM 150
RIGHT 450
LEFT 42
TOP 42
LEFT 42
Пример 4
TOP 50
RIGHT 50
BOTTOM 50
LEFT 50
BOTTOM 10
TOP 50
RIGHT 50
BOTTOM 50
LEFT 50
BOTTOM 10
Пример 5
TOP 100
TOP 100
TOP 200
Пример 6
TOP 100
TOP 100
BOTTOM 150
BOTTOM 150
BOTTOM 100