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.

2

3

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0071 - Reducere

def can_reduce(A, B):

   n = len(A)
   m = len(B)

   i = j = 0
   while i < n and j < m:
       if A[i] == B[j]:
           i += 1
           j += 1
       else:
           sum_a = A[i]
           sum_b = B[j]
           while i < n-1 and sum_a != sum_b:
               i += 1
               sum_a += A[i]
           while j < m-1 and sum_a != sum_b:
               j += 1
               sum_b += B[j]
           if sum_a != sum_b:
               return False
   
   return j == m

if __name__ == "__main__":

   T = int(input())
   for i in range(T):
       n = int(input())
       A = list(map(int, input().split()))
       m = int(input())
       B = list(map(int, input().split()))

       if n < 1 or n > 1000 or m < 1 or m > 1000:
           print("Datele nu corespund restricțiilor impuse.")
           continue

       if any(x < 1 or x > 10000 for x in A) or any(x < 1 or x > 10000 for x in B):
           print("Datele nu corespund restricțiilor impuse.")
           continue

       if sum(A) != sum(B):
           print(0)
           continue

       if can_reduce(A, B):
           print(1)
       else:
           print(0)

</syntaxhighlight>

Explicatie Rezolvare

Programul are o singură funcție numită reduce_to_b. Această funcție primește ca argumente două liste a și b, și returnează o valoare de tipul boolean, care indică dacă lista a se poate reduce la lista b.

În interiorul funcției, se parcurge lista b și se caută secvențele din lista a care adunate dau fiecare element din lista b. Pentru aceasta, se pornește de la prima poziție din lista a și se adună elementele de la acea poziție până când suma acestora este egală cu primul element din lista b. Dacă s-a găsit o astfel de secvență, se trece la următorul element din lista b și se caută o altă secvență începând de la poziția imediat următoare celei la care s-a găsit ultima secvență. Dacă nu s-a găsit nicio secvență care să corespundă elementului curent din lista b, funcția returnează False. Dacă s-au găsit secvențe corespunzătoare tuturor elementelor din lista b, funcția returnează True.

În funcția main se face citirea datelor și se apelaează funcția reduce_to_b pentru fiecare set de date. În funcție de rezultatul returnat de această funcție, se afișează 1 sau 0, în funcție de faptul că lista a se poate reduce la lista b sau nu.