Задача №429. На лифтах через пропасть
Сережа очень любит старые игры. Недавно он нашел у себя на компьютере одну старую приключенческую игру. Управляя героем, надо перемещаться по карте и собирать различные предметы.
На определенном этапе игры Сережа столкнулся с неожиданной проблемой. Для продолжения приключений герою надо перебраться через пропасть. Для этого можно использовать последовательно расположенные лифты, которые имеют вид горизонтальных платформ. Каждый лифт вертикально перемещается туда-сюда между некоторыми уровнями. Герой может переходить между соседними платформами, однако это можно сделать только в тот момент, когда они находятся на одном уровне. Аналогично, с края пропасти на лифт и обратно можно перейти лишь в тот момент, когда лифт окажется на уровне края.
Каждый лифт имеет ширину, равную четырем метрам. В начале герой находится на расстоянии два метра от края пропасти. Он должен закончить свое путешествие в двух метрах от противоположного края пропасти. Герой перемещается со скоростью два метра в секунду. Таким образом, если герой находится в начальном положении или в центре лифта и хочет перейти на соседний лифт (или сойти с последнего лифта на противоположный край пропасти), он должен начать движение ровно за одну секунду до того момента, когда они окажутся на одном уровне. Через две секунды герой оказывается в центре соседнего лифта (или в конечном положении).
Края пропасти находятся на одном уровне. Для каждого лифта задан диапазон высот, между которыми он перемещается, начальное положение и направление движения в начальный момент. Все лифты перемещаются со скоростью один метр в секундy. Выясните, сможет ли герой перебраться на противоположный край пропасти, и если да, то какое минимальное время ему для этого понадобится.
В первой строке вводится целое число n – количество лифтов ( 1
\( le\)" width="16" height="28" align="middle" />n\( le\)" width="16" height="28" align="middle" />100). Следующие n строк содержат описания лифтов.
Каждое описание состоит из четырех целых чисел: l, u, s – самое нижнее, самое верхнее и начальное положение лифта относительно края пропасти в метрах ( -100\( le\)" width="16" height="28" align="middle" />l\( le\)" width="16" height="28" align="middle" />s\( le\)" width="16" height="28" align="middle" />u\( le\)" width="16" height="28" align="middle" />100, l < u), и d – направление движения лифта в начальный момент (d = 1 означает, что лифт двигается вверх, d = - 1 – вниз).
Выведите минимальное время в секундах, необходимое для того, чтобы перебраться на противоположный край пропасти. Если перебраться на противоположный край пропасти невозможно, выведите число -1.
4 -1 2 1 -1 0 3 0 1 -4 0 0 -1 -2 1 0 -1
29