Условие

Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Лёгкую Задачу. Ответственный секретарь Оргкомитета напечатал её условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за х секунд, а другой – за y. (Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии) Помогите ему выяснить, какое минимальное время для этого потребуется.

Примеры

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

Ввод: 5 1 2 Вывод: 4

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

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

    // Читаем количество копий (n) и время ксероксов (x, y)
    val (n, x, y) = reader.readLine().split(" ").map(String::toInt)

    val minTime = minOf(x, y) // Минимальное время для одной копии
    var left = 0L // Левая граница бинарного поиска
    var right = (n - 1).toLong() * minTime // Правая граница (грубая оценка максимального времени)

    // Бинарный поиск минимального времени, за которое можно сделать (n - 1) копий
    while (left < right) {
        val mid = (left + right) / 2 // Среднее значение диапазона
        val copies = mid / x + mid / y // Количество копий, сделанных за это время
        if (copies >= (n - 1)) right = mid else left = mid + 1 // Корректируем границы поиска
    }

    writer.write((left + minTime).toString()) // Выводим итоговое время, добавляя время первой копии
    writer.newLine()
    writer.flush()
    writer.close()
}