Задача C. Место у прохода, пожалуйста ≡
| Автор: | Жюри ВКОШП-2008 | Ограничение времени: | 2 сек | |
| Входной файл: | aisle.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | aisle.out |
Условие
Те, кто часто путешествуют самолетами, любят просить место у прохода. Ведь если сидеть у прохода, можно встать и прогуляться, не тревожа своих соседей.
Компания "Аэротрам" готовит к производству новый самолет "T-239-n". Перед инженерами встала задача спланировать организацию салона, чтобы как можно больше мест было у прохода. Будем использовать следующую упрощенную математическую модель салона самолета. В горизонтальном сечении салон представляет собой прямоугольник длиной l и шириной w сантиметров. Кресло представляет собой прямоугольник размером x на y сантиметров и должно быть расположено в салоне так, чтобы его сторона длиной x была параллельна стороне салона длиной l. Проход представляет собой полосу шириной a, параллельную стороне салона длиной l. Проход идет вдоль всего салона.
В салоне требуется разместить n кресел. Помогите инженерам компании выяснить, как организовать
салон, чтобы максимальное количество кресел было расположено у прохода. В салоне
необходимо сделать хотя бы один проход. Кресло считается расположенным у прохода, если оно
имеет хотя бы одну общую сторону с проходом.
В первом примере оптимально расположить кресла, например, следующим образом:
Формат входного файла
Формат входного файла Входной файл содержит шесть целых чисел: n, l, w, x, y и a.Формат выходного файла
Формат выходного файла Если разместить n кресел в салоне так, чтобы был хотя бы один проход, невозможно, выведите в выходной файл единственное число − 1. Иначе выведите максимальное количество кресел, которое можно разместить у прохода.Ограничения
1 ≤ n, l, w, x, y, a ≤ 104
Примеры тестов
| № | Входной файл (aisle.in) |
Выходной файл (aisle.out) |
|---|---|---|
| 1 | |
|
| 2 | |
|