Условие

Организаторы детского праздника планируют надуть для него M воздушных шариков. С этой целью они пригласили N добровольных помощников, i-й среди которых надувает шарик за T_i минут, однако каждый раз после надувания Z_i шариков устает и отдыхает Yi минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).

Примеры

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

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

Решение

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

// Класс для хранения данных о помощнике
data class Helper(val t: Int, val z: Int, val y: Int)

// Функция для вычисления времени надувания заданного числа шариков одним помощником
fun timeToBlow(helper: Helper, balloons: Int): Long {
    if (balloons == 0) return 0L
    val fullCycles = (balloons - 1) / helper.z // Количество полных циклов до последнего шарика
    val totalTime = fullCycles * (helper.t.toLong() * helper.z + helper.y) // Время на полные циклы
    val remainingBalloons = balloons - fullCycles * helper.z // Оставшиеся шарики
    return totalTime + remainingBalloons * helper.t.toLong() // Добавляем время на остаток
}

// Функция для поиска минимального времени и распределения шариков
fun solve(m: Int, n: Int, helpers: List<Helper>): Pair<Long, IntArray> {
    var left = 0L // Нижняя граница времени
    var right = 15000L * 100 // Верхняя граница времени
    
    lateinit var bestDistribution: IntArray // Лучшее распределение шариков
    
    // Бинарный поиск по времени
    while (left < right) {
        val mid = left + (right - left) / 2
        var totalBalloons = 0
        val current = IntArray(n) // Текущее распределение
        
        // Считаем, сколько шариков каждый помощник надует за время mid
        for (i in 0 until n) {
            val h = helpers[i]
            var lo = 0L
            var hi = m.toLong()
            while (lo <= hi) {
                val balloons = lo + (hi - lo) / 2
                if (timeToBlow(h, balloons.toInt()) <= mid) {
                    current[i] = balloons.toInt()
                    lo = balloons + 1
                } else {
                    hi = balloons - 1
                }
            }
            totalBalloons += current[i]
        }
        
        // Если надутых шариков достаточно, сохраняем распределение и уменьшаем время
        if (totalBalloons >= m) {
            bestDistribution = current.copyOf()
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    // Корректируем распределение до ровно m шариков
    var sum = bestDistribution.sum()
    for (i in 0 until n) {
        while (sum > m && bestDistribution[i] > 0) {
            bestDistribution[i]--
            sum--
        }
    }
    
    return left to bestDistribution
}

fun main(args: Array<String>) {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    // Читаем количество шариков и помощников
    val (m, n) = reader.readLine().split(" ").map { it.toInt() }
    
    // Читаем данные о помощниках
    val helpers = mutableListOf<Helper>()
    repeat(n) {
        val (t, z, y) = reader.readLine().split(" ").map { it.toInt() }
        helpers.add(Helper(t, z, y))
    }
    
    // Решаем задачу и получаем время и распределение
    val (time, distribution) = solve(m, n, helpers)
    
    // Выводим результат
    writer.write("$time\\n")
    writer.write(distribution.joinToString(" "))
    writer.newLine()
    
    reader.close()
    writer.close()
}