Question

На каждом 3-⁠м километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна 3*N* километров. Нулевой километр и 3*N*-⁠й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров. Из каждого пункта мусор вывозит отдельный мусоровоз. Стоимость доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Центр переработки отходов открыли в одном из пунктов сбора мусора таким образом, чтобы общая стоимость доставки мусора из всех пунктов в этот центр была минимальной.Определите минимальные расходы на доставку мусора в центр переработки отходов.**Входные данные.**27_A.txt27_B.txt

Дано два входных файла (файл *A* и файл *B*), каждый из которых в первой строке содержит число *N* (1 ≤ *N* ≤ 10 000 000) — количество пунктов сбора мусора на кольцевой автодороге. В каждой из следующих *N* строк находится число — количество мусора в контейнере (все числа натуральные, количество мусора в каждом пункте не превышает 1000). Числа указаны в порядке расположения контейнеров на автомагистрали, начиная с первого километра.В ответе укажите два числа: сначала значение искомой величины для файла *А*, затем — для файла *B*.*Типовой пример организации данных во входном файле:*6820513719При таких исходных данных, если контейнеры установлены на каждом километре автодороги, необходимо открыть центр переработки в пункте 6. В этом случае сумма транспортных затрат составит: 1 · 7 + 0 · 19 + 1 · 8 + 2 · 20 + 3 · 5 + 2 · 13.*Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.*

**Предупреждение:** для обработки файла *B* **не следует** использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Ответ:

Accepted Answer

Answer

### СТАТЕМЕНТ

На кольцевой автодороге длиной $3N$ километров на каждом третьем километре установлены контейнеры для мусора. Нулевой и $3N$-й километры совпадают. Известно количество мусора в каждом контейнере. Стоимость доставки вычисляется как произведение количества мусора на расстояние до центра переработки. Центр открывают в одном из пунктов сбора так, чтобы общая стоимость была минимальной.

**Входные данные:** два файла (A и B). Первая строка — число $N$ (1 ≤ $N$ ≤ 10 000 000). Далее $N$ строк с количеством мусора в каждом контейнере (натуральные числа, не превышающие 1000).

**Выходные данные:** два числа — минимальные расходы для файла A и файла B.

**Пример:** при $N = 6$ и мусоре $[8, 20, 5, 13, 7, 19]$ центр в пункте 6 даёт стоимость $1 \cdot 7 + 0 \cdot 19 + 1 \cdot 8 + 2 \cdot 20 + 3 \cdot 5 + 2 \cdot 13$.

### РЕШЕНИЕ

Идея решения: для каждого возможного положения центра переработки вычислить общую стоимость, используя скользящее окно и поддержание сумм элементов слева и справа от центра на кольцевой дороге.

**Шаг 1.** Прочитаем количество пунктов и значения мусора в каждом контейнере.

**Шаг 2.** Умножим каждый элемент на 3, так как контейнеры расположены на каждом третьем километре.

**Шаг 3.** Для первого пункта (индекс 0) как центра переработки вычислим начальную стоимость. Разделим остальные пункты на две группы: слева (индексы $1, 2, \ldots, \lfloor N/2 \rfloor - 1$) и справа (индексы $\lceil N/2 \rceil + 1, \ldots, N-1$). Расстояние от пункта $i$ до центра в пункте 0 равно $\min(i, N - i) \cdot 3$. Суммируем произведения мусора на расстояния. Одновременно накапливаем суммы мусора слева и справа.

**Шаг 4.** Переместим центр в следующий пункт. При сдвиге центра на один пункт вперёд новая стоимость вычисляется через предыдущую, добавляя мусор, который теперь ближе (слева), и вычитая мусор, который теперь дальше (справа). Обновим суммы слева и справа для следующей итерации.

**Шаг 5.** Повторим для всех $N$ пунктов и найдём минимум.

**Сложность:** $O(N)$ — один проход для инициализации, один проход для вычисления всех позиций.

```python
f = open("27_B.txt")
n = int(f.readline())
elems = [0 for i in range(n)]
answers = [0 for i in range(n)]
sum_cost = 0
right_sum = 0
left_sum = 0

for i in range(n):
    elems[i] = int(f.readline())

for i in range(n):
    elems[i] = elems[i] * 3

for i in range(1, n // 2):
    sum_cost = sum_cost + elems[i] * i + elems[n - i] * i
    right_sum = right_sum + elems[i]
    left_sum = left_sum + elems[n - i]

sum_cost = sum_cost + elems[n // 2] * (n // 2)
answers[0] = sum_cost

for i in range(1, n):
    answers[i] = (answers[i - 1] + left_sum + elems[i - 1] - 
                  right_sum - elems[(i + (n // 2) - 1) % n])
    right_sum = right_sum - elems[i] + elems[(i + (n // 2) - 1) % n]
    left_sum = left_sum - elems[(i + (n // 2)) % n] + elems[i - 1]

print(min(answers))
```

### ОТВЕТ

Задание №27ПрограммированиеЕГЭ по информатике