Условие

Для освоения Марса требуется построить исследовательскую базу. База должна состоять из n одинаковых модулей, каждый из которых представляет собой прямоугольник.

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

Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером wh метров. При этом они должны быть организованы в виде регулярной сетки: их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.

Требуется написать программу, которая по заданным количеству и размеру модулей, а также размеру поля для их размещения, определяет максимальную толщину слоя дополнительной защиты, который можно добавить к каждому модулю.

Примеры

Ввод: 1 1 1 1 1 Вывод: 0

Ввод: 1 1 1 3 3 Вывод: 1

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.StringTokenizer
import kotlin.math.min

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val tokenizer = StringTokenizer(reader.readLine())

    // Читаем количество прямоугольников (n), их ширину (a) и высоту (b), а также размеры области (w, h)
    val n = tokenizer.nextToken().toLong()
    val a = tokenizer.nextToken().toLong()
    val b = tokenizer.nextToken().toLong()
    val w = tokenizer.nextToken().toLong()
    val h = tokenizer.nextToken().toLong()

    // Функция проверяет, можно ли разместить n прямоугольников с дополнительным запасом d
    fun canFit(d: Long, width: Long, height: Long): Boolean {
        val newWidth = width + 2 * d // Увеличиваем ширину прямоугольника на 2*d
        val newHeight = height + 2 * d // Увеличиваем высоту на 2*d
        val cols = w / newWidth // Вычисляем количество столбцов
        val rows = h / newHeight // Вычисляем количество рядов
        return cols * rows >= n // Проверяем, достаточно ли места
    }

    // Функция выполняет бинарный поиск максимального возможного запаса d
    fun maxProtection(): Long {
        var left = 0L
        var right = min(w, h) // Верхняя граница поиска (размер минимальной стороны области)
        while (left < right) {
            val mid = (left + right + 1) / 2 // Средний возможный запас
            if (canFit(mid, a, b) || canFit(mid, b, a)) { // Проверяем обе ориентации прямоугольников
                left = mid // Увеличиваем нижнюю границу
            } else {
                right = mid - 1 // Уменьшаем верхнюю границу
            }
        }
        return left // Возвращаем максимальный возможный запас
    }

    writer.write(maxProtection().toString()) // Выводим результат
    writer.newLine()

    reader.close()
    writer.close()
}