26.06 Распределение объектов по местам (хранение багажа, парковки, кафе, гостиницы)
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Освобождение ячейки происходит в течение 1 мин, освобождение начинается в минуту ухода клиента. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит.
Входные данные представлены в файле следующим образом.
В первой строке входного файла находится натуральное число 
, не превышающее 1000, – количество ячеек в
камере хранения. Во второй строке – натуральное число 
(
1000), обозначающее количество пассажиров.
Каждая из следующих 
строк содержит два натуральных числа, каждое из которых не превышает 1440:
указанное в заявке время размещения багажа в ячейке и время освобождения ячейки (в минутах от начала
суток).
Требуется выбрать для каждой ячейки один багаж, который удалось оставить в данной ячейке так, чтобы сумма времени хранения всех выбранных багажей была минимальная и четная.
В ответе запишите одно число: найденную сумму.
Пример входного файла:
2
5
30 60
40 1000
59 60
61 1000
1010 1440
f = open(’26-1.txt’) k = int(f.readline()) # Kоличество ячеек n = int(f.readline()) # Kоличество пассажиров # Сортировка пассажиров по времени сдачи багажа a = sorted([list(map(int, i.split())) for i in f]) cell = [[] for i in range(k)] # Cписок ячеек for i in a: # Для каждой заявки пассажира for j in range(k): # Ищем свободную ячейку # Если ячейка пустая или успеет освободиться if (not cell[j]) or (i[0] > cell[j][-1][1]): cell[j].append(i) # Добавляем заявку в ячейку break # Останавливаем поиск # Вычисляем длительность каждого хранения багажа в ячейках t = [[j[1]-j[0] for j in i] for i in cell] s = 0 # Сумма всех длительностей mr = 1000050000 # Минимальная разница for i in t: # Проходим по каждой ячейке line = sorted(i) # Сортировка длительностей по возрастанию s += line[0] # Добавление минимальной длительности к общей сумме if len(line) > 1: # Если в ячейке больше одной длительности for j in range(1, len(line)): # Ищем минимальную нечетную разницу if (abs(line[0]-line[j]) < mr) and (abs(line[0]-line[j]) % 2 !=0): mr = abs(line[0]-line[j]) # Обновляем минимальную нечетную разницу if s % 2 != 0: s = s + mr print(s)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
