Задание EGEINFBED6E1: Эффективная обработка данных и кластеры

Решение.
Соседние контейнеры расположены через 3 км. Груз из каждого контейнера доставляется к выбранному центру по кратчайшему из двух направлений кольца. Обозначим количества мусора через a₀, a₁, …, aₙ₋₁, а центр — индексом k, считая индексы с нуля.
Сначала считаем расстояния в промежутках между соседними контейнерами. Для контейнера i это min(|i − k|, N − |i − k|). Стоимость Cₖ в таких единицах равна сумме произведений aᵢ на эти расстояния. Полученный минимум умножим на 3, чтобы учесть километры.
Прямой пересчёт суммы для каждого центра занял бы O(N²) времени. Вместо этого вычислим C₀ одним проходом, а затем будем переносить центр на соседний контейнер, обновляя сумму за постоянное время.
Пусть S — общее количество мусора, m — целая часть половины N. Обозначим через Fₖ сумму мусора в следующих m контейнерах по направлению движения от центра k. Все индексы при выходе за N − 1 циклически возвращаются к началу.
При чётном N расстояния до этих m контейнеров уменьшаются на один промежуток, а до остальных увеличиваются на один. Поэтому новая стоимость получается из старой так:
Cₖ₊₁ = Cₖ + (S − Fₖ) − Fₖ = Cₖ + S − 2Fₖ.
При нечётном N контейнер с индексом k + m + 1 находится на одинаковом расстоянии m от старого и нового центров. Его вклад не меняется. Его массу aₖ₊ₘ₊₁ нужно исключить из группы, расстояния до которой увеличиваются:
Cₖ₊₁ = Cₖ + S − 2Fₖ − aₖ₊ₘ₊₁.
Сама сумма F обновляется удалением ближайшего контейнера и добавлением следующего дальнего:
Fₖ₊₁ = Fₖ − aₖ₊₁ + aₖ₊ₘ₊₁.
Таким образом, после начального прохода посещаем все N возможных центров и выбираем минимальную стоимость. Формулы учитывают и чётное, и нечётное количество контейнеров; при N = 1 перевозка не нужна и стоимость равна нулю.
Скачиваемый ZIP объединяет два исходных файла A и B официального варианта ФИПИ. Содержимое этих TXT сохранено без изменений.
Программа на Python 3. Оба файла из архива сохраняем под указанными в программе именами:

def minimum_cost(filename):
    with open(filename, encoding='utf-8-sig') as source:
        n, *weights = map(int, source.read().split())
    assert len(weights) == n
    half, odd = divmod(n, 2)
    total = sum(weights)
    cost = sum(weight * min(index, n - index)
               for index, weight in enumerate(weights))
    forward = sum(weights[1:half + 1])
    best = cost
    for center in range(n - 1):
        opposite = weights[(center + half + 1) % n]
        cost += total - 2 * forward
        if odd:
            cost -= opposite
        forward += opposite - weights[(center + 1) % n]
        best = min(best, cost)
    return 3 * best
print(minimum_cost('107_27_A.txt'),
      minimum_cost('107_27_B.txt'))

Результаты для исходных данных:

Проверка выполнена прямым суммированием расстояний от каждого контейнера до найденного центра: получаются те же значения. Независимый способ через накопленные суммы масс и произведений масс на индексы подтвердил стоимость для каждого возможного центра, а не только итоговый минимум.
Числа в иллюстративном примере условия расположены через 1 км; при работе с основными файлами используем именно 3 км. Это объясняет множитель 3 в последней строке функции.
Время работы O(N), память O(N). Python хранит целые числа точно; все вычисления здесь выполняются без округления.
Ответ: 471228 49113954961677.