Организаторы детского праздника планируют надуть для него m воздушных шариков. С этой целью они пригласили n добровольных помощников, i-й среди которых надувает шарик за ti минут, однако каждый раз после надувания zi шариков устает и отдыхает yi минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).
Входные данные
В первой строке входных данных задаются числа m и n (0≤m≤15000,1≤n≤1000). Следующие n строк содержат по три целых числа — ti, zi и yi соответственно (1≤ti,yi≤100,1≤zi≤1000).
Выходные данные
Выведите в первой строке число T — время, за которое будут надуты все шарики. Во второй строке выведите n чисел — количество шариков, надутых каждым из приглашенных помощников. Если распределений шариков несколько, выведите любое из них.
Пример
входные данные
1 2
2 1 1
1 1 2
выходные данные
1
0 1
Ответ
from random import randint, seed
from time import time
import heapq
seed(42)
start = time()
m,n = 15000,1000
#t,z,y = map(list,zip(*[map(int, input().split()) for _ in range(n)]))
t,z,y = map(list,zip(*[[randint(1,100) for i in range(3)] for j in range(n)]))
counter = [0]*n
times = list(zip(t,range(n)))
heapq.heapify(times)
for _ in range(m):
next_time, i = heapq.heappop(times)
counter[i] += 1
heapq.heappush(times, (next_time + t[i] + y[i]*(counter[i]%z[i]==0), i))
print(f’Время расчета {time()-start:.3f}c’)
print(next_time)
print(*counter[:10])
КодВыделить код
Время расчета 0.028c
368
4 3 12 26 5 6 28 5 5 4