Sıçrayan Top#12311

Sıçrayan Top (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

$a_{1}$ a_1-dan başqa bütün məsafələrin iki dəfə qət ediləcəyini müşahidə edin, yəni proses aşağıdakı kimi olacaq:

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

Beləliklə, simulyasiya aşağıdakı kimi olur:

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

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

Mürəkkəblik $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