В городе M расположена кольцевая автодорога длиной N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод.
Мусор до завода доставляет автомобиль, но в него вмещается не более K килограмм мусора за раз.
Стоимость доставки мусора вычисляется как произведение количества необходимых заездов автомобиля до точки и расстояния от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым.
Требуется определить разницу между максимальной и минимальной возможными общими стоимостями доставки мусора со всех точек.
Входные данные:
Первое число N — количество контейнеров для мусора. Второе число K — вместимость автомобиля. Последующие N чисел — количество килограмм мусора, которое производится на точке.
В ответе укажите два числа через пробел: сначала искомое значение для файла А, затем для файла B.
Решение для файла A
from math import ceil
f = open(’27A_07_4.txt’)
N = int(f.readline())
K = int(f.readline())
a = [ceil(int(i) / K) for i in f] * 2
mn = 10 ** 10
mx = -1
ind = -1
for i in range(0, N):
sm = 0
for j in range(1 + i, N + i):
d = abs(j - i)
sm += a[j] * min(d, N - d)
mn = min(mn, sm)
mx = max(mx, sm)
print(mx - mn)
Решение для файла B
f = open(’27B_07_4.txt’) # Открываем файл
n = int(f.readline()) # Считываем количество контейнеров
k = int(f.readline()) # Считываем вместимость автомобиля
# Список с вместимостью каждого пункта
a = [(int(i) // k) + (int(i) % k != 0) for i in f]
# Инициализируем начальную стоимость доставки мусора,
# если завод расположен в пункте по индексу 0
s = a[n // 2] * (n // 2) # Прибавляем к сумме средний элемент
for i in range(1, n // 2):
# Добавляем стоимость доставки для пунктов слева и справа
s += a[i] * i + a[-i] * i
# Рассчитываем разницу в стоимости доставки мусора
# при перемещении завода на следующий пункт
d = sum(a) - sum(a[1:(n // 2) + 1]) * 2
# Так как пункт по индексу 0 посчитали отдельно, возьмем стоимость для него как начальную
mx = s # Задаём максимальную стоимость
mn = s # Задаём минимальную стоимость
# Для каждого следующего пункта находим стоимость доставки
for i in range(1, n):
# Обновляем текущую стоимость доставки
s += d
# Пробуем обновить макс. и мин. стоимости
mx = max(mx, s)
mn = min(mn, s)
# Рассчитываем смещение разницы стоимости доставки
# при перемещении завода к следующему пункту
r = a[i % n] * 2 - a[(i + n // 2) % n] * 2
# Обновляем разницу в стоимости доставки
d += r
print(mx - mn) # Выводим разницу макс. и мин. стоимостей