0071 - Reducere: Diferență între versiuni
Fără descriere a modificării |
Fără descriere a modificării |
||
(Nu s-au afișat 4 versiuni intermediare efectuate de același utilizator) | |||
Linia 15: | Linia 15: | ||
== Date de ieșire == | == 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 == | == Restricţii şi precizări == | ||
Linia 21: | Linia 22: | ||
* elementele vectorilor A, B sunt numere naturale din intervalul [1,10000] | * elementele vectorilor A, B sunt numere naturale din intervalul [1,10000] | ||
0 < T ≤ 10 | 0 < T ≤ 10 | ||
== Exemplu == | == Exemplu 1 == | ||
; Intrare | ; Intrare | ||
: 2 | : 2 | ||
Linia 33: | Linia 34: | ||
: 5 3 4 | : 5 3 4 | ||
; Ieșire | ; Ieșire | ||
: Datele sunt introduse corect. | |||
: 1 | : 1 | ||
: 0 | : 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 == | ||
Linia 41: | Linia 57: | ||
# 0071 - Reducere | # 0071 - Reducere | ||
def | def se_poate_reduca_la_B(A, B): | ||
i = j = 0 | |||
n = | n = len(A) | ||
m = len(B) | |||
m = | while i < n and j < m: | ||
if A[i] == B[j]: | |||
return | 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 | 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 | return True | ||
if __name__ == | if __name__ == "__main__": | ||
T = int(input()) | |||
for i in range( | 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)) | |||
</syntaxhighlight> | </syntaxhighlight> | ||
== Explicatie Rezolvare == | == 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. |
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.