0520 - Secventa2: Diferență între versiuni
(Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/520/secventa2 0520 - Secventa2] ---- == Cerinţa == Se dă un vector x cu n elemente, numere naturale și un vector y cu m elemente, numere naturale. Să se determine de câte ori este vectorul y secvență în vectorul x. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y. == Date de ieșire == Pr...) |
Fără descriere a modificării |
||
(Nu s-au afișat 4 versiuni intermediare efectuate de același utilizator) | |||
Linia 6: | Linia 6: | ||
Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y. | Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y. | ||
== 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 '''va afișa pe ecran numărul C, reprezentând valoarea cerută''', 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 == | ||
* 1 ≤ m ≤ n ≤ 1000 | * 1 ≤ m ≤ n ≤ 1000 | ||
== Exemplu == | == Exemplu 1 == | ||
; Intrare | ; Intrare | ||
: 10 | : 10 | ||
Linia 16: | Linia 17: | ||
: 8 5 8 | : 8 5 8 | ||
; Ieșire | ; Ieșire | ||
: Datele sunt introduse corect. | |||
: 3 | : 3 | ||
== Exemplu 2 == | |||
; Intrare | |||
: 11 | |||
: 2 3 4 5 7 1 8 3 2 | |||
: 2 | |||
: 1 2 1 | |||
; Ieșire | |||
: Datele nu corespund restricțiilor impuse. | |||
== Rezolvare == | == Rezolvare == | ||
Linia 23: | Linia 34: | ||
# 0520 - Secventa2 | # 0520 - Secventa2 | ||
n = int(input()) | import sys | ||
x = list(map(int, input().split())) | |||
m = int(input()) | def validate_input(n, x, m, y): | ||
y = list(map(int, input().split())) | if not(1 <= n <= 1000) or not(1 <= m <= 1000): | ||
return False | |||
if len(x) != n or len(y) != m: | |||
return False | |||
for elem in x + y: | |||
if not isinstance(elem, int) or elem < 0: | |||
return False | |||
return True | |||
def count_subsequences(n, x, m, y): | |||
count = 0 | |||
for i in range(n-m+1): | |||
# Verificăm dacă vectorul y apare ca secvență în x începând de la poziția i | |||
if x[i:i+m] == y: | |||
count += 1 | |||
return count | |||
if __name__ == "__main__": | |||
# Citim datele de intrare | |||
n = int(input()) | |||
x = list(map(int, input().split())) | |||
m = int(input()) | |||
y = list(map(int, input().split())) | |||
# Validăm datele de intrare | |||
if not validate_input(n, x, m, y): | |||
print("Datele nu corespund restricțiilor impuse.") | |||
sys.exit(0) | |||
# Datele sunt introduse corect | |||
print("Datele sunt introduse corect.") | |||
# Calculăm și afișăm numărul de apariții ale lui y ca secvență în x | |||
print(count_subsequences(n, x, m, y)) | |||
</syntaxhighlight> | </syntaxhighlight> | ||
== Explicatie Rezolvare == | |||
validate_input(n, x, m, y) - această funcție primește ca argumente numărul de elemente ale vectorului x (n), vectorul x, numărul de elemente ale vectorului y (m) și vectorul y. Funcția verifică dacă datele de intrare sunt valide, adică dacă 1 <= n <= 1000, 1 <= m <= 1000, vectorii x și y au lungimea corespunzătoare numărului de elemente specificat, iar toate elementele din x și y sunt numere întregi pozitive. Funcția returnează True dacă datele de intrare sunt valide și False în caz contrar. | |||
count_subsequences(n, x, m, y) - această funcție primește ca argumente numărul de elemente ale vectorului x (n), vectorul x, numărul de elemente ale vectorului y (m) și vectorul y. Funcția parcurge toate pozițiile posibile din vectorul x și verifică dacă vectorul y apare ca subsecvență în x începând de la fiecare poziție. Pentru a face aceasta, se verifică egalitatea între slice-urile de lungime m din x și vectorul y. Dacă x[i:i+m] == y, numărul de apariții al vectorului y ca subsecvență în x este incrementat cu 1. La final, funcția returnează numărul de apariții al vectorului y ca subsecvență în x. | |||
În blocul principal if __name__ == "__main__", datele de intrare sunt citite de la tastatură și apoi verificate prin apelul funcției validate_input. Dacă datele sunt valide, se afișează mesajul "Datele sunt introduse corect." și numărul de apariții al vectorului y ca subsecvență în x. În caz contrar, se afișează mesajul "Datele nu corespund restricțiilor impuse.". |
Versiunea curentă din 14 mai 2023 19:49
Sursa: 0520 - Secventa2
Cerinţa
Se dă un vector x cu n elemente, numere naturale și un vector y cu m elemente, numere naturale. Să se determine de câte ori este vectorul y secvență în vectorul x.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y.
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 va afișa pe ecran numărul C, reprezentând valoarea cerută, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".
Restricţii şi precizări
- 1 ≤ m ≤ n ≤ 1000
Exemplu 1
- Intrare
- 10
- 8 5 8 5 8 3 8 5 8 6
- 3
- 8 5 8
- Ieșire
- Datele sunt introduse corect.
- 3
Exemplu 2
- Intrare
- 11
- 2 3 4 5 7 1 8 3 2
- 2
- 1 2 1
- Ieșire
- Datele nu corespund restricțiilor impuse.
Rezolvare
Rezolvare ver. 1
# 0520 - Secventa2
import sys
def validate_input(n, x, m, y):
if not(1 <= n <= 1000) or not(1 <= m <= 1000):
return False
if len(x) != n or len(y) != m:
return False
for elem in x + y:
if not isinstance(elem, int) or elem < 0:
return False
return True
def count_subsequences(n, x, m, y):
count = 0
for i in range(n-m+1):
# Verificăm dacă vectorul y apare ca secvență în x începând de la poziția i
if x[i:i+m] == y:
count += 1
return count
if __name__ == "__main__":
# Citim datele de intrare
n = int(input())
x = list(map(int, input().split()))
m = int(input())
y = list(map(int, input().split()))
# Validăm datele de intrare
if not validate_input(n, x, m, y):
print("Datele nu corespund restricțiilor impuse.")
sys.exit(0)
# Datele sunt introduse corect
print("Datele sunt introduse corect.")
# Calculăm și afișăm numărul de apariții ale lui y ca secvență în x
print(count_subsequences(n, x, m, y))
Explicatie Rezolvare
validate_input(n, x, m, y) - această funcție primește ca argumente numărul de elemente ale vectorului x (n), vectorul x, numărul de elemente ale vectorului y (m) și vectorul y. Funcția verifică dacă datele de intrare sunt valide, adică dacă 1 <= n <= 1000, 1 <= m <= 1000, vectorii x și y au lungimea corespunzătoare numărului de elemente specificat, iar toate elementele din x și y sunt numere întregi pozitive. Funcția returnează True dacă datele de intrare sunt valide și False în caz contrar.
count_subsequences(n, x, m, y) - această funcție primește ca argumente numărul de elemente ale vectorului x (n), vectorul x, numărul de elemente ale vectorului y (m) și vectorul y. Funcția parcurge toate pozițiile posibile din vectorul x și verifică dacă vectorul y apare ca subsecvență în x începând de la fiecare poziție. Pentru a face aceasta, se verifică egalitatea între slice-urile de lungime m din x și vectorul y. Dacă x[i:i+m] == y, numărul de apariții al vectorului y ca subsecvență în x este incrementat cu 1. La final, funcția returnează numărul de apariții al vectorului y ca subsecvență în x.
În blocul principal if __name__ == "__main__", datele de intrare sunt citite de la tastatură și apoi verificate prin apelul funcției validate_input. Dacă datele sunt valide, se afișează mesajul "Datele sunt introduse corect." și numărul de apariții al vectorului y ca subsecvență în x. În caz contrar, se afișează mesajul "Datele nu corespund restricțiilor impuse.".