- Описание
- Отправленные решения
102. Космическое поселение
Для освоения Марса требуется построить исследовательскую базу. База должна состоять из n одинаковых модулей, каждый из которых представляет собой прямоугольник.
Каждый модуль представляет собой жилой отсек, который имеет форму прямоугольника размером a на b метров. Для повышения надёжности модулей инженеры могут добавить вокруг каждого модуля слой дополнительной защиты. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину дополнительной защиты. Модуль с защитой, толщина которой равна d метрам, будет иметь форму прямоугольника размером (a+2d)(b+2d) метров.
Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером wh метров. При этом они должны быть организованы в виде регулярной сетки: их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.
Требуется написать программу, которая по заданным количеству и размеру модулей, а также размеру поля для их размещения, определяет максимальную толщину слоя дополнительной защиты, который можно добавить к каждому модулю.
Формат ввода
Входной файл содержит пять разделенных пробелами целых чисел: n, a, b, w и h (). Гарантируется, что без дополнительной защиты все модули можно разместить в поселении описанным образом.
Формат вывода
Выходной файл должен содержать одно целое число: максимальную возможную толщину дополнительной защиты. Если дополнительную защиту установить не удастся, требуется вывести число 0.
Примечание
Для входных данных 11 3 2 21 25 можно установить дополнительную защиту толщиной 2 метра и разместить модули на поле, как показано на рисунке.
Ограничения
Ограничение времени
1 с
Ограничение памяти
64 МБ
Пример 1
1 1 1 1 1
0
Пример 2
1 1 1 3 3
1