Bouncing Ball#12311

Bouncing Ball (Editorial)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

Observe all distances except $a_{1}$ a_1 will be travelled twice , i.e. the process will be as following :

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 ...

So the simulation ends up being :

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

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

Complexity $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