Кулька, що відскакує#12311

Кулька, що відскакує (Розбір)

Автор задачі:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Рішення

Зверніть увагу, що всі відстані, крім $a_{1}$ a_1, будуть пройдені двічі, тобто процес виглядатиме так:

0 + a_{1} a_{1} - a_{1} 0 + a_{2} a_{2} - a_{2} 0 \to ...

0\xrightarrow{+a_1} a_1 \xrightarrow{-a_1} 0 \xrightarrow{+a_2}a_2 \xrightarrow{-a_2} 0 \rightarrow ...

Отже, симуляція закінчується:

a_{1} + 2 i = 2 \sum n a_{i}

a_1 + 2\sum_{i=2}^n a_i

Складність $O (n)$ .

def solve():
   n=int(input())
   a=list(map(int,input().split()))
   ans=a[0]
   for i in range(1,n):ans+=2*a[i]
   print(ans)

for _ in range(int(input())):
    solve()

Python