Задание 26. Информатика. ЕГЭ. Шастин. 30.11.2024

(Д. Бахтиев, Л. Шастин) На железнодорожной станции ведётся учёт прибывающих и отправляющихся поездов (в минутах, прошедших с начала суток). Станция работает круглосуточно и без перерывов, а администрация станции фиксирует время прибытия и отправления станции каждого поезда. Поезд считается находящимся на станции с момента его прибытия до момента отправления, т.е. если поезд прибыл в минуту \(t\), то всю эту минуту он уже находился на платформе; если поезд уехал в минуту \(t\), то в эту минуту на платформе его уже нет.

Инженер станции анализирует данные, чтобы определить пики загруженности — это промежутки времени, когда на платформе находилось наибольшее количество поездов. Такие периоды могут повторяться в течение суток.

Входной файл содержит информацию о времени прибытия и отправления каждого поезда и номера поездов. Найдите количество пиков загруженности за первые \(24\) часа от начала суток, а также определите сумму номеров всех поездов, которые находились на платформе хотя бы одну минуту в период самого длинного пика. Гарантируется, что самый длинный пик представлен в единственном экземпляре.

Входные данные

В первой строке входного файла находится натуральное число \(N\) (\(N < 10~000\)) — количество поездов, прибывших на станцию в течение суток. Следующие \(N\) строк содержат три числа: первое обозначает номер поезда (натуральное число, не превышающее \(100~000\)), второе и третье — время прибытия и время отправления (оба натуральные числа, не превышающие \(1440\)) каждого поезда в минутах от начала суток.

Выходные данные

В ответе укажите сначала количество пиков, а затем сумму номеров поездов, находившихся на платформе во время самого длинного пика.

Пример входных данных
\(5\)
\(12 \,\, 140 \,\, 250\)
\(44 \,\, 200 \,\, 278\)
\(13 \,\, 0 \,\, 41\)
\(84 \,\, 250 \,\, 310\)
\(11 \,\, 13 \,\, 190\)

Для таких входных данных пиковое количество поездов равно \(2\), а количество таких пиков — \(3\) (с \(3\) до \(41\) минуты, с \(140\) до \(190\) и с \(200\) до \(278\)). Самый длинный пик — третий, сумма номеров поездов для него равна \(12 + 44 + 84 = 140.\) Ответ: \(3 \,\, 140.\)

base = ''
fd = open(base + '26.txt')

day = {k: 0 for k in range(1441)} #количество поездов на станции в каждую минуту
trains = {k: [] for k in range(1441)} #номера поездов, находящихся на станции в k-ю минуту
N = int(fd.readline())
for line in fd:
    train, arrive, leave = map(int, line.split())
    for k in range(arrive, leave):
        day[k] += 1
        trains[k].append(train)
        
train_peaks = max(day.values()) # максимальное число поездов на станции 

p = 0  #находим пики двойными указателями
peaks = []
while day[p] < train_peaks:
    p += 1
p1 = p
while p < 1441 or p1 < 1441:
    while p1 < 1441 and day[p1] == train_peaks:
        p1 += 1
    peaks.append((p, p1))
    p = p1
    while p < 1441 and day[p] < train_peaks:
        p += 1
    p1 = p
    
peaks = [(x[1] - x[0], x) for x in peaks] #len(peaks) будет кол-во пиков
max_peak = max(peaks)[1] #самый длинный из пиков

st = set() #забросим в это множество номера поездов, которые были на станции в максимальный пик
           #одни могли уехать, другие приехать
for k in range(max_peak[0], max_peak[1]):
    st = st.union(set(trains[k]))
    
print(len(peaks), sum(st))