В детском летнем лагере есть А комнат, предназначенных для размещения приехавших детей. Все комнаты пронумерованы, начиная с единицы. Дети в лагере приезжают и уезжают группами. Известно время, в которое группы детей заселяются в комнаты, и время, в которое они планируют их освободить, а также количество комнат, которое потребуется для того, чтобы разместить всю группу детей сразу. Каждая группа детей заселяется в свободные номера с наименьшими индексами. Известно, что если несколько групп детей приехали в одинаковое время, то прежде всего заселяются группы, которые планируют уехать раньше и для размещения которых требуется меньшее количество номеров. На заселение и выселение детей уходит одна минута. Со следующей минуты можно заселять в освободившуюся комнату других детей. Если группа детей пришла, но необходимого количества (которого достаточно для заселения их всех) свободных комнат нет – вся группа разом заселиться не может, потому их забирают родители домой.
Определите, сколько всего групп детей придут и смогут заселиться в номера лагеря за 24 часа (час на планете, на которой находится лагерь длится 75 минут), а также суммарное время, в которое хотя бы одна из комнат была свободна.
Входные данные. В первой строке входного файла находится число А – количество жилых комнат в лагере (натуральное число, не превышающее 1000). Во второй строке находится число В – количество групп детей, которые собираются заселиться в комнаты. В следующих В строках находятся три значения: минута заселения группы детей; минута, до которой группа детей планирует проживать в комнате; количество комнат, которое потребуется для размещения всей группы.
Отсчёт ведётся от начала суток (1800), для каждой группы – в отдельной строке.
Выходные данные. Два целых числа через пробел: сначала количество групп детей, которые смогут заселиться в комнаты за 24 часа, затем суммарное время, в которое хотя бы одна из комнат была свободна.
Решение (Python)
f = open(’26_4__1vv32.txt’)
k = int(f.readline()) # количество жилых комнат
n = int(f.readline()) # количество групп детей
a = sorted(list(map(int, f.readline().split())) for _ in range(n)) # считываем файл и сортируем данные
numbers = [-1]*k # симулируем номера, в каждой ячейке списка будет записано время освобождения данного номера
# словарь, в котором в качества ключа указана минута, а в качестве значения будет указано сколько номеров занято в данную минуту
free_time = {minute: 0 for minute in range(1,1801)}
count = 0
for start, end, quantity in a: # перебор групп детей
# если есть такое количество свободных комнат, которое необходимо текущей группе детей
if len([time for time in numbers if time<start]) >= quantity:
# то начинается процесс заселения детей в комнаты
while quantity>0: # пока текущая группа детей не заняла необходимые ей комнаты
for number in range(k): # перебор комнат
if numbers[number]<start: # если время приезда текущей группы больше времени освобождения этой комнаты группой, которая заняла эту комнату
numbers[number]=end # записываем время освобождения комнаты текущей группой
quantity-=1 # уменьшаем количество необходимых комнат для детей, так как только что в одну комнату дети заселились
for minute in range(start, end+1): # проход по минутам от времени приезда до минуты уезда
free_time[minute]+=1 # отмечаем, что в данные минуты на одну комнату занято будет больше
break
count+=1 # увеличиваем счётчик заселившихся групп детей
# вывод количества заселившихся групп и суммарного времени в течении которого хотя бы одна комната была свободна
print(count, sum(free_time[minute] < k for minute in free_time))