Задача G. На лифтах через пропасть ≡
| Автор: | Сергей Оршанский, Андрей Станкевич | Ограничение времени: | 2 сек | |
| Входной файл: | lifts.in | Ограничение памяти: | 8 Мб | |
| Выходной файл: | lifts.out |
Условие
Сережа очень любит старые игры. Недавно он нашел у себя на компьютере одну старую приключенческую игру. Управляя героем, надо перемещаться по карте и собирать различные предметы.
На определенном этапе игры Сережа столкнулся с неожиданной проблемой. Для продолжения приключений герою надо перебраться через пропасть. Для этого можно использовать последовательно расположенные лифты, которые имеют вид горизонтальных платформ. Каждый лифт вертикально перемещается туда-сюда между некоторыми уровнями. Герой может переходить между соседними платформами, однако это можно сделать только в тот момент, когда они находятся на одном уровне. Аналогично с края пропасти на лифт и обратно можно перейти лишь в тот момент, когда лифт окажется на уровне края.
Каждый лифт имеет ширину равную четырем метрам. В начале герой находится на расстоянии два метра от края пропасти. Он должен закончить свое путешествие в двух метрах от противоположного края пропасти. Герой перемещается со скоростью два метра в секунду. Таким образом, если герой находится в начальном положении или в центре лифта и хочет перейти на соседний лифт (или сойти с последнего лифта на противоположный край пропасти), он должен начать движение ровно за одну секунду до того момента, когда они окажутся на одном уровне. Через две секунды герой оказывается в центре соседнего лифта (или в конечном положении).
Края пропасти находятся на одном уровне. Для каждого лифта задан диапазон высот, между которыми он перемещается, начальное положение и направление движения в начальный момент. Все лифты перемещаются со скоростью один метр в секундy. Выясните, сможет ли герой перебраться на противоположный край пропасти, и если да, то какое минимальное время ему для этого понадобится.
Формат входного файла
Первая строка входного файла содержит целое число n — количество лифтов. Следующие n строк содержат описания лифтов. Каждое описание состоит из четырех целых чисел: l, u, s — самое нижнее, самое верхнее и начальное положение лифта относительно края пропасти в метрах, и d — направление движения лифта в начальный момент (d = 1 означает, что лифт двигается вверх, d = −1 — вниз).Формат выходного файла
Выведите в выходной файл минимальное время в секундах, необходимое чтобы перебраться на противоположный край пропасти. Если перебраться на противоположный край пропасти невозможно, выведите в выходной файл −1.Ограничения
1 ≤ n ≤ 100, -100 ≤ l ≤ s ≤ u ≤ 100, l < uПримеры тестов
| № | Входной файл (lifts.in) |
Выходной файл (lifts.out) |
|---|---|---|
| 1 |
|
|