Задача к ЕГЭ по информатике на тему «Мусорки, кольцевая дорога» №2

Просмотров 5 Комментарии 0

Стоимость доставки фантиков равно произведению количества фантиков на квадрат расстояния от сборщика до мусорки.

Дано число $n$ — количество мусорок, расположенных по кругу, затем $n$ чисел — количество фантиков в каждой мусорке. Требуется найти все возрастающие взвешенные суммы для всех начальных позиций пункта сбора. Возрастающей взвешенной суммой является сумма членов, имеющих вид $a[i]⋅(2⋅i+ 1)$ , где $a[i]$ — i-ое число фантиков, значение i проходит половину круга относительно своей стартовой позиции.

Вывести все эти числа от $1$ до $9 n(1 ≤ n ≤ 10)$ .

Для $n = 4$ и чисел $10$ , $3$ , $5$ , $4$ получатся следующие возрастающие взвешенные суммы:

$10⋅1 + 3⋅3 = 19$ ,

$3⋅1 + 5⋅3 = 18$ ,

$5⋅1 + 4⋅3 = 17$ ,

$4⋅1 + 10⋅3 = 34$

f = open("2.txt")
n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
s = [0] * n
s[0] = sum(a[:n // 2])
for i in range(1, n):
    s[i] = s[i - 1] - a[i - 1] + a[(i + n // 2 - 1) % n]

v = [0] * n

#База. Посчитали первую возрастающую
#взвешенную сумму
for i in range(n // 2):
    v[0] += a[i] * (2*i + 1)

#Пересчитываем все остальные
for i in range(1, n):
    v[i] = v[i - 1] - 2*s[i - 1] + a[i - 1] + a[(i - 1 + n//2) % n] * ((n//2 - 1)*2 + 1)

print(*v)

Ответ: 2200 3100 4000 4900 2800 1900