0519 - Secventa1: Difference between revisions
Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/519/secventa1 0519 - Secventa1] ---- == Cerinţa == Se dă un vector x cu n elemente, numere naturale și un vector y cu m elemente, numere naturale. Să se verifice dacă vectorul y este 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 == Programul... |
No edit summary |
||
(5 intermediate revisions by the same user not shown) | |||
Line 6: | Line 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 p, reprezentând poziția din vectorul x de unde începe secvența y, dacă y este secvență în x, respectiv mesajul NU dacă y nu este secvență în x''', 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 | ||
* elementele celor doi vectori vor fi indexate de la 1 | * elementele celor doi vectori vor fi indexate de la 1 | ||
* dacă vectorul y este de mai multe ori secvență în x se va afișa poziția de început a primei apariții | * dacă vectorul y este de mai multe ori secvență în x se va afișa poziția de început a primei apariții | ||
== Exemplu == | == Exemplu 1 == | ||
; Intrare | ; Intrare | ||
: 10 | : 10 | ||
Line 18: | Line 19: | ||
: 8 5 2 3 10 7 | : 8 5 2 3 10 7 | ||
; Ieșire | ; Ieșire | ||
: Datele sunt introduse corect. | |||
: 3 | : 3 | ||
== Exemplu 2 == | |||
; Intrare | |||
: 1 | |||
: 2 3 4 5 6 7 8 3 1 11 2 | |||
: 4 | |||
: 1 2 3 4 5 6 | |||
; Ieșire | |||
: Datele nu corespund restricțiilor impuse. | |||
== Rezolvare == | == Rezolvare == | ||
Line 25: | Line 37: | ||
# 0519 - Secventa1 | # 0519 - Secventa1 | ||
n = | def find_sequence(x, y): | ||
x = | |||
n = len(x) | |||
m = len(y) | |||
if m > n: | |||
return -1 | |||
for i in range(n - m + 1): | |||
if x[i:i+m] == y: | |||
return i + 1 | |||
return -1 | |||
def validate_input(n, m): | |||
m = | if not(1 <= m <= n <= 1000): | ||
return False | |||
return True | |||
if __name__ == '__main__': | |||
if | # Citim input-ul | ||
print( | n = int(input()) | ||
x = list(map(int, input().split())) | |||
else: | m = int(input()) | ||
y = list(map(int, input().split())) | |||
# Validam input-ul | |||
if not validate_input(n, m): | |||
print('Datele nu corespund restrictiilor impuse.') | |||
exit() | |||
# Gasim secventa si afisam raspunsul | |||
poz = find_sequence(x, y) | |||
if poz != -1: | |||
print('Datele sunt introduse corect.') | |||
print(poz) | |||
else: | |||
print('Datele sunt introduse corect.') | |||
print('NU') | |||
</syntaxhighlight> | </syntaxhighlight> | ||
== Explicatie Rezolvare == | |||
Funcția validate_input verifică restricțiile impuse și returnează True dacă datele sunt valide, sau False în caz contrar. | |||
Funcția find_subsequence caută secvența y în vectorul x și returnează poziția de început a secvenței sau -1 dacă secvența nu a fost găsită. | |||
În funcția main citim datele de intrare și le trimitem la funcția de validare. Dacă datele sunt valide, afișăm mesajul "Datele sunt introduse corect." și apoi apelăm funcția de rezolvare pentru a găsi poziția de început a secvenței y în vectorul x. În caz contrar, afișăm mesajul "Datele nu corespund restricțiilor impuse." |
Latest revision as of 19:43, 14 May 2023
Sursa: 0519 - Secventa1
Cerinţa[edit | edit source]
Se dă un vector x cu n elemente, numere naturale și un vector y cu m elemente, numere naturale. Să se verifice dacă vectorul y este secvență în vectorul x.
Date de intrare[edit | edit source]
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[edit | edit source]
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 p, reprezentând poziția din vectorul x de unde începe secvența y, dacă y este secvență în x, respectiv mesajul NU dacă y nu este secvență în x, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".
Restricţii şi precizări[edit | edit source]
- 1 ≤ m ≤ n ≤ 1000
- elementele celor doi vectori vor fi indexate de la 1
- dacă vectorul y este de mai multe ori secvență în x se va afișa poziția de început a primei apariții
Exemplu 1[edit | edit source]
- Intrare
- 10
- 8 5 8 5 2 3 10 7 1 6
- 6
- 8 5 2 3 10 7
- Ieșire
- Datele sunt introduse corect.
- 3
Exemplu 2[edit | edit source]
- Intrare
- 1
- 2 3 4 5 6 7 8 3 1 11 2
- 4
- 1 2 3 4 5 6
- Ieșire
- Datele nu corespund restricțiilor impuse.
Rezolvare[edit | edit source]
Rezolvare ver. 1[edit | edit source]
<syntaxhighlight lang="python" line>
- 0519 - Secventa1
def find_sequence(x, y):
n = len(x) m = len(y) if m > n: return -1 for i in range(n - m + 1): if x[i:i+m] == y: return i + 1 return -1
def validate_input(n, m):
if not(1 <= m <= n <= 1000): return False return True
if __name__ == '__main__':
# Citim input-ul n = int(input()) x = list(map(int, input().split())) m = int(input()) y = list(map(int, input().split()))
# Validam input-ul if not validate_input(n, m): print('Datele nu corespund restrictiilor impuse.') exit()
# Gasim secventa si afisam raspunsul poz = find_sequence(x, y) if poz != -1: print('Datele sunt introduse corect.') print(poz) else: print('Datele sunt introduse corect.') print('NU')
</syntaxhighlight>
Explicatie Rezolvare[edit | edit source]
Funcția validate_input verifică restricțiile impuse și returnează True dacă datele sunt valide, sau False în caz contrar.
Funcția find_subsequence caută secvența y în vectorul x și returnează poziția de început a secvenței sau -1 dacă secvența nu a fost găsită.
În funcția main citim datele de intrare și le trimitem la funcția de validare. Dacă datele sunt valide, afișăm mesajul "Datele sunt introduse corect." și apoi apelăm funcția de rezolvare pentru a găsi poziția de început a secvenței y în vectorul x. În caz contrar, afișăm mesajul "Datele nu corespund restricțiilor impuse."