26.08 Составление расписания (конференц залы, аэропорты)
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Входной файл содержит сведения о заявках на бронирование учебной аудитории для проведения факультативных занятий. В каждой заявке указаны время начала и окончания занятия (в минутах от начала суток), а также количество учеников, которые собираются посетить занятие. Два занятия можно провести, только если время окончания одного из них строго меньше времени начала другого.
Определите максимальное количество учеников, которые могут посетить факультативные занятия в течение суток, а также общую продолжительность всех проведённых занятий, выбранных для расписания. Если максимальное количество можно получить несколькими способами, то в ответ нужно записать минимальную общую продолжительность проведенных занятий, при которой будет максимальное количество учеников.
Входные данные
В первой строке входного файла записано натуральное число 
(
) — количество заявок
на проведение занятий. Каждая из следующих 
строк содержит три числа: время начала и время
окончания занятия (натуральные числа, не превосходящие 
), а также количество учеников (натуральное
число).
Выходные данные
Два числа через пробел: общая длительность проведённых занятий и максимальное количество учеников, посетивших занятия
Пример входного файла:
Максимальное количество учеников достигается при выборе факультативов 
, 
, 
. Общая продолжительность:
. Ответ: 
.
f = open(’26.txt’) # Открываем файл n = int(f.readline()) # Kоличество заявок # Записываем времена начала, окончания занятий и кол-во учеников a = [list(map(int, i.split())) for i in f] a.sort(key=lambda x:x[1]) # Сортировка по времени окончания занятий price = [i[2] for i in a] # Cписок кол-ва учеников tm = [i[1]-i[0]+1 for i in a] # Список длительностей занятий cnt = [1]*n # Список количества занятий for i in range(1, n): # Перебираем заявки for j in range(i): # Все предыдущие заявки до текущей # Если занятий j заканчивается до начала занятий i if a[j][1] < a[i][0]: # Если сумма кол-ва учеников i-й и j-й заявок больше текущей максимальной if price[j]+a[i][2] > price[i]: # Обновляем максимальное кол-во учеников для i-й заявки price[i] = price[j]+a[i][2] # Обновляем общую длительность занятий tm[i] = tm[j]+a[i][1]-a[i][0] + 1 # Обновляем количество занятий cnt[i] = cnt[j]+1 elif price[j]+a[i][2] == price[i]: if tm[i] > tm[j]+a[i][1]-a[i][0] + 1: tm[i] = tm[j]+a[i][1]-a[i][0] + 1 mx = max(price) # Mаксимальное количество учеников за день for i in range(n): if price[i] == mx: print(tm[i]) # Длительность всех выбранных занятий print(mx)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
