Ошибка.
Попробуйте повторить позже
Аэропорту необходимо оптимизировать расписание вылетов самолетов. Для этого они получили список всех полетов с указанием времени вылета и времени прилета. Известно, что в небе одновременно может находиться только один самолет, поэтому необходимо составить наиболее оптимальное расписание, чтобы обеспечить максимальное количество вылетов. Если время прибытия одного рейса совпадает со временем вылета другого, то вылет может быть осуществлен без задержек по времени. Расписание составляется таким образом, что в первую очередь совершаются рейсы с минимальным временем прилёта.
Входные данные:
В первой строке входного файла находятся два числа через пробел: число A - общая продолжительность рабочего
дня аэропорта (натуральное число, не превышающее 
) и число B - количество запланированных рейсов
(натуральное число, не превышающее 
). В следующих B строках находится по два числа через пробел. Первое
число - время вылета рейса (натуральное число, не превышающее 
). Второе число - время прилета (натуральное
число, не превышающее 
).
Найдите количество вылетов в расписании, а также суммарное время выполнения рейсов.
В ответе укажите сначала найденное количество, а затем, через пробел, общую длительность рейсов. Если вариантов составить расписание несколько, необходимо выбрать такое, при котором общая длительность рейсов будет минимальна.
Решение при помощи электронных таблиц:
Сначала переносим данные в Excel, удалим первую строчку, а потом при помощи настраиваемой сортировки отсортируем в первую очередь по столбцу B - по возрастанию, а потом по столбцу А - по убыванию (чтобы рейсы длились как можно меньше). Нужно сортировать по времени окончания рейса, так как чем раньше один кончится, тем раньше сможет начаться следующий.
В ячейку C1 запишем значение ячейки B1, в ячейку C2 запишем следующую формулу и растянем её до конца таблицы:
=ЕСЛИ(A2>=C1;B2;C1)
Таким образом у нас в столбце C будет храниться время окончания последнего (на данный момент) рейса. Каждый новое вылет мы проверяем - может ли он начаться после предыдущего последнего, и если да - сохраняем уже новое время окончания, иначе дублируем старое.
В столбце D мы посчитаем количество прошедших рейсов. В ячейку D1 запишем 1, а в ячейку D2 запишем следующую формулу и растянем её до конца таблицы:
=ЕСЛИ(C2<>C1;D1+1;D1)
Если сменилось время окончания - увеличиваем счётчик, иначе дублируем предыдущий.
Прежде чем определять ответ необходимо удалить из таблицы все строчки, в которых в столбце B значение больше времени окончания работы аэропорта - это строчки начиная с номера 5907, так как в ней в столбце B значение 8424, что больше чем 8423 из условия.
Максимальное число в столбце D и будет количеством рейсов - 144.
В столбце E мы посчитаем длительность прошедших рейсов. В ячейку E1 запишем разницу между B1 и A1, а в ячейку E2 запишем следующую формулу и растянем её до конца таблицы:
=ЕСЛИ(C2<>C1;E1+(B2-A2);E1)
Если поменялось время окончания - увеличиваем общую длительность, иначе дублируем предыдущую.
Общая длительность рейсов - 5130.
Решение при помощи программы:
f = open(’7_26_conf.txt’) dur, n = map(int, f.readline().split()) plains = [list(map(int, i.split())) for i in f] # Сортируем по времени окончания, так как # чем раньше один кончится, тем раньше сможет начаться следующий plains.sort(key=lambda x: (x[1], -x[0])) # Уберем все рейсы, кончающиеся после закрытия аэропорта ind = len(plains) for i in range(len(plains)): if plains[i][1] > dur: ind = i break plains = plains[:ind] # Время окончания последнего рейса last_end = plains[0][1] cnt = 1 sm = plains[0][1] - plains[0][0] for start, end in plains: # Может начаться новое - начинаем, не может - добавляем в список возможных if start >= last_end: cnt += 1 last_end = end # Увеличиваем время общей длительности sm += end - start print(cnt, sm)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
