Темы --> Информатика --> Алгоритмы --> Задачи на моделирование
---> 1 задач <---
Источники --> Командные олимпиады --> ВКОШП --> 2004
Страница: 1 Отображать по:
#429
На лифтах через пропасть
  
Источники: [ Командные олимпиады, ВКОШП, 2004, Задача G ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Необходимо перебраться через пропасть по платформам. Платформы расположены в вдоль прямой OX и для каждой из них задана верхняя и нижняя точка, которых они достигают и направление движение. Требуется определить минимальное время, за которое можно достичь противоположного края пропасти.

Сережа очень любит старые игры. Недавно он нашел у себя на компьютере одну старую приключенческую игру. Управляя героем, надо перемещаться по карте и собирать различные предметы.

На определенном этапе игры Сережа столкнулся с неожиданной проблемой. Для продолжения приключений герою надо перебраться через пропасть. Для этого можно использовать последовательно расположенные лифты, которые имеют вид горизонтальных платформ. Каждый лифт вертикально перемещается туда-сюда между некоторыми уровнями. Герой может переходить между соседними платформами, однако это можно сделать только в тот момент, когда они находятся на одном уровне. Аналогично, с края пропасти на лифт и обратно можно перейти лишь в тот момент, когда лифт окажется на уровне края.

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

Края пропасти находятся на одном уровне. Для каждого лифта задан диапазон высот, между которыми он перемещается, начальное положение и направление движения в начальный момент. Все лифты перемещаются со скоростью один метр в секундy. Выясните, сможет ли герой перебраться на противоположный край пропасти, и если да, то какое минимальное время ему для этого понадобится.

 

includegraphics{pics/lifts.1}

Входные данные

В первой строке вводится целое число n – количество лифтов ( 1\( le\)n\( le\)100). Следующие n строк содержат описания лифтов.

Каждое описание состоит из четырех целых чисел: l, u, s – самое нижнее, самое верхнее и начальное положение лифта относительно края пропасти в метрах ( -100\( le\)l\( le\)s\( le\)u\( le\)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
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест