Тема 27. Программирование
27.02 Мусорки, кольцевая дорога
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела программирование
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#88414

На кольцевой автодороге с двусторонним движением находится N бензоколонок (не более одной бензоколонки на каждом километре дороги). Длина кольцевой автодороги равна K км. Нулевой километр и K-й километр находятся в одной точке. Известно количество топлива, которое ежедневно на каждую бензоколонку доставляет отдельный бензовоз. Для перевозки топлива используются бензовозы вместимостью 25 м3  . Стоимость доставки топлива вычисляется как произведение количества рейсов бензовоза на расстояние от нефтехранилища до бензоколонки. Пробег пустого бензовоза не учитывается. Определите минимальные расходы на доставку топлива до всех бензоколонок, если нефтехранилище расположено на кольцевой автодороге на территории одной из бензоколонок.

Входные данные: Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит два числа: N, K (1 ≤ N ≤ 10000 000  , 1 ≤ K ≤ 10000000  ) – соответственно количество бензоколонок на кольцевой автодороге и длина автодороги в километрах. В каждой из следующих N строк находятся два числа: номер километра кольцевой автодороги, на котором расположена бензоколонка, и количество топлива в кубометрах (все числа натуральные, количество топлива на каждой бензоколонке не превышает 1000). Данные указаны в порядке расположения бензоколонок на автодороге.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Вложения к задаче
Показать ответ и решение
# Файлик A
from math import ceil

f = open(’1_27A.txt’)

N, K = map(int, f.readline().split())
b = 25

points = []
for i in f:
    dist, petrol = map(int, i.split())
    # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
    if dist == K:
        dist = 0
    points.append([dist, ceil(petrol / b)])

costs = []
for cur_d, cur_p in points:
    # Перебираем пункты, где можем поставить нефтехранилище
    sm = 0
    for dist, petrol in points:
        # Для пункта увеличиваем сумму
        # Умножаем расстояние от нефтехранилища до пункта на количество рейсов
        sm += petrol * min(abs(cur_d - dist), K - abs(cur_d - dist))
    costs.append(sm)

print(min(costs))

# Файлик B
from math import ceil

f = open(’1_27B.txt’)

N, K = map(int, f.readline().split())
b = 25

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количество рейсов к конкретному пункту
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет влиять на сумму

points = [0] * K
for i in f:
    dist, petrol = map(int, i.split())
                                                                                                  
                                                                                                  
    # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
    petrol = ceil(petrol / b)
    # Выполняем условие, что K-й километр также является и 0-м
    if dist == K:
        dist = 0
    points[dist] = petrol

points = points * 2

# Изначальная сумма для 0-го пункта
sm = 0
for i in range(1, K):
    sm += points[i] * min(i, K - i)

# Все пункты слева будут удаляться, на их сумму будем увеличивать
l = sum(points[-(K // 2):])
# Все пункты справа будут приближаться, их сумму будем вычитать
r = sum(points[:K // 2])

costs = []
# Первый пункт добавляем только в случае, если там может стоять завод
if points[0] > 0:
    costs.append(sm)

for i in range(1, K):
    l += points[i - 1] - points[-(K // 2) + i - 1]
    r += points[(K // 2) + i - 1] - points[i - 1]
    sm += l - r
    # Пункт добавляем только в случае, если в нём может стоять завод
    if points[i] > 0:
        costs.append(sm)

print(min(costs))

Ответ: 138047 18483087239705

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!