0071 - Reducere: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 41: Line 41:
; Intrare
; Intrare
: 2
: 2
: 12
: 1001
: 7 3 4 1 6 4 6 9 7 1 8 7
: 7 3 4 1 6 4 6 9 7 1 8 7
: 4
: 4
Line 58: Line 58:
# 0071 - Reducere
# 0071 - Reducere


def citeste_date_intrare():
def can_reduce(A, B):
     n = int(input())
     n = len(A)
    a = list(map(int, input().split()))
     m = len(B)
     m = int(input())
    b = list(map(int, input().split()))
    return a, b


def valideaza_datele_intrare(a, b):
    i = j = 0
     if not(0 < len(a) < 1001 and 0 < len(b) < 1001):
     while i < n and j < m:
         return False
         if A[i] == B[j]:
    if not(all(1 <= x <= 10000 for x in a) and all(1 <= x <= 10000 for x in b)):
            i += 1
        return False
            j += 1
     return True
        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


def se_poate_reduce(a, b):
if __name__ == "__main__":
     i, j = 0, 0
     T = int(input())
     while i < len(a) and j < len(b):
     for i in range(T):
         s = a[i]
         n = int(input())
         i += 1
         A = list(map(int, input().split()))
         while i < len(a) and s < b[j]:
         m = int(input())
            s += a[i]
        B = list(map(int, input().split()))
            i += 1
 
         if s != b[j]:
         if n < 1 or n > 1000 or m < 1 or m > 1000:
             return False
             print("Datele nu corespund restricțiilor impuse.")
        j += 1
            continue
    return j == len(b)


if __name__ == '__main__':
        if any(x < 1 or x > 10000 for x in A) or any(x < 1 or x > 10000 for x in B):
    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.")
             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>
</syntaxhighlight>
== Explicatie Rezolvare ==
== 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.
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 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.
Î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.

Revision as of 21:28, 13 May 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

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.