На кольцевой автодороге с двусторонним движением находится N бензоколонок (не более одной бензоколонки на каждом километре дороги). Длина кольцевой автодороги равна K км. Нулевой километр и K-й километр находятся в одной точке. Известно количество топлива, которое ежедневно на каждую бензоколонку доставляет отдельный бензовоз. Для перевозки топлива используются бензовозы вместимостью 25 м
. Стоимость доставки топлива вычисляется как произведение количества рейсов бензовоза на расстояние от нефтехранилища до бензоколонки. Пробег пустого бензовоза не учитывается. Определите минимальные расходы на доставку топлива до всех бензоколонок, если нефтехранилище расположено на кольцевой автодороге на территории одной из бензоколонок.
Входные данные: Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит два числа: N, K (
, 
) – соответственно количество бензоколонок на кольцевой автодороге и длина автодороги в километрах. В каждой из следующих N строк находятся два числа: номер километра кольцевой автодороги, на котором расположена бензоколонка, и количество топлива в кубометрах (все числа натуральные, количество топлива на каждой бензоколонке не превышает 1000). Данные указаны в порядке расположения бензоколонок на автодороге.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.
Решение для файла А
from math import ceil
f = open(’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(’27B.txt’) # Открываем файл
n, k = map(int, f.readline().split()) # Считываем количество бензоколонок и длину автодороги
b = 25 # Задаём вместимость
# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количество рейсов к конкретному пункту
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет влиять на сумму
a = [0] * k
for i in f:
km, petrol = map(int, i.split()) # Считываем номер километра и количество топлива
km %= k
# Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
a[km] = ceil(petrol / b)
# Инициализируем начальную стоимость доставки мусора,
# если завод расположен в пункте №1
s = a[k // 2] * (k // 2) # Прибавляем к сумме средний элемент
for i in range(1, k // 2):
# Добавляем стоимость доставки для пунктов слева и справа
s += a[i] * i + a[-i] * i
# Рассчитываем разницу в стоимости доставки мусора
# при перемещении завода на следующий пункт
d = sum(a) - sum(a[1:(k // 2) + 1]) * 2
# Задаём минимальную стоимость
if a[0] != 0:
mn = s
else:
mn = 10 ** 20
for i in range(1, k + 1): # Для каждого пункта проверяем стоимость доставки
s += d # Обновляем текущую стоимость доставки
if s < mn and a[i] != 0: # Если текущая стоимость больше максимальной
mn = s # Запоминаем сумму
# Рассчитываем смещение разницы стоимости доставки
# при перемещении завода к следующему пункту
r = a[i % k] * 2 - a[(i + k // 2) % k] * 2
d += r # Обновляем разницу в стоимости доставки
print(mn) # Выводим минимальную стоимость