3737 - SecvEgale1 v2
Sursa: - SecvEgale1 v2
Cerinţa[edit | edit source]
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[edit | edit source]
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând elementele vectorului.
Date de ieșire[edit | edit source]
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.", iar apoi va afișa pe ecran indicii st dr ai capetelor secvenței determinate, separați printr-un spațiu. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".
Restricţii şi precizări[edit | edit source]
- 1 ≤ n ≤ 1.000.000
- cele n numere citite vor fi mai mici decât 1.000.000
- indexarea elementelor vectorului începe de la 1.
Exemple[edit | edit source]
Exemplul 1[edit | edit source]
- Intrare
- 12
- 6 6 8 3 6 6 3 8 4 3 3 4
- Ieșire
- Datele sunt corecte.
- 4 11
Exemplul 2[edit | edit source]
- Intrare
- 7
- 1 2 3 4 1 7 8
- Ieșire
- Datele sunt corecte.
- 1 5
Exemplul 3[edit | edit source]
- Intrare
- 2
- 314441 41241241
- Ieșire
- Datele nu sunt comform restricțiilor impuse.
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line>
- 3737
def secvente(vector, n):
lungime_maxima=0 st = 0 dr = 0 for i in range(n): for j in range(i+1 , n+1): if vector[i] == vector [j-1] and j - i > lungime_maxima: lungime_maxima = j-i st = i dr = j-1 print(st+1, dr+1)
def conform_restrictiilor(n, vector):
if n > 1000000 or n < 1: print("Datele nu sunt comform restricțiilor impuse.") return False for x in vector: if x > 1000000 or x < 0: print("Datele nu sunt comform restricțiilor impuse.") return False print("Datele sunt corecte.") return True
if __name__ == '__main__':
n=int(input()) vector = list(map(int,input().split())) if conform_restrictiilor(n, vector) is True: secvente(vector, n)
</syntaxhighlight>
Explicaţie cod[edit | edit source]
Funcția secvente() primește vectorul vector și numărul de elemente din vector n. Acestă funcție calculează cea mai lungă secvență de elemente din vector care începe și se termină cu aceeași valoare. Inițial, variabilele lungime_maxima, st și dr sunt inițializate cu 0. Două bucle for sunt utilizate pentru a itera prin toate elementele vectorului și pentru a găsi secvențele de lungime maximă. Când sunt găsite două elemente consecutive egale, se calculează lungimea secvenței, iar dacă aceasta este mai mare decât lungimea maximă găsită anterior, atunci variabilele st și dr sunt actualizate cu indicii elementelor de început și de sfârșit ai secvenței. Indicii afișați sunt incrementați cu 1 pentru a corespunde indexării elementelor în program, care începe de la 1, nu de la 0. Funcția conform_restrictiilor primește un numar n și o listă vector și verifică dacă sunt respectate restricțiile problemei (0 < n < 1000000, 0 ≤ vector[i] ≤ 1000000 pentru fiecare i în [0, n)). Dacă restricțiile nu sunt respectate, funcția afișează un mesaj de eroare și returnează False; în caz contrar, afișează un mesaj de confirmare și returnează True.
În blocul __name__ == '__main__', programul citește dimensiunea și secvența de la intrare folosind input() și map(). Apoi verifică dacă restricțiile sunt respectate utilizând funcția conform_restrictiilor. Dacă restricțiile sunt respectate, funcția secvente este apelată cu vector și n ca argumente.