Задача 3. Метрострой ≡

Условие

Буровая установка «Мегабур 2022» для прокладки туннелей метро Байтсбурга имеет n двигателей. Питание установки устроено таким образом, что на все двигатели подается одно и то же целочисленное напряжение x.

У каждого двигателя есть два режима, если на него подается напряжение x, то i-й двигатель работает в первом режиме, если x ≤ z_i и во втором режиме, если x > z_i.

При этом i-й двигатель характеризуется удельной мощностью a_i в первом режиме и b_i во втором режиме. Это означает, что увеличение напряжения на 1 когда двигатель находится в первом режиме, приводит к увеличению его мощности на a_i, а во втором режиме приводит к увеличению его мощности на b_i. Иначе говоря, при подаче напряжения x, если i-й двигатель находится в первом режиме он работает с мощностью a_i x, а если во втором режиме, то с мощностью a_i z_i + b_i(x − z_i).

Для прокладки туннеля суммарная мощность двигателей должна быть не меньше p. Какое минимальное целочисленное напряжение необходимо подать на установку, чтобы суммарная мощность двигателей была больше или равна p?

Формат входных данных

Первая строка ввода содержит целые числа n и p.

Следующие n строк описывают двигатели и содержат по три целых числа z_i, a_i, b_i.

Формат выходных данных

Требуется вывести одно целое число — минимальное напряжение, которые необходимо подать на установку.

Ограничения

1 ≤ n ≤ 100, 1 ≤ p ≤ 10¹²

1 ≤ z_i ≤ 10⁹, 1 ≤ a_i, b_i ≤ 10⁴

Примеры тестов

1 6
4 1 2

5

3 15
2 3 3
4 2 1
5 2 2

3

Разбор

Подзадача 1

Заметим, что если двигатель всего один, то существует два случая: необходимая мощность достигается при работе двигателя в первом режиме или во втором. При этом легко понять, какой режим необходим, если сравнить z₁ a₁ и p. Таким образом, решение первой подзадачи выглядит так:

if p <= z[0] * a[0]:
    print(ceil(p / a))
else:
    print(z + ceil((p - z[0] * a[0]) / b)

Подзадача 2

Ограничения этой подзадачи позволяли явно перебрать и найти минимальный x, удовлетворяющий условию задачи.

x = 1
while True:
    q = 0
    for i in range(n):
        if x <= z[i]:
            q += a[i] * x
        else:
            q += a[i] * z[i] + b[i] * (x - z[i])
    if q >= p:
        break
    c += 1

print(x)

Подзадача 3

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

Первый случай выполняется, если n∑i = 1a_i z₁ ⩾ p. В таком случае, ответ — pn∑i = 1a_i, округленное вверх. Иначе, ответ можно найти как p − n∑i = 1a_i z₁n∑i = 1b_i.

Подзадача 4

1. либо оба двигателя будут работать в первом режиме (x ∈ [0, z₁)), тогда ответ — ceil(pa₁ + a₂);
2. либо двигатель 1 будет работать во втором режиме, а двигатель 2 — в первом (x ∈ [z₁, z₂)), тогда ответ — ceil(p − (a₁ + a₂) ⋅ z₁b₁ + a₂);
3. либо оба будут прокладывать туннель во втором режиме (x ∈ [z₂, ∞)), ответ в этом случае — ceil(p − (a₁ + a₂) ⋅ z₁ − (b₁ + a₂) ⋅ (z₂ − z₁)b₁ + b₂).

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

Здесь намеренно не рассматривается отдельно случай, когда z₁ = z₂, это возможно так как не существует таких x, которые попадают в полуинтервал [z₁, z₂) = varnothing .

Полное решение, способ 1

Давайте обобщим решение предыдущей подзадачи на n > 2. Отсортируем двигатели по z_i. Точно так же у нас будет n + 1 непересекающийся полуинтервал, объединение таких полуинтервалов будет давать числовой луч [0,  + ∞).

В каждом интервале [z_i, z_i + 1) (считаем, что z₀ = 0 и z_n + 1 = ∞) можно находить минимальный x при котором достигается необходимая мощность, как p − S(i)j − 1∑i = 1b_i + n∑i = ja_i, округленное вверх. Функцией S(i) здесь обозначена мощность, которая достигается при x = z_i, ее можно найти по формуле i − 1∑k = 1(z_k − z_k − 1)(k − 1∑i = 1b_i + n∑i = ka_i).

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

Время работы такого решения O(n²) или O(nlog n), если немного оптимизировать.

Полное решение, способ 2

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

Время работы такого решения O(nlog n).