26.08 Составление расписания (конференц залы, аэропорты)
Ошибка.
Попробуйте повторить позже
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале и какова максимальная продолжительность мероприятия, проходившего в середине (если число мероприятий четно, то берется мероприятие, замыкающее первую половину) при условии, что проведено максимальное кол-во мероприятий.
Входные данные. В первой строке входного файла находится натуральное число N — количество заявок на проведение мероприятий (натуральное число, не превыщающее 10000).
Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятия (каждое из чисел натуральное, не превосходящее 1440).
Запишите в ответе два числа через пробел: максимальное количество мероприятий можно провести в конференц-зале и максимальную продолжительность мероприятия, проходившего в середине при условии, что проведено максимальное кол-во мероприятий.
Решение (Excel/LibreOffice)
Переносим данные в Excel, удаляем первую строку файла. Переходим в раздел «Настраиваемая сортировка» и сортируем сначала по столбцу B по возрастанию, а затем – по столбцу А по возрастанию.
В ячейку C1 запишем значение ячейки B1, в ячейку C2 запишем следующую формулу:
=ЕСЛИ(A2>=C1;B2;C1)
и растянем её до конца таблицы.
В ячейку D1 запишем 1, а в ячейку D2 запишем следующую формулу:
=ЕСЛИ(C2<>C1;D1+1;D1)
растянем её до конца таблицы.
Максимальное число в столбце D будет ответом на первый вопрос: количество мероприятий – 97.
Чтобы ответить на второй вопрос найдем строку, где проходит 49 мероприятие (то есть то, что в середине). Время начала 49-го мероприятия: 1040, время его окончания – 1055. Значит, его продолжительность 15.
Решение (Python)
f = open(’26_10__4107m.txt’) n = int(f.readline()) # считываем данные из файла confs = [list(map(int, i.split())) for i in f] # Сортируем по времени окончания, так как # чем раньше один кончится, тем раньше сможет начаться следующий confs.sort(key = lambda x:(x[1],x[0])) # помещаем первое мероприятие в расписание проведенных мероприятий schedule = [confs[0]] for conf in confs: # проход по всем мероприятиям if conf[0] >= schedule[-1][1]: # если начало текущего мероприятия больше или равно окончанию последнего мероприятия, которое мы взяли в расписание schedule.append(conf) # тогда добавляем текущее мероприятие в список print(len(schedule)) # вывод количества проведенных мероприятий # мероприятия, которые могут быть 49-ыми по счёту ost_confs = [i[1]-i[0] for i in confs if i[0] >= schedule[47][1] and i[1] <= schedule[49][0]] # вывод максимальной длительности 49-ого мероприятия print(max(ost_confs))
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
