В городе M расположена кольцевая автодорога длиной N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод таким образом, чтобы максимизировать стоимость доставки мусора.
Стоимость доставки мусора вычисляется как произведение вместимости пункта сбора и минимального расстояния от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым.
Нумерация контейнеров происходит от 1 до N. Требуется определить, рядом с каким пунктом сбора мусора нужно поставить мусороперерабатывающий завод.
Входные данные:
Первое число N — количество контейнеров для мусора. Последующие N чисел — количество килограмм мусора, которое производится на точке.
Выходных данные:
Одно число – номер контейнера для мусора рядом с которым стоит расположить перерабатывающий завод.
В ответе укажите два числа через пробел: сначала искомое значение для файла А, затем для файла B.
f = open(’27_5B__3hjkh.txt’) # Открываем файл
n = int(f.readline()) # Считываем количество контейнеров
# Список с вместимостью каждого пункта
a = [int(i) 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 # Задаём максимальную стоимость
p = 0 # Задаём пункт для ответа
# Для каждого следующего пункта находим стоимость доставки
for i in range(1, n):
# Обновляем текущую стоимость доставки
s += d
if s > mx:
mx = s # Запоминаем сумму
p = i + 1 # Запоминаем номер пункта
# Рассчитываем смещение разницы стоимости доставки
# при перемещении завода к следующему пункту
r = a[i % n] * 2 - a[(i + n // 2) % n] * 2
# Обновляем разницу в стоимости доставки
d += r
print(p) # Выводим максимальную стоимость