Задача к ЕГЭ по информатике на тему «Программирование – оптимизация по времени и по памяти» №1

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

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

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

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

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

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

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

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

$4⋅3 + 10⋅1 = 22$

f = open("3.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]

u = [0] * n

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

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

print(*u)

Ответ: 1400 2300 3200 4100 4400 3500