26.09 Прочие прототипы
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Входной файл содержит информацию о заказах на использование фотостудии в течение суток. Каждый заказ включает время начала и окончания съёмки (в минутах от начала суток), а также сумму, которую клиент готов заплатить за аренду студии. Съемки можно проводить только со следующей минуты после окончания предыдущей.
Определите максимальный доход, который можно получить за аренду студии, а также общую продолжительность съёмок, которые будут проведены в этом случае. Если максимальный доход можно получить несколькими способами, то в ответ нужно записать минимальную общую продолжительность съёмок, при которой будет получен максимальный доход.
Входные данные
В первой строке файла записано натуральное число 
(
) — количество заказов. Каждая из
следующих N строк содержит по три числа: время начала, время окончания съёмки (натуральные числа, не
превышающие 
), и сумму оплаты.
Выходные данные
Два числа через пробел: максимальный доход и суммарная продолжительность выбранных съёмок.
Пример входного файла:
Максимальный доход достигается при выборе заказов 
, 
, 
. Общая продолжительность:
. Ответ: 
.
f = open(’26_1.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[i] == price[j]+a[i][2] and 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аксимальная сумма оплаты за день print(mx) for i in range(n): if price[i] == mx: print(tm[i]) # Длительность всех выбранных съемок
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
