В школьной столовой есть некоторое количество посадочных мест. Места делятся на две категории: для сотрудников школы и для детей. Для сотрудников школы выделено А мест, для детей — В. Сотрудник школы может занять любое место в своей категории, при этом, если все места заняты, он может пересесть на место для детей. Однако ребенок не может сесть на место, предназначенное для сотрудника школы. Место можно занять в следующую минуту после его освобождения. Если человек не находит себе свободного места, он уходит из столовой голодный.
Входные данные.
Первая строка входного файла содержит три целых числа: С – общее количество людей в школе, которые за учебный день придут в столовую, В — количество мест для детей и А — количество мест для сотрудников школы. Каждая из следующих С строк описывает человека и содержит 2 целых числа и букву. Первое число означает время в минутах с начала суток, когда человек пришёл в столовую, второе – необходимую длительность обеда в минутах. Буква означает тип человека: В – ребенок, А – сотрудник школы.
В ответе запишите два целых числа через пробел: сначала количество человек, которые смогут пообедать, затем – общее количество человек, которые уйдут из-за отсутствия мест.
Решение (Python)
file = open(’26_8__1vv37__34yhg.txt’)
count_people, count_child, count_teacher = map(int,file.readline().split()) # Считываем из файла количество людей,детей и учителей
array_people = []
for people in file:#Проходимся по всему файлу
start, duration, category = people.split()
start, duration = int(start), int(duration)
array_people += [(start,duration,category)]#Добавление в список всех значений из файла
array_people.sort()
count = 0
places_A = [0]*count_teacher # посадочные места учителей
places_B = [0]*count_child # посадочные места детей
places = [places_A,places_B]
# проход по людям
for start,duration,category in array_people:
ok = False # Переменная-флаг, которая описывает сел ли текущий человек на место или нет. Изначально мы его еще никуда не посадили
if category == ’B’:# Проверяем, какой категории принадлежит пришедший человек, если это учитель
for i in range(len(places_B)):#Проход по всевозможным местам для детей
if start > places_B[i]:#Если время прихода текущего ребенка больше чем время ухода ребенка,который занимает данное место
places_B[i] = start + duration#То в ячейку записываем время ухода текущего ребенка
count += 1
ok = True
break# Прерываем цикл перебора мест и переходим к следующему человеку
else:
ok = False# Переменная-флаг, которая описывает сел ли текущий человек на место или нет. Изначально мы его еще никуда не посадили
for i in range(len(places_A)):
if start > places_A[i]:#Если время прихода текущего взрослого больше, чем время ухода того взрослого, который занимает текущее место
places_A[i] = start + duration# Тогда записываем время ухода текущего взрослого
count += 1
ok = True# Посадили человека на место. Значение флага делаем True
break# Прерываем цикл перебора мест и переходим к следующему человеку
if not ok:#Если учителя мы не смогли посадить на место для учителей
for i in range(len(places_B)):# Проход по всевозможным местах для детей
if start > places_B[i]:
places_B[i] = start + duration
count += 1
ok = True
break
# Нам нужно вывести количество людей, которые сели за место и количество людей, которые не сели за место
#Количество тех, кто не сел за место можно посчитать так: общее количество людей - количество людей, кто сел за место
print(count,count_people-count)