Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 1 сек | |
Входной файл: | space.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | space.out | |||
Максимальный балл: | 100 |
Для освоения Марса требуется построить исследовательскую базу. База должна состоять из N одинаковых модулей.
Каждый модуль представляет собой жилой отсек, который в основании имеет форму прямоугольника размером A × B метров.
Для повышения надежности модулей инженеры могут добавить вокруг каждого модуля дополнительный защитный слой. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину защитного слоя.
Модуль с защитным слоем, толщина которой равна D метрам, будет иметь в основании форму прямоугольника размером (A + 2D) × (B + 2D) метров.
Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером W × H метров.
При этом они должны быть организованы в виде регулярной сетки, их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.
Требуется написать программу, которая по заданным количеству и размеру модулей, а также размеру поля для их размещения, определяет максимальную толщину дополнительного защитного слоя, который можно добавить к каждому модулю.
В первом примере можно установить дополнительный защитный слой толщиной 2 метра и разместить модули на поле, как показано на рисунке.
Во втором примере жилой отсек имеет в основании размер 5 × 5 метров, а поле — размер 6 × 6 метров.
Добавить дополнительный защитный слой к модулю нельзя.
Входной файл содержит пять разделенных пробелами целых чисел: N, A, B, W, H.
Гарантируется, что без дополнительного защитного слоя все модули можно разместить в поселении описанным образом.
Выходной файл должен содержать одно целое число: максимальную возможную толщину дополнительного защитного слоя.
Если дополнительный защитный слой установить не удастся, требуется вывести число 0.
1 ≤ N, A, B, W, H ≤ 1018
1 ≤ N ≤ 1000; 1 ≤ A, B, W, H ≤ 1000.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
1 ≤ N ≤ 1000; 1 ≤ A, B, W, H ≤ 109.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
1 ≤ N ≤ 109; 1 ≤ A, B, W, H ≤ 1018.
В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
1 ≤ N ≤ 1018; 1 ≤ A, B, W, H ≤ 1018.
В этой подзадаче 9 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
№ | Входной файл (space.in ) |
Выходной файл (space.out ) |
---|---|---|
1 |
|
|
2 |
|
|