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

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

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 nu corespund restricțiilor impuse.

2

3

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0071 - Reducere

def citeste_date_intrare():

   n = int(input())
   a = list(map(int, input().split()))
   m = int(input())
   b = list(map(int, input().split()))
   return a, b

def valideaza_datele_intrare(a, b):

   if not(0 < len(a) < 1001 and 0 < len(b) < 1001):
       return False
   if not(all(1 <= x <= 10000 for x in a) and all(1 <= x <= 10000 for x in b)):
       return False
   return True

def se_poate_reduce(a, b):

   i, j = 0, 0
   while i < len(a) and j < len(b):
       s = a[i]
       i += 1
       while i < len(a) and s < b[j]:
           s += a[i]
           i += 1
       if s != b[j]:
           return False
       j += 1
   return j == len(b)

if __name__ == '__main__':

   t = int(input())
   for _ in range(t):
       a, b = citeste_date_intrare()
       if valideaza_datele_intrare(a, b):
           if se_poate_reduce(a, b):
               print("Datele sunt introduse corect.")
               print(1)
           else:
               print("Datele sunt introduse corect.")
               print(0)
       else:
           print("Datele nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicatie Rezolvare

Funcția citeste_date_intrare() citește cele două tablouri A și B din intrare și le returnează ca o pereche de liste. Funcția valideaza_datele_intrare(a, b) verifică dacă cele două liste respectă constrângerile impuse de problemă și returnează True dacă da și False altfel. Funcția se_poate_reduce(a, b) verifică dacă tabloul A se poate reduce la tabloul B și returnează True dacă da și False altfel.

În funcția principală (if __name__ == '__main__':) se citește numărul de seturi de date de test t, apoi se parcurg t iterații pentru a procesa fiecare set de date. Se citesc cele două tablouri, se validează și se verifică dacă A se poate reduce la B și se afișează rezultatul.