Приёмщики винограда двух сортов
В период сбора урожая на винограднике работают N сборщиков и K приёмщиков винограда. Каждый сборщик собирает только один сорт винограда: традиционный сорт A или новый сорт B. Каждый приёмщик принимает урожай только одного сорта. Всем приёмщикам присвоены номера начиная с единицы. Приёмщики с нечётными номерами принимают урожай винограда сорта A, чётными – сорта B. Умная камера оценивает количество собранного винограда и определяет время начала и время окончания приёмки партии урожая. Время задаётся в минутах от начала рабочего дня. Приёмщик начинает получение следующей партии винограда от сборщика не ранее, чем через 5 минут после окончания приёмки предыдущей партии. Несколько сборщиков не могут сдавать урожай одному приёмщику в одно и то же время. Автоматизированная система отправляет очередного сборщика к приёмщику данного сорта с минимальным номером. Если в момент прибытия партии урожая свободных приёмщиков нет, то виноград передаётся на рынок для продажи. Определите максимальное суммарное количество партий винограда обоих сортов, полученных приёмщиками, и номер приёмщика, который последним примет партию урожая. Входные данные В первой строке входного файла находятся, разделённые пробелом, натуральные числа K и N, не превышающих 10 000, – количество приёмщиков и сборщиков винограда соответственно. Каждая из следующих N строк содержит два целых числа, разделённых пробелом, – назначенное сборщику время начала и окончания приёмки урожая (в минутах от начала рабочего дня), а также латинскую букву, обозначающую сорт винограда. Типовой пример организации данных во входном файле 2 6 30 60 A 65 1000 A 65 1000 B 1010 1300 B 65 900 A 905 1100 A Пример приведён для двух приёмщиков и шести сборщиков винограда. При таких исходных данных приёмщики получат 5 партий винограда ((30 60 A), (65 900 A), (905 1100 A), (65 1000 B), (1010 1300 B)), одна партия будет отправлена на рынок, последним примет урожай винограда приёмщик с номером 2. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Источник: ФИПИ (Основная 19.06.2026), № 31165
Скачать файл: task_31165_A.txt. В редакторе он уже лежит рядом с кодом, открывай как на экзамене: open('task_31165_A.txt').
Показать разбор
- Прочитай k и заявки, отсортируй по началу, а при равенстве по концу.
- Для каждого приёмщика храни конец его последней партии.
- Для заявки перебирай приёмщиков нужного сорта с шагом 2: сорт A с номера 1, сорт B с номера 2.
- Если начало не раньше, чем через 5 минут после конца прошлой партии, отдай партию и останови перебор.
- Выведи число принятых партий и номер последнего приёмщика.
data = []
f = open('task_31165_A.txt')
k, n = map(int, f.readline().split())
for line in f:
a, b, c = line.split()
data.append((int(a), int(b), c))
data.sort()
w = [-10] * (k + 1)
count = 0
last = 0
for s, e, c in data:
first = 1 if c == 'A' else 2
for i in range(first, k + 1, 2):
if s >= w[i] + 5:
w[i] = e
count += 1
last = i
break
print(count, last)