Задание 26 ЕГЭ информатика: № 26010. Типовые варианты

Входной файл содержит сведения о мероприятиях, в которых приглашён участвовать директор фирмы. Для каждого мероприятия указаны время начала и длительность его проведения (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то руководитель может принять участие только в одном из них. Если время окончания одного мероприятия совпадает со временем начала другого, то руководитель может принять участие в обоих мероприятиях (очно и дистанционно). Определите, в каком максимальном количестве мероприятий может принять участие руководитель, и каков при этом максимально возможный перерыв между двумя последними мероприятиями.

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

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

Типовой пример организации данных во входном файле:
5
20 120
90 20
147 43
150 30
120 20

При таких исходных данных можно провести максимум 3 мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 10 мин., если состоятся мероприятия по заявкам 2, 4 и 5.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

2610.txt 8,8 КБ

data = []
with open('2610.txt') as file:
    N = int(file.readline())

    for line in file:
        parts = line.strip().split()
        end = int(parts[0])+int(parts[1])
        event = {"start": int(parts[0]), "end": end}
        data.append(event)

events = sorted(data, key=lambda event: (event["end"], -event["start"]))

approved_events = [events[0]]

# Определяем подходящие мероприятия начало рассматриваемого
# должно быть позже конца последнего взятого мероприятия
for event in events[1:]:
    if event["start"] >= approved_events[-1]["end"]:
        approved_events.append(event)

# Самый длинный перерыв — разница между началом последнего
# и концом предпоследнего (последнее мероприятие можем сдвинуть дальше)
longest_break = 0
for event in events:
    if event["start"] >= approved_events[-2]["end"]:
        longest_break= max(longest_break,
                           event['start'] - approved_events[-2]["end"])

print(len(approved_events), longest_break)

Рекомендуемые статьи