Источник: https://kpolyakov.spb.ru/
В операционном зале есть N банкоматов, работающих круглосуточно. Все банкоматы пронумерованы. В течение дня M клиентов хотят воспользоваться банкоматом. Клиенты обслуживаются в порядке общей очереди. Если в один момент подошли несколько клиентов, то они становятся в очередь в порядке расположения данных в файле. Клиент, стоящий первым в очереди, подходит к первому освободившемуся банкомату (если таких несколько – к банкомату с наименьшим номером). Обслуживание очередного клиента может начаться в ту же минуту, когда банкомат станет свободным. Известно время в минутах от начала суток, когда клиент подошёл к банкомату, и время его обслуживания.
Определите наименьшее количество клиентов, которые были обслужены одним банкоматом за 24 часа, и время начала обслуживания последнего клиента этим банкоматом. Последним обслуженным клиентом считается тот, который подошёл к банкомату до окончания суток (его обслуживание могло закончиться в следующие сутки).
Входные данные
В первой строке входных данных задается два числа: N — количество банкоматов и M – количество клиентов. В каждой из последующих M строк содержится информация по одному клиенту: время начала обслуживания клиента (в минутах с начала суток) и время обслуживания (в минутах).
Выходные данные
Запишите в ответе два числа: наименьшее количество клиентов, которые были обслужены одним банкоматом за 24 часа, и время начала обслуживания последнего клиента этим банкоматом.
Пример входного файла:
При таких исходных данных наименьшее число клиентов (2) обслужит 2-й банкомат: это клиенты со временем обслуживания 12 и 8. Последний из них начинает работу с банкоматом на 18-й минуте. Ответ: 2 18.
Решение 1
with open(’26.txt’) as F:
N, M = map( int, F.readline().split() )
data = []
for _ in range(M):
t0, delta = map(int, F.readline().split())
data.append( (t0, delta) )
data.sort( key = lambda x: x[0] )
tFree = [0]*N
stats = [(0,0)]*N
TMAX = 24*60
i = 0
queue = []
for t in range(TMAX):
while i < len(data) and data[i][0] <= t:
queue.append( data[i][1] )
i += 1
while queue:
delta, placed = queue[0], False
for k in range(N):
if tFree[k] <= t:
tFree[k] = t + delta
stats[k] = (stats[k][0]+1, t)
placed = True
queue.pop(0)
break
if not placed: break
print( *min( stats, key = lambda x: x[0] ) )
Решение 2
f = open(’26.txt’)
n, m = map(int, f.readline().split())
a = [list(map(int, f.readline().split())) for i in range(m)]
a = sorted(a, key = lambda x: x[0])
banks = [-1] * n
banks_start = [-1]*n
cnt_banks = [0] * n
for start, time in a:
f = 0
end = start + time
for j in range(len(banks)):
if start <= 1440:
if start >= banks[j]:
banks[j] = end
cnt_banks[j] += 1
f = 1
banks_start[j] = start
break
if f == 0:
min_t = min(banks)
if min_t < 1440:
ind = banks.index(min_t)
banks[ind] += time
banks_start[ind] = min_t
cnt_banks[ind] += 1
print(min(cnt_banks), banks_start[cnt_banks.index(min(cnt_banks))])