0071 - Reducere: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
 
Linia 51: Linia 51:
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.
: 2
 
: 3
== Rezolvare ==  
== Rezolvare ==  
=== Rezolvare ver. 1 ===
=== Rezolvare ver. 1 ===
Linia 58: Linia 57:
# 0071 - Reducere
# 0071 - Reducere


def can_reduce(A, B):
def se_poate_reduca_la_B(A, B):
    i = j = 0
     n = len(A)
     n = len(A)
     m = len(B)
     m = len(B)
    i = j = 0
     while i < n and j < m:
     while i < n and j < m:
         if A[i] == B[j]:
         if A[i] == B[j]:
Linia 68: Linia 66:
             j += 1
             j += 1
         else:
         else:
             sum_a = A[i]
             s = A[i]
             sum_b = B[j]
             i += 1
             while i < n-1 and sum_a != sum_b:
             while i < n and s < B[j]:
                s += A[i]
                 i += 1
                 i += 1
                sum_a += A[i]
             if s != B[j]:
             while j < m-1 and sum_a != sum_b:
                 return 0
                j += 1
            j += 1
                sum_b += B[j]
            if sum_a != sum_b:
                 return False
   
     return j == m
     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__":
if __name__ == "__main__":
     T = int(input())
     T = int(input())
     for i in range(T):
     if T <= 0 or T > 10:
        n = int(input())
        print("Datele nu corespund restricțiilor impuse.")
        A = list(map(int, input().split()))
    else:
        m = int(input())
        print("Datele sunt introduse corect.")
        B = list(map(int, input().split()))
        for i in range(T):
 
            n = int(input())
        if n < 1 or n > 1000 or m < 1 or m > 1000:
            A = list(map(int, input().split()))
             print("Datele nu corespund restricțiilor impuse.")
            m = int(input())
            continue
            B = list(map(int, input().split()))
 
             if not validare(n, A, m, B):
        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.")
            print("Datele nu corespund restricțiilor impuse.")
             else:
             continue
                print(se_poate_reduca_la_B(A, B))
 
        if sum(A) != sum(B):
            print(0)
            continue
 
        if can_reduce(A, B):
            print(1)
        else:
            print(0)


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== 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.
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.


Î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.
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.


Î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.
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.

Versiunea curentă din 14 mai 2023 20:14

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

# 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))

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.