В городе планируется музыкальный фестиваль, на который открыт предзаказ билетов. Каждая заявка на предзаказ содержит только одно целое число — количество билетов, которые человек хочет купить.
Перед началом фестиваля кассир распределяет заявки следующим образом: в первую очередь рассматриваются заявки, содержащие наибольшее количество билетов для покупки. Все билеты из одной заявки должны находится в одном ряду. А также, в первую очередь заполняется ряд с наименьшим номером.
Определите, какое количество заявок подтвердит кассир и сколько свободных мест останется после распределения всех заявок.
Входные данные. В первой строке находится три числа: A — количество рядов, B — количество мест в ряду и C — количество заявок. В каждом из С следующих строк находится одно число — количество билетов в заявке.
Выходные данные. Два числа через пробел — сначала количество подтвержденных заявок, затем количество оставшихся мест.
Решение (Python)
with open(’26_2__1vv2z.txt’) as f:
# k - количество рядов
# m - количество мест в ряду
# n - количество заявок
k, m, n = map(int, f.readline().split())
# Список заявок
s = [int(f.readline())for _ in range(n)]
# Сортируем список так, чтобы в начале стояли наибольшие числа
s.sort(reverse=True)
# Список для обозначения свободных мест
free = [m]*k
# Количество подтверждённых заявок
cnt = 0
# Проходимся по заявкам
for x in s:
# Проходимся по каждому ряду
for i in range(k):
# Если в ряду достаточно свободных мест для заявки — засчитываем
if free[i] >= x:
# Отнимаем кол-во занимаемых мест от кол-ва свободных мест в этом ряду
free[i] -= x
cnt += 1
break # сбрасываем цикл - переходим к следующей заявке
print(cnt, sum(free))