Ошибка.
Попробуйте повторить позже
На кольцевой автодороге с двусторонним движением находится N бензоколонок (не более одной бензоколонки на каждом километре дороги). Длина кольцевой автодороги равна K км. Нулевой километр и K-й километр находятся в одной точке. Известно количество топлива, которое ежедневно на каждую бензоколонку доставляет отдельный бензовоз. Для перевозки топлива используются бензовозы вместимостью 180 м. Стоимость доставки топлива вычисляется как произведение количества рейсов бензовоза на расстояние от нефтехранилища до бензоколонки. Пробег пустого бензовоза не учитывается. Определите минимальные возможные расходы на доставку топлива до всех бензоколонок, если нефтехранилище расположено на кольцевой автодороге на территории одной из бензоколонок c количеством топлива меньше 300.
Входные данные: Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит два числа: N, K (, ) – соответственно количество бензоколонок на кольцевой автодороге и длина автодороги в километрах. В каждой из следующих N строк находятся два числа: номер километра кольцевой автодороги, на котором расположена бензоколонка, и количество топлива в кубометрах (все числа натуральные, количество топлива на каждой бензоколонке не превышает 1000). Данные указаны в порядке расположения бензоколонок на автодороге.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.
# Файлик A from math import ceil f = open(’5_27A.txt’) N, K = map(int, f.readline().split()) b = 180 m = 300 points = [] for i in f: dist, petrol = map(int, i.split()) # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil if dist == K: dist = 0 points.append([dist, petrol]) costs = [] for cur_d, cur_p in points: # Перебираем пункты, где можем поставить нефтехранилище sm = 0 for dist, petrol in points: # Для пункта увеличиваем сумму # Умножаем расстояние от нефтехранилища до пункта на количество рейсов sm += ceil(petrol / b) * min(abs(cur_d - dist), K - abs(cur_d - dist)) if 0 < cur_p < m: costs.append(sm) print(min(costs)) # Файлик B from math import ceil f = open(’5_27B.txt’) N, K = map(int, f.readline().split()) b = 180 m = 300 # Список, в котором индекс - расстояние от нулевой отметки до этого пункта # элементы - количество рейсов к конкретному пункту # Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет влиять на сумму points = [0] * K for i in f: dist, petrol = map(int, i.split()) # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil # Выполняем условие, что K-й километр также является и 0-м if dist == K: dist = 0 points[dist] = petrol points = points * 2 # Изначальная сумма для 0-го пункта sm = 0 for i in range(1, K): sm += ceil(points[i] / b) * min(i, K - i) # Все пункты слева будут удаляться, на их сумму будем увеличивать l = sum([ceil(i / b) for i in points[-(K // 2):]]) # Все пункты справа будут приближаться, их сумму будем вычитать r = sum([ceil(i / b) for i in points[:K // 2]]) costs = [] # Первый пункт добавляем только в случае, если там может стоять завод if 0 < points[0] < m: costs.append(sm) for i in range(1, K): l += ceil(points[i - 1] / b) - ceil(points[-(K // 2) + i - 1] / b) r += ceil(points[(K // 2) + i - 1] / b) - ceil(points[i - 1] / b) sm += l - r # Пункт добавляем только в случае, если в нём может стоять завод if 0 < points[i] < m: costs.append(sm) print(min(costs))
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!