В городе M расположена кольцевая автодорога длиной N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод таким образом, чтобы общая стоимость доставки мусора была минимальной.
Стоимость доставки мусора вычисляется как произведение вместимости пункта сбора и расстояния от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым.
Требуется определить, какая будет минимальная общая стоимость доставки мусора.
Входные данные:
Первое число N — количество контейнеров для мусора. Последующие N чисел — количество килограмм мусора, которое производится на точке.
Выходных данные:
Одно число – минимальная общая стоимость доставки мусора со всех точек.
В ответе укажите два числа через пробел: сначала искомое значение для файла А, затем для файла B.
# Файлик А
f = open(’27A_07_1.txt’)
N = int(f.readline())
a = [int(i) for i in f] * 2
mn = 10 ** 10
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(sm, mn)
print(mn)
# Файлик B
f = open(’27B_07_1.txt’)
N = int(f.readline())
a = [int(i) for i in f] * 2
sm = 0
for i in range(1, N):
sm += a[i] * min(i, N - i)
l = sum(a[-(N // 2):])
r = sum(a[:N // 2])
sums = [sm]
for i in range(1, N):
l += a[i - 1] - a[-(N // 2) + i - 1]
r += a[(N // 2) + i - 1] - a[i - 1]
sm += l - r
sums.append(sm)
print(min(sums))