Задача №113097. Космическое поселение
Для освоения Марса требуется построить исследовательскую базу. База должна состоять из \(n\) одинаковых модулей, каждый из которых представляет собой прямоугольник.
Каждый модуль представляет собой жилой отсек, который имеет форму прямоугольника размером \(a \times b\) метров. Для повышения надежности модулей инженеры могут добавить вокруг каждого модуля слой дополнительной защиты. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину дополнительной защиты. Модуль с защитой, толщина которой равна \(d\) метрам, будет иметь форму прямоугольника размером \((a + 2d) \times (b + 2d)\) метров.
Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером \(w \times h\) метров. При этом они должны быть организованы в виде регулярной сетки: их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.
Требуется написать программу, которая по заданным количеству и размеру модулей, а также размеру поля для их размещения, определяет максимальную толщину слоя дополнительной защиты, который можно добавить к каждому модулю.
Строка содержит пять разделенных пробелами целых чисел: \(n\), \(a\), \(b\), \(w\) и \(h\) (\(1 \le n, a, b, w, h \le 10^{18}\)). Гарантируется, что без дополнительной защиты все модули можно разместить в поселении описанным образом.
Ответ должен содержать одно целое число: максимальную возможную толщину дополнительной защиты. Если дополнительную защиту установить не удастся, требуется вывести число 0.
В первом примере можно установить дополнительную защиту толщиной 2 метра и разместить модули на поле, как показано на рисунке.
\(1 \le n \le 1000, 1 \le a, b, w, h \le 1000\).
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены
\(1 \le n \le 1000, 1 \le a, b, w, h \le 10^9\).
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
\(1 \le n \le 10^9 , 1 \le a, b, w, h \le 10^{18}\).
В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
\(1 \le n \le 10^{18} , 1 \le a, b, w, h \le 10^{18}\).
В этой подзадаче 9 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
11 2 3 21 25
2
1 5 5 6 6
0