Задача F. Фермерские будни
Условие
Год назад Флатландию потряс серьезный экономический кризис,
после которого, с целью снижения издержек, фермер Джон и фермер Билл
решили объединить свои фермы. За год совместной продуктивной
работы на объединенной территории было построено четыре сарая.
Однако последствия кризиса в последнее время ощущаются все меньше,
да и совместное ведение хозяйства — дело непростое. Поэтому фермеры
решили снова разделить свои фермы.
Для раздела ферм решено было построить забор. Разумеется, прежде чем
приступить к строительству, фермеры взяли карту совместного хозяйства
и стали обсуждать возможное положение забора. Забор должен представлять
собой прямую линию. Поскольку по закону границы участков должны
быть направлены либо с севера на юг, либо с запада на восток, забор
на карте должен представлять собой прямую, параллельную краю карты —
вертикальную либо горизонтальную.
Единственная проблема — четыре построенных за год совместной
работы сарая. Разумеется, каждому фермеру в результате раздела должно
достаться по два сарая. Поэтому после постройки забора два сарая должны
оказаться с одной стороны от него, а два других — с другой.
Помогите фермерам найти такое положение для забора. Забор может проходить
непосредственно вдоль стены сарая.
Формат входного файла
Входной файл содержит четыре четверки целых чисел. Каждая четверка
описывает один сарай. Первые два числа в описании сарая — это координаты
на карте его левого нижнего угла, следующие два числа — координаты
правого верхнего угла.
Система координат размещена таким образом, что ось
OX направлена
слева направо, а ось
OY — снизу вверх. Оси координат параллельны краям карты.
Стороны сараев также параллельны краям карты. Сараи не имеют общих точек.
Каждый сарай имеет ненулевую площадь.
Формат выходного файла
Если построить забор, удовлетворяющий всем условиям, невозможно, выведите
на первой строке выходного файла слово
Impossible.
В противном случае на первой строке выведите слово
Vertical если
забор следует построить параллельно вертикальному краю карты или слово
Horizontal, если забор следует построить параллельно горизонтальному
краю карты.
На следующей строке выведите координату
x всех точек забора, если
он должен быть вертикальным, либо координату
y всех точек забора, если он
должен быть горизонтальным. Выведенная координата должна быть целым числом
(несложно показать, что если забор можно построить, то его можно построить так, чтобы
искомая координата была целой).
Ограничения
Все координаты неотрицательны и не превышают 10
9.
Примеры тестов
| № |
Входной файл (farm.in) |
Выходной файл (farm.out) |
|---|
| 1 |
0 0 1 1
1 2 3 3
4 0 5 3
3 4 6 7
|
Vertical
3
|
| 2 |
0 0 1 1
1 2 3 3
4 0 5 2
2 4 6 7
|
Horizontal
2
|
| 3 |
0 0 1 1
1 2 3 3
4 0 5 3
2 4 6 7
|
Impossible
|
Задача G. На лифтах через пропасть
Условие
Сережа очень любит старые игры. Недавно он нашел у себя
на компьютере одну старую приключенческую игру. Управляя героем,
надо перемещаться по карте и собирать различные предметы.
На определенном этапе игры Сережа столкнулся с неожиданной проблемой.
Для продолжения приключений герою надо перебраться через пропасть.
Для этого можно использовать последовательно расположенные лифты,
которые имеют вид горизонтальных
платформ. Каждый лифт вертикально перемещается туда-сюда между некоторыми уровнями.
Герой может переходить между соседними платформами, однако это можно сделать
только в тот момент, когда они находятся на одном уровне. Аналогично
с края пропасти на лифт и обратно можно перейти лишь в тот момент, когда лифт
окажется на уровне края.
Каждый лифт имеет ширину равную четырем метрам. В начале герой
находится на расстоянии два метра от края пропасти.
Он должен закончить свое путешествие в двух метрах от противоположного
края пропасти.
Герой перемещается со скоростью два метра в секунду. Таким образом, если
герой находится в начальном положении или в центре лифта и хочет
перейти на соседний лифт (или сойти с последнего лифта на противоположный
край пропасти), он должен начать движение ровно за
одну секунду до того момента, когда они окажутся на одном уровне.
Через две секунды герой оказывается
в центре соседнего лифта (или в конечном положении).
Края пропасти находятся на одном уровне.
Для каждого лифта задан диапазон высот, между которыми он перемещается,
начальное положение и направление движения в начальный момент.
Все лифты перемещаются со скоростью один метр в секунд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 |
4
-1 2 1 -1
0 3 0 1
-4 0 0 -1
-2 1 0 -1
|
29
|
Задача J. Лесопилка
Условие
Недавно на лесопилку, где работает Вася поступил
новый заказ. Для постройки нового дома мэру соседнего
города требуется a досок длины x футов
и b досок длины y футов.
Поскольку на лесопилке имеется только неограниченный запас досок
длины z футов, Васе поручили исполнить заказ клиента, распилив
имеющиеся доски на меньшие. Вася хочет закончить работу как можно
быстрее, поэтому он хочет выполнить заказ, сделав как можно
меньше распилов. При этом количество использованных досок длины
z роли не играет, кроме того, часть досок, образовавшихся в результате
распила, может не требоваться для заказа и остаться на лесопилке.
Например, если на лесопилке имеются доски длины 80, а клиенту
требуется две доски длины 30 и семь досок длины 20, то достаточно
сделать семь распилов: одну доску распилить двумя распилами
на доски длины 20, 30 и 30, одну тремя распилами на четыре доски
длины 20 и одну двумя распилами на доски длины 20, 20 и 40.
Доска длины 40 клиенту не нужна, она останется на лесопилке, остальные
доски будут отправлены клиенту.
Формат входного файла
Входной файл содержит целые числа
a,
x,
b,
y и
z.
Формат выходного файла
Выведите в выходной файл минимальное количество распилов,
которые требуется сделать для того, чтобы выполнить заказ.
Ограничения
Все числа положительны и не превышают 300,
x ≤
z,
y ≤
z,
x ≠
y.
Примеры тестов
| № |
Входной файл (sawmill.in) |
Выходной файл (sawmill.out) |
|---|
| 1 |
2 30 7 20 80
|
7
|
