Задание №4561.
Обработка целочисленной информации. ЕГЭ по информатике
Файл, необходимый для выполнения задания: ссылка для скачивания.Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные.В первой строке входного файла находится натуральное число
N (N ≤ 1000) – количество заявок на проведение мероприятий.
Следующие
N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Типовой пример организации данных во входном файле.
5
10 150
100 120
131 170
150 180
120 130
При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 20 мин., если состоятся мероприятия по заявкам 2, 4 и 5.Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файла.
Пояснение:
Решим задание, написав программу на языке программирования Python.
Алгоритм действий следующий. Храним данные из файла в списке из картежей, где первый элемент картежа — время начала мероприятия, а второй — время его окончания. Сортируем список по возрастанию по второму элементу картежа — времени окончания мероприятия.
Затем перебираем все элементы списка, считая количество состоявшихся мероприятий и сравнивая время окончания текущего мероприятия со временем начала мероприятия из заявки.
with open('26_222.txt') as data: N = int(data.readline()) data = sorted([(int(i.split()[0]), int(i.split()[1])) for i in data.read().splitlines()], key=lambda x: x[1]) count_events = duration = current_event = 0 for x in range(len(data)): if x == 0: current_event = data[x] count_events += 1 else: if data[x][0] >= current_event[1]: duration = data[x][0] - current_event[1] current_event = data[x] count_events += 1 print(count_events, duration) |
Таким образом,
23 — максимальное количество мероприятий;
16 — самый длинный перерыв между двумя последними мероприятиями (в минутах).
Показать ответ
23 16
Источник: ФИПИ. Открытый банк тестовых заданий
Сообщить об ошибке
Тест с похожими заданиями