Massivi bərpa et#12305

Massivi bərpa et (Həll təhlili)

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

Həll

Biz orijinal massivi əldə etmək üçün prefiks-cəmi prosesini tərsinə çevirə bilərik, bu, fərq massivindən istifadə etməklə edilə bilər, beləliklə yeni tərsinə çevrilmiş proses olacaq:

ilkin elementi $x = a_{1}$ x=a_1 qəbul et.
$a_{1}$ a_1 eyni qalır.
$d_{1}, d_{2}, .., d_{n - 1}$ d_1,d_2,..,d_{n-1} fərq massivini qəbul et.
$i = 2, .., n$ i=2,..,n üzrə keç, sonra $d_{i} \leftarrow a_{i} - a_{i - 1}$ d_i \gets a_i-a_{i-1}
$a \leftarrow [a_{1}, d_{1}, d_{2}, .., d_{n - 1}]$ a \gets [a_1,d_1,d_2,..,d_{n-1}]

Proses dəqiq $k$ dəfə təkrarlanacaq, sonra orijinal massiv $a$ bərpa olunacaq.

Komplekslik $O (nk)$

def solve():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    for _ in range(k):
        d=[]
        for i in range(1,n):
            d.append(a[i]-a[i-1])
        a=[a[0]]+d
    print(*a)

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

Python