0071 - Reducere: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/71/reducere 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, el...
 
Flaviu (talk | contribs)
No edit summary
Line 41: Line 41:
# 0071 - Reducere
# 0071 - Reducere


T = int(input())
def citeste_date_intrare():
 
    """Functia citeste datele de intrare si returneaza cele doua liste A si B."""
for _ in range(T):
     n = int(input())
     n = int(input())
     A = list(map(int, input().split()))
     a = [int(x) for x in input().split()]
     m = int(input())
     m = int(input())
     B = list(map(int, input().split()))
     b = [int(x) for x in input().split()]
    return a, b


     i = j = 0
def verifica_reducere(a, b):
     while i < n and j < m:
    """Verifica daca lista a se poate reduce la lista b."""
         sum = 0
     j = 0 # pozitia curenta in lista a
         while j < m and sum < A[i]:
     for x in b:
             sum += B[j]
         s = 0 # suma elementelor consecutive din lista a
         while j < len(a) and s < x:
             s += a[j]
             j += 1
             j += 1
         if sum != A[i]:
         if s != x:
             break
             return False
        i += 1
    return True
     if i == n:
 
        print(1)
if __name__ == '__main__':
    else:
    t = int(input())  # numarul de teste
        print(0)
     for i in range(t):
        a, b = citeste_date_intrare()
        if verifica_reducere(a, b):
            print(1)
        else:
            print(0)




</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
În funcția citeste_date_intrare citim numărul de elemente ale fiecărei liste, apoi citim elementele și le returnăm ca o pereche de liste.
În funcția verifica_reducere parcurgem lista b și pentru fiecare element verificăm dacă se poate obține ca sumă a unor elemente consecutive din lista a. Pentru aceasta, ținem cont de poziția curentă j în lista a și calculăm suma s a elementelor consecutive din această listă începând de la poziția j până când această sumă depășește elementul curent din lista b sau ajungem la sfârșitul listei a. Dacă la sfârșitul verificării suma s nu este egală cu elementul curent din lista b, atunci lista a nu se poate reduce la lista b și funcția returnează False.
În blocul if __name__ == '__main__' citim numărul de teste, apoi citim datele de intrare pentru fiecare test și verificăm dacă lista a se poate reduce la lista b. Rezultatul verificării este afișat pe ecran.

Revision as of 19:57, 17 April 2023

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

Programul 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, respectiv 0 în caz contrar.

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
1
0

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0071 - Reducere

def citeste_date_intrare():

   """Functia citeste datele de intrare si returneaza cele doua liste A si B."""
   n = int(input())
   a = [int(x) for x in input().split()]
   m = int(input())
   b = [int(x) for x in input().split()]
   return a, b

def verifica_reducere(a, b):

   """Verifica daca lista a se poate reduce la lista b."""
   j = 0  # pozitia curenta in lista a
   for x in b:
       s = 0  # suma elementelor consecutive din lista a
       while j < len(a) and s < x:
           s += a[j]
           j += 1
       if s != x:
           return False
   return True

if __name__ == '__main__':

   t = int(input())  # numarul de teste
   for i in range(t):
       a, b = citeste_date_intrare()
       if verifica_reducere(a, b):
           print(1)
       else:
           print(0)


</syntaxhighlight>

Explicatie Rezolvare

În funcția citeste_date_intrare citim numărul de elemente ale fiecărei liste, apoi citim elementele și le returnăm ca o pereche de liste. În funcția verifica_reducere parcurgem lista b și pentru fiecare element verificăm dacă se poate obține ca sumă a unor elemente consecutive din lista a. Pentru aceasta, ținem cont de poziția curentă j în lista a și calculăm suma s a elementelor consecutive din această listă începând de la poziția j până când această sumă depășește elementul curent din lista b sau ajungem la sfârșitul listei a. Dacă la sfârșitul verificării suma s nu este egală cu elementul curent din lista b, atunci lista a nu se poate reduce la lista b și funcția returnează False. În blocul if __name__ == '__main__' citim numărul de teste, apoi citim datele de intrare pentru fiecare test și verificăm dacă lista a se poate reduce la lista b. Rezultatul verificării este afișat pe ecran.