Задача #2171

Сортировка

Сложнее ЕГЭ

(П. Говоров) Диджей "Dr4g0n" решил подготовить расписание песен для школьной дискотеки. Он записывал в какой момент песня должна была заиграть(в секунду от момента начала диск.), длительность песни, а также помечал некоторые песни, как "любимые". Однако, он заметил, что допустил ошибку в расчетах и временные рамки песен могут "накладываться" друг на друга. Необходимо определить наибольшее количество песен, которые будут играть на дискотеке, учитывая, что "любимые" песни должны быть обязательно включены в программу и никакие песни не должны "накладываться" друг на друга(песня может начать играть в ту же секунду, в которую окончилась предыдущая), а также наибольшее время конца последней возможной "нелюбимой" песни.

Входные данные представлены в файле следующим образом. Первая строка входного файла содержит количество песен N (N ≤ 10000). Каждая из следующих N строк содержит три целых числа, записанные через пробел: время начала (T1) и длительность этой песни (T2) (в секундах 0 < T1 ≤ T2 < 300 000 ), а также 1, если песня "любимая" и 0, если "нелюбимая" соответственно.

Запишите в ответе два числа: наибольшее количество песен, которые будут играть на дискотеке, учитывая, что "любимые" песни должны быть обязательно включены в программу, а также наибольшее возможное время конца последней "нелюбимой" песни.

Пример входного файла:

6
1 2 0
4 2 0
6 1 1
4 1 0
3 1 0
2 1 1

В данном случае наибольшее число песен (4), их временные рамки: (2,3); (3,4); (4,5) или также подходит (4,6); (6,7) , а "нелюбимая" возможная песня, которая играла последней началась в 4, длилась 2, закончилась в 6. Ответ: 4 6

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

Скачать 26.txt

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

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

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

Ответ

109

101163

f = open('26.txt')

n = int(f.readline())

fav_music = [] #массив любимых песен

oth_music = [] #массив остальных песен

for i in range(n): #ввод данных

st, dlit, rate = map(int, f.readline().split())

if rate==1: fav_music.append((st,st+dlit))

else: oth_music.append((st,st+dlit))

oth_music = sorted(oth_music, key=lambda x:x[1]) #сортировка по концу песни

fav_music = sorted(fav_music)

def check_cross(st,end): #проверка на пересечение с любимыми песнями

global fav_music

for st1,end1 in fav_music:

if st1 >= end: return True

if st < end1 and end > st1: return False

return True

used_otr=[]

for st_o, end_o in oth_music: #посчет используемых песен

if len(used_otr)>0:

if st_o >= used_otr[-1][1] and check_cross(st_o, end_o):

used_otr.append((st_o, end_o))

elif check_cross(st_o, end_o):

used_otr.append((st_o, end_o))

print(len(used_otr)+len(fav_music))

#массив возможных последних игравших песен

last_probably_otr_arr = [i for i in oth_music if check_cross(i[0],i[1]) and i[0]>=used_otr[-2][1]]

print(last_probably_otr_arr[-1][1])

Номер