6D. Space settlement.py

"""
Для освоения Марса требуется построить исследовательскую базу. База должна состоять
из n одинаковых модулей, каждый из которых представляет собой прямоугольник.
Каждый модуль представляет собой жилой отсек, который имеет форму прямоугольника
размером a на b метров. Для повышения надежности модулей инженеры могут добавить
вокруг каждого модуля слой дополнительной защиты. Толщина этого слоя должна составлять
целое число метров, и все модули должны иметь одинаковую толщину дополнительной
защиты. Модуль с защитой, толщина которой равна d метрам, будет иметь форму прямоугольника
размером (a+2d)(b+2d) метров.
Все модули должны быть расположены на заранее подготовленном прямоугольном поле
размером wh метров. При этом они должны быть организованы в виде регулярной сетки:
их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы
одинаково.
Требуется написать программу, которая по заданным количеству и размеру модулей,
а также размеру поля для их размещения, определяет максимальную толщину слоя дополнительной
защиты, который можно добавить к каждому модулю.

Формат ввода
Входной файл содержит пять разделенных пробелами целых чисел: n, a, b, w и h (1
≤ n, a, b, w, h ≤ 1018). Гарантируется, что без дополнительной защиты все модули
можно разместить в поселении описанным образом.

Формат вывода
Выходной файл должен содержать одно целое число: максимальную возможную толщину
дополнительной защиты. Если дополнительную защиту установить не удастся, требуется
вывести число 0.

Пример 1
Ввод
Вывод
1 1 1 1 1

0

Пример 2
Ввод
Вывод
1 1 1 3 3

1

Примечания
Для входных данных 11 3 2 21 25 можно установить дополнительную защиту толщиной
2 метра и разместить модули на поле, как показано на рисунке.
"""


def max_num(w, a, d):
    return w // (a + 2 * d)


def check(d, params):
    n, a, b, w, h = params

    max1 = max_num(w, a, d) * max_num(h, b, d)
    max2 = max_num(h, a, d) * max_num(w, b, d)

    return max(max1, max2) >= n


def rfind(l, r, params):
    while l < r:
        m = (l + r + 1) // 2
        if check(m, params):
            l = m
        else:
            r = m - 1

    return l


def fun(n, a, b, w, h):
    """
    >>> fun(1, 1, 1, 1, 1)
    0
    >>> fun(1, 1, 1, 3, 3)
    1
    >>> fun(11, 3, 2, 21, 25)
    2
    """

    a, b = sorted([a, b])
    w, h = sorted([w, h])

    return rfind(0, h, (n, a, b, w, h))


n, a, b, w, h = map(int, input().split())
print(fun(n, a, b, w, h))


# print(f">>> fun({n}, {a}, {b}, {w}, {h})")
# print(f"    {fun(n, a, b, w, h)}")


# if __name__ == "__main__":
#     import doctest

#     doctest.testmod()