В прачечной есть K стиральных машин, которые пронумерованы с 1. Принимаемые вещи кладутся в свободную стиральную машину с минимальным номером. Известно время, когда пассажиры сдают и забирают вещи (в минутах с начала суток). Среди стиральных машин есть супер-стиральные машины, они стирают вещи в два раза быстрее. У таких машин номер кратен 5. Если время стирки было нечётным, то оно округляется в меньшую сторону. Стиралка доступна для вещей, начиная со следующей минуты, после окончания срока хранения. Если свободных машинок не находится, то вещи не принимаются в стиральную машину. Если в один момент пришло несколько клиентов, то в первую очередь, вещи принимаются у того, чья стирка займет меньшее время.
Найдите количество вещей, которое будет сдано в стиральные машины за 24 часа и номер стиралки, в которую сдаст вещи последний клиент. Входные данные В первой строке входного файла находится число K – количество стиральных машин, во второй строке файла число N – количество клиентов, сдающих свои вещи (натуральное число, не превышающее 1000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1440: время сдачи вещей и время выдачи вещей.
Выходные данные
Программа должна вывести два числа через пробел: количество сданных в стиральные машины вещей и номер стиралки, в которую примут вещи у последнего клиента, который сможет сдать вещи.
Решение (Python)
file = open(’R1_26__3vnm4.txt’)
count_machine = int(file.readline()) # количество стиральных машин
count_client = int(file.readline()) # количество клиентов
array_client = sorted(list(map(int,i.split())) for i in file)
machines = [-1] * count_machine # симулируем стиральные машины. В каждой ячейке будет записано время освобождения определенной стиральной машины
count = 0
last = 0
for start,end in array_client: # перебор клиентов
for i in range(len(machines)): # проход по стиральным машинам
if start > machines[i]: # если текущий клиент может положить вещи в определенную стиральную машину
if (i+1) % 5 == 0: # если это супер стиралка
machines[i] = start + ((end - start) // 2) # то записываем время выполнения стирки в два раза быстрее
else: # если это обычная стиралка
machines[i] = end # записываем время освобождения
count += 1
last = i + 1 # запоминаем номер стиральной машины, куда положил последний клиент
break # сбрасываем цикл - переходим к следующему клиенту
print(count,last)