НачалоПодразделы
Другие разделы
Дата и время
20/12/2024 13:50:40
Занятие 3
A. Поздравительные открытки B. Открытки и конверты C. Разложение D. "Грузите апельсины бочках братья Карамазовы" E. Поле для крикета F. Водопровод
F. Водопровод
Рекурсивный переборОлимпиадные задачи на русском языке
| 03/07/2006 | Лето 2006 дорешивание ( 9E) |
| 24/07/2006 | Лето 2006 - 9 (нет результатов) (E) |
| 26/09/2007 | Занятие 3 (F) |
Ограничения: время – 3s/6s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке `(x_1,\ y_1)`, а вторая – в точке `(x_2,\ y_2)`.
К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 градусов. Требуется, зная длины отрезков труб `L_1,\ L_2,\ …,\ L_K` и количество отрезков каждой длины `C_1,\ C_2,\ …,\ C_K`, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.
Ограничения: `1\ ≤\ K\ ≤\ 4`, `1\ ≤\ x_1,\ y_1,\ x_2,\ y_2,\ L_i\ ≤\ 1000`, `1\ ≤\ C_i\ ≤\ 10`, все числа целые.
Ввод
В первой строке находятся числа `x_1,\ y_1,\ x_2,\ y_2,\ K`, затем `2K` чисел: `L_1,\ L_2,\ …,\ L_K,\ C_1,\ C_2,\ …,\ C_K`.
Вывод
Вывести одно число – минимальное количество нужных отрезков труб или `-1`, если соединение невозможно.
Пример ввода 1
5 5 5 6 1 2 10
Пример вывода 1
-1
Пример ввода 2
20 10 60 50 2 70 30 2 2
Пример вывода 2
4
