Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 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 |
|
|