0524 - SecvEgale1: Diferență între versiuni
(Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/524/secvegale1 0524 - SecvEgale1] ---- == Cerinţa == Se dă un vector cu n elemente, numere naturale. Determinați cea mai lungă secvență de elemente din vector care începe și se termină cu aceeași valoare. Dacă în vector există mai multe secvențe corecte de lungime maximă se va determina cea mai din stânga. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi n numere naturale, reprezentând eleme...) |
Fără descriere a modificării |
||
(Nu s-au afișat 5 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, reprezentând elementele vectorului. | Programul citește de la tastatură numărul n, iar apoi n numere naturale, reprezentând elementele vectorului. | ||
== 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 indicii st dr ai capetelor secvenței determinate, separați printr-un spațiu''', 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 ≤ n ≤ 1000 | * 1 ≤ n ≤ 1000 | ||
* cele n numere citite vor fi mai mici decât 1.000.000.000 | * cele n numere citite vor fi mai mici decât 1.000.000.000 | ||
* indexarea elementelor vectorului începe de la 1. | * indexarea elementelor vectorului începe de la 1. | ||
== Exemplu == | == Exemplu 1 == | ||
; Intrare | ; Intrare | ||
: 12 | : 12 | ||
: 6 6 8 3 6 6 3 8 4 3 3 4 | : 6 6 8 3 6 6 3 8 4 3 3 4 | ||
; Ieșire | ; Ieșire | ||
: Datele sunt introduse corect.. | |||
: 4 11 | : 4 11 | ||
== Exemplu 2 == | |||
; Intrare | |||
: 11 | |||
: 6 2 8 3 3 6 3 8 4 1 3 4 | |||
; Ieșire | |||
: Datele nu corespund restricțiilor impuse. | |||
== Rezolvare == | == Rezolvare == | ||
Linia 23: | Linia 32: | ||
# 0524 - SecvEgale1 | # 0524 - SecvEgale1 | ||
n | def validate_input(n, v): | ||
if not (isinstance(n, int) and n >= 1 and n <= 1000): | |||
return False | |||
if not all(isinstance(x, int) and x >= 0 and x < 1000000000 for x in v): | |||
return False | |||
return True | |||
max_len = 0 | def find_identical_sequence(n, v): | ||
max_len = 0 | |||
seq_start = None | |||
seq_end = None | |||
for i in range(n): | |||
for j in range(i+1, n+1): | |||
if v[i:j] == v[i:j][::-1] and j-i > max_len: | |||
seq_start = i+1 | |||
seq_end = j | |||
max_len = j-i | |||
if max_len > 0: | |||
return (seq_start, seq_end) | |||
else: | |||
return None | |||
if __name__ == "__main__": | |||
n = int(input()) | |||
v = list(map(int, input().split())) | |||
if validate_input(n, v): | |||
result = find_identical_sequence(n, v) | |||
if result: | |||
print("Datele sunt introduse corect.") | |||
print(result[0], result[1]) | |||
else: | |||
print("Nu exista secventa identica.") | |||
else: | |||
print("Datele nu corespund restricțiilor impuse.") | |||
</syntaxhighlight> | </syntaxhighlight> | ||
== Explicatie Rezolvare == | |||
Funcția validate_input primește n și v și verifică dacă n se află în intervalul [1, 1000] și dacă fiecare element al listei v se află în intervalul [0, 1000000000]. Dacă datele sunt valide, funcția returnează True, altfel returnează False. | |||
Funcția find_identical_sequence primește n și v și parcurge fiecare posibilă subsecvență a lui v. Dacă subsecvența este identică cu inversul ei și este mai mare decât lungimea maximă găsită până acum, actualizează lungimea maximă și poziția de început și sfârșit a secvenței. Dacă nu se găsește o secvență identică, funcția returnează None. | |||
În funcția if __name__ == "__main__", citim n și v și verificăm dacă datele sunt valide. Dacă sunt, apelăm find_identical_sequence și afișăm secvența identică dacă există. Altfel, afișăm un mesaj de eroare corespunzător. |
Versiunea curentă din 14 mai 2023 20:04
Sursa: 0524 - SecvEgale1
Cerinţa
Se dă un vector cu n elemente, numere naturale. Determinați cea mai lungă secvență de elemente din vector care începe și se termină cu aceeași valoare. Dacă în vector există mai multe secvențe corecte de lungime maximă se va determina cea mai din stânga.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, reprezentând elementele vectorului.
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 indicii st dr ai capetelor secvenței determinate, separați printr-un spațiu, 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 ≤ n ≤ 1000
- cele n numere citite vor fi mai mici decât 1.000.000.000
- indexarea elementelor vectorului începe de la 1.
Exemplu 1
- Intrare
- 12
- 6 6 8 3 6 6 3 8 4 3 3 4
- Ieșire
- Datele sunt introduse corect..
- 4 11
Exemplu 2
- Intrare
- 11
- 6 2 8 3 3 6 3 8 4 1 3 4
- Ieșire
- Datele nu corespund restricțiilor impuse.
Rezolvare
Rezolvare ver. 1
# 0524 - SecvEgale1
def validate_input(n, v):
if not (isinstance(n, int) and n >= 1 and n <= 1000):
return False
if not all(isinstance(x, int) and x >= 0 and x < 1000000000 for x in v):
return False
return True
def find_identical_sequence(n, v):
max_len = 0
seq_start = None
seq_end = None
for i in range(n):
for j in range(i+1, n+1):
if v[i:j] == v[i:j][::-1] and j-i > max_len:
seq_start = i+1
seq_end = j
max_len = j-i
if max_len > 0:
return (seq_start, seq_end)
else:
return None
if __name__ == "__main__":
n = int(input())
v = list(map(int, input().split()))
if validate_input(n, v):
result = find_identical_sequence(n, v)
if result:
print("Datele sunt introduse corect.")
print(result[0], result[1])
else:
print("Nu exista secventa identica.")
else:
print("Datele nu corespund restricțiilor impuse.")
Explicatie Rezolvare
Funcția validate_input primește n și v și verifică dacă n se află în intervalul [1, 1000] și dacă fiecare element al listei v se află în intervalul [0, 1000000000]. Dacă datele sunt valide, funcția returnează True, altfel returnează False.
Funcția find_identical_sequence primește n și v și parcurge fiecare posibilă subsecvență a lui v. Dacă subsecvența este identică cu inversul ei și este mai mare decât lungimea maximă găsită până acum, actualizează lungimea maximă și poziția de început și sfârșit a secvenței. Dacă nu se găsește o secvență identică, funcția returnează None.
În funcția if __name__ == "__main__", citim n și v și verificăm dacă datele sunt valide. Dacă sunt, apelăm find_identical_sequence și afișăm secvența identică dacă există. Altfel, afișăm un mesaj de eroare corespunzător.