Задача #4265

Сортировка

Уровень ЕГЭ

В период сбора урожая на винограднике работают N сборщиков и К приёмщиков винограда. Каждый сборщик собирает только один сорт винограда: традиционный сорт А или новый сорт В. Каждый приёмщик принимает урожай только одного сорта. Всем приёмщикам присвоены номера начиная с единицы. Приёмщики нечётными номерами принимают урожай винограда сорта А, чётными - сорта В.
Умная камера оценивает количество собранного винограда и определяет время начала и время окончания приёмки партии урожая. Время задаётся в минутах от начала рабочего дня. Приёмщик начинает получение следующей партии винограда от сборщика не ранее, чем через 5 минут после окончания приёмки предыдущей партии. Несколько сборщиков не могут сдавать урожай одному приёмщику в одно и то же время. Автоматизированная система отправляет очередного сборщика к приёмщику данного сорта с минимальным номером. Если в момент прибытия партии урожая свободных приёмщиков нет, то виноград передаётся на рынок для продажи.
Определите максимальное суммарное количество партий винограда обоих сортов, полученных приёмщиками, и номер приёмщика, который последним примет партию урожая.
Входные данные
В первой строке входного файла находятся, разделённые пробелом, натуральных числа К и N, не превышающих 10 000, - количество приёмщиков и сборщиков винограда соответственно. Каждая из следующих N строк содержит два целых числа, разделённых пробелом, - назначенное сборщику время начала и окончания приёмки урожая (в минутах от начала рабочего дня), а также латинскую букву, обозначающую сорт винограда.
Типовой пример организации данных во входном файле
2 6
30 60 A
65 1000 A
65 1000 В
1010 1300 B
65 900 A
905 1100 A
Пример приведён для двух приёмщиков и шести сборщиков винограда. При таких исходных данных приёмщики получат 5 партий винограда ((30 60 A), (65 900 A), (905 1100 A), (65 1000 В), (1010 1300 В)), одна партия будет отправлена на рынок, последним примет урожай винограда приёмщик с номером 2.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файлы к задаче

Скачать 26.txt

Новая

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть Нажми, чтобы скрыть

Ответ

9338

Видео по задаче

Смотреть в VK

f = open('26_2.txt')

K, N = [int(x) for x in f.readline().split()]

a = []

for s in f:
    st, end, t = s.split()
    a.append([int(st), int(end), t])

a.sort()

sbor = [0]*(K+1)

ans = []

for st, end, t in a:
    if t=='A':
        for i in range(1,K+1,2):
            if st>=sbor[i]:
                ans.append(i)
                sbor[i] = end+5
                break
    else:
        for i in range(2,K+1,2):
            if st>=sbor[i]:
                ans.append(i)
                sbor[i] = end+5
                break
print(len(ans), ans[-1])

Номер