시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 12 | 6 | 6 | 50.000% |
Для освоения Марса требуется построить исследовательскую базу. База должна состоять из n одинаковых модулей, каждый из которых представляет собой прямоугольник.
Каждый модуль представляет собой жилой отсек, который имеет форму прямоугольника размером a × b метров. Для повышения надежности модулей инженеры могут добавить вокруг каждого модуля слой дополнительной защиты. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину дополнительной защиты. Модуль с защитой, толщина которой равна d метрам, будет иметь форму прямоугольника размером (a + 2d) × (b + 2d) метров.
Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером w × h метров. При этом они должны быть организованы в виде регулярной сетки: их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.
Требуется написать программу, которая по заданным количеству и размеру модулей, а также размеру поля для их размещения, определяет максимальную толщину слоя дополнительной защиты, который можно добавить к каждому модулю.
Входной файл содержит пять разделенных пробелами целых чисел: n, a, b, w и h (1 ≤ n, a, b, w, h ≤ 1018). Гарантируется, что без дополнительной защиты все модули можно разместить в поселении описанным образом.
Выходной файл должен содержать одно целое число: максимальную возможную толщину дополнительной защиты. Если дополнительную защиту установить не удастся, требуется вывести число 0.
번호 | 배점 | 제한 |
---|---|---|
1 | 26 | 1 ≤ n ≤ 1000, 1 ≤ a, b, w, h ≤ 1000 |
2 | 23 | 1 ≤ n ≤ 1000, 1 ≤ a, b, w, h ≤ 109 |
3 | 24 | 1 ≤ n ≤ 109, 1 ≤ a, b, w, h ≤ 1018 |
4 | 27 | 1 ≤ n ≤ 1018, 1 ≤ a, b, w, h ≤ 1018 |
11 2 3 21 25
2
1 5 5 6 6
0
В первом примере можно установить дополнительную защиту толщиной 2 метра и разместить модули на поле, как показано на рисунке.
Жилой модуль | Жилой модуль с дополнительной защитой толщиной 2 | Размещение модулей на поле |
---|
Во втором примере жилой отсек имеет размер 5 × 5 метров, а поле – размер 6 × 6 метров. Добавить дополнительную защиту к модулю нельзя.
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2016 2번