printРабочее место участника

printЗадачи

2269. Космическое поселение

Ограничения: время – 1s/2s, память – 256MiB Ввод: space.in или стандартный ввод Вывод: space.out или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Для освоения Марса требуется построить исследовательскую базу. База должна состоять из `n` одинаковых модулей. Каждый модуль представляет собой жилой отсек, который в основании имеет форму прямоугольника размером `a times b` метров.
Для повышения надежности модулей инженеры могут добавить вокруг каждого модуля дополнительный защитный слой. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину защитного слоя. Модуль с защитным слоем, толщина которой равна `d` метрам, будет иметь в основании форму прямоугольника размером `(a + 2d) times (b + 2d)` метров.
Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером `w times h` метров. При этом они должны быть организованы в виде регулярной сетки: их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.
Требуется написать программу, которая по заданным количеству и размеру модулей, а также размеру поля для их размещения, определяет максимальную толщину дополнительного защитного слоя, который можно добавить к каждому модулю.
Формат входного файла
Входной файл содержит пять разделенных пробелами целых чисел: `n`, `a`, `b`, `w` и `h` (`1 ≤ n,\ a,\ b,\ w,\ h ≤ 10^{18}`). Гарантируется, что без дополнительного защитного слоя все модули можно разместить в поселении описанным образом.
Формат выходного файла
Выходной файл должен содержать одно целое число: максимальную возможную толщину дополнительного защитного слоя. Если дополнительный защитный слой установить не удастся, требуется вывести число 0.

Пример ввода 1

11 2 3 21 25

Пример вывода 1

2

Пример ввода 2

1 5 5 6 6

Пример вывода 2

0
Пояснение к примерам
В первом примере можно установить дополнительный защитный слой толщиной 2 метра и разместить модули на поле, как показано на рисунке.

33496.png

Во втором примере жилой отсек имеет в основании размер `5 times 5` метров, а поле – размер `6 times 6` метров. Добавить дополнительный защитный слой к модулю нельзя.
Описание подзадач и системы оценивания
Подзадача 1 (26 баллов)
`1 ≤ n ≤ 1000`, `1 ≤ a,\ b,\ w,\ h ≤ 1000`.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 2 (23 балла)
`1 ≤ n ≤ 1000`, `1 ≤ a,\ b,\ w,\ h\ ≤ 10^9`.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 3 (до 24 баллов)
`1 ≤ n ≤ 10^9`, `1 ≤ a,\ b,\ w,\ h\ ≤ 10^{18}`.
В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
Подзадача 4 (до 27 баллов)
`1 ≤ n ≤ 10^{18}`, `1 ≤ a,\ b,\ w,\ h\ ≤ 10^{18}`.
В этой подзадаче 9 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
Источник: региональный этап Всероссийской олимпиады по информатике 2015/2016, http://neerc.ifmo.ru/school/
loading