UniLecs #Task. Детский праздник

Published in

UniLecs

2 min readNov 11, 2019

Задача: для организации детского праздника необходимо надуть M воздушных шариков. Для этого организаторы позвали N добровольцев, i-й среди которых надувает шарик за Ti минут, однако каждый раз после надувания Zi шариков устает и отдыхает Yi минут.

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

Примечание: если доброволец надул шарик и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу же после надувания последнего шарика, а не после отдыха.

Входные данные: M, N — натуральные числа, где 0<=M<=1000; 1<=N<=20.

List — список из N наборов, каждый набор содержит по 3 значения для Ti, Zi, Yi соот-но, где 1<=Ti, Yi<=100; 1<=Zi<=1000.

Вывод: минимально возможное время, за которое будут надуты все шарики.

Пример:

1. M = 10; N = 3;

List = { (T: 1, Z: 2, Y: 3),

(T: 3, Z: 10, Y: 3),

(T: 2, Z: 4, Y: 3) }

Answer = 8;

2. M = 3; N = 2;

List = { (T: 2, Z: 2, Y: 5),

(T: 1, Z: 1, Y: 10) }

Answer = 4;

Разбор

Будем решать задачу двоичным поиском по ответу. Пусть t — возможное время надувания всех шаров. Посчитаем, сколько шаров надует за время t каждый из помощников, с учетом времени отдыха.

Просуммируем полученные числа — сумма должна быть не меньше, чем M. Это делает функция check(t), которая возвращает True, если можно надуть за время t нужное количество шаров и False в противном случае.

Определим левую и правую границы для двоичного поиска. В качестве левой границы нужно взять такое время t, за которое нельзя надуть M шаров. Но при этом во входных данных возможно значение M=0, ответом для которого будет 0, поэтому возьмем в качестве левой границы t=−1. В качестве правой границы можно взять значение t=1000∗200 — за такое время один помощник успеет надуть 1000 шаров, даже если он будет надувать один шар за 100 секунд и после каждого шара отдыхать еще 100 секунд (наиболее «медленный» помощник).

Детали смотрите в реализации.