0071 - Reducere

Sursa: 0071 - Reducere

---

Cerinţa

Se consideră două tablouri unidimensionale A și B cu elemente numere naturale din intervalul [1,10000]. Spunem că tabloul A se poate reduce la tabloul B dacă există o împărțire a tabloului A în secvențe disjuncte de elemente aflate pe poziţii consecutive în tabloul A astfel încât prin înlocuirea secvențelor cu suma elementelor din secvență să se obţină, în ordine, elementele tabloului B. Se dau două tablouri A și B. Să se verifice dacă tabloul A se poate reduce la tabloul B.

Programul va citi mai multe seturi de date, fiecare constând în doi vectori A, B și va afișa pentru fiecare set de date dacă tabloul A se poate reduce la tabloul B.

Date de intrare

Programul citește un număr natural T, reprezentând numărul de seturi de date de test care urmează. Urmează T seturi de date, descrise astfel:

• se citește n
• se citesc n valori, reprezentând elementele tabloului A
• se citește m
• se citesc m valori, reprezentând elementele tabloului B

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează pentru fiecare dintre cele T teste, pe câte o linie a ecranului valoare 1, dacă tabloul A se poate reduce la tabloul B, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 0 < n, m < 1001
• elementele vectorilor A, B sunt numere naturale din intervalul [1,10000]

0 < T ≤ 10

Exemplu 1

Intrare

2

12

7 3 4 1 6 4 6 9 7 1 8 7

4

14 7 26 16

5

1 4 2 2 3

3

5 3 4

Ieșire

Datele sunt introduse corect.

1

0

Exemplu 2

Intrare

2

1001

7 3 4 1 6 4 6 9 7 1 8 7

4

14 7 26 16

5

1 4 2 2 3

3

5 3 4

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0071 - Reducere

def se_poate_reduca_la_B(A, B):

   i = j = 0
   n = len(A)
   m = len(B)
   while i < n and j < m:
       if A[i] == B[j]:
           i += 1
           j += 1
       else:
           s = A[i]
           i += 1
           while i < n and s < B[j]:
               s += A[i]
               i += 1
           if s != B[j]:
               return 0
           j += 1
   return j == m

def validare(n, A, m, B):

   if not(1 <= n <= 1000) or not(1 <= m <= 1000):
       return False
   if not all(1 <= a <= 10000 for a in A) or not all(1 <= b <= 10000 for b in B):
       return False
   return True

if __name__ == "__main__":

   T = int(input())
   if T <= 0 or T > 10:
       print("Datele nu corespund restricțiilor impuse.")
   else:
       print("Datele sunt introduse corect.")
       for i in range(T):
           n = int(input())
           A = list(map(int, input().split()))
           m = int(input())
           B = list(map(int, input().split()))
           if not validare(n, A, m, B):
               print("Datele nu corespund restricțiilor impuse.")
           else:
               print(se_poate_reduca_la_B(A, B))

</syntaxhighlight>

Explicatie Rezolvare

validate_data(a, b): Această funcție primește ca parametri două liste, a și b, reprezentând cele două tablouri. Funcția validează dacă datele introduse respectă restricțiile problemei, adică dacă dimensiunile celor două tablouri sunt între 1 și 1000 și dacă toate elementele tablourilor sunt numere naturale între 1 și 10000. Dacă datele sunt valide, funcția returnează True, în caz contrar returnează False.

reduce(a, b): Această funcție primește ca parametri două liste, a și b, reprezentând cele două tablouri. Funcția verifică dacă tabloul a se poate reduce la tabloul b. În acest scop, parcurge fiecare element al tabloului b și caută în tabloul a o secvență de elemente consecutive aflate pe poziții consecutive în tabloul a, a cărei sumă să fie egală cu elementul curent din tabloul b. Dacă găsește o astfel de secvență, o elimină din tabloul a și trece la următorul element din tabloul b. Dacă nu găsește o astfel de secvență, funcția returnează False. Dacă se parcurge cu succes întregul tablou b și toate elementele sale au fost găsite în tabloul a, funcția returnează True.

main(): Această funcție este funcția principală a programului. Ea citeste datele de intrare din consolă, apoi validează datele folosind funcția validate_data. Dacă datele sunt valide, se parcurg cele t teste și pentru fiecare test se citesc cele două tablouri și se apelează funcția reduce pentru a verifica dacă primul tablou se poate reduce la cel de-al doilea. Rezultatul verificării se afișează în consolă. Dacă datele nu sunt valide, se afișează un mesaj corespunzător.