Reconstruction de Préfixe et Suffixe#12226

Reconstruction de Préfixe et Suffixe (Corrigé)

Auteur du Problème:	Hasan Saleh (MathModel)
Préparé par:	Hasan Saleh (MathModel)
Édité par:	Hasan Saleh (MathModel)

Solution

Construisons le tableau $a$ par la différence de $p$ et $s$ . En général, soit $x$ la construction de $a$ basée sur $p$ et soit $y$ la construction de $a$ basée sur $s$ , soit $x_{1} = a_{1}$ x_1=a_1 et

x_{i} = p_{i + 1} - p_{i}

\displaystyle x_i=p_{i+1}-p_i

pour chaque $(1 \leq i \leq n - 1)$ (1 \le i \le n-1). Il en va de même pour la somme suffixe, $y_{n} = s_{1}$ y_n=s_1 et

y_{n - i} = s_{i} - s_{i - 1}

\displaystyle y_{n-i}=s_i-s_{i-1}

À la fin de notre construction, si $x = y$ x=y, alors il y a un $a$ valide et c'est correct et nous le considérons.

for _ in range(int(input())):
    n=int(input())
    p=list(map(int,input().split()))
    s=list(map(int,input().split()))
    a=[0]*n
    b=[0]*n
    a[0]=p[0]
    b[n-1]=s[0]
    for i in range(1,n):
        a[i]=p[i]-p[i-1]
        b[n-1-i]=s[i]-s[i-1]
    if(a==b):
        print(*a)
    else:
        print(-1)

Python

Complexité $O (n)$ .