Задание 26. Информатика. ЕГЭ. Шастин. 30.11.2024
- Просмотры: 429
- Изменено: 1 февраля 2025
(Д. Бахтиев, Л. Шастин) На железнодорожной станции ведётся учёт прибывающих и отправляющихся поездов (в минутах, прошедших с начала суток). Станция работает круглосуточно и без перерывов, а администрация станции фиксирует время прибытия и отправления станции каждого поезда. Поезд считается находящимся на станции с момента его прибытия до момента отправления, т.е. если поезд прибыл в минуту \(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.\)
Решение:
Python
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))
Ответ: \(11 \,\, 27785627\)