3737 - SecvEgale1 v2

Sursa: - SecvEgale1 v2

---

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, separate prin spații, reprezentând elementele vectorului.

Date de ieșire

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

• 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

Exemplul 1

Intrare

12

6 6 8 3 6 6 3 8 4 3 3 4

Ieșire

Datele sunt corecte.

4 11

Exemplul 2

Intrare

7

1 2 3 4 1 7 8

Ieșire

Datele sunt corecte.

1 5

Exemplul 3

Intrare

2

314441 41241241

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 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=int(input())
   vector = list(map(int,input().split()))
   
   if n > 1000000 or n < 1:
       print("Datele nu sunt comform restricțiilor impuse.")
       exit()
   for x in vector:
       if x > 1000000 or x < 0:
           print("Datele nu sunt comform restricțiilor impuse.")
           exit()
   print("Datele sunt corecte.")
   return vector, n

if __name__ == '__main__':

   vector, n = conform_restrictiilor()
   secvente(vector, n)

</syntaxhighlight>

Explicaţie cod

Funcția conform_restrictiilor() primește input-ul de la tastatură și verifică dacă este conform restricțiilor impuse. Aceasta primește un întreg n care reprezintă numărul de elemente din vector, iar apoi primește n numere separate prin spații și le atribuie vectorului vector. Programul verifică dacă numărul de elemente și numerele din vector îndeplinesc restricțiile impuse. În caz negativ, programul afișează mesajul "Datele nu sunt comform restricțiilor impuse." și se încheie prin apelul funcției exit(). În caz pozitiv, programul afișează mesajul "Datele sunt corecte." și continuă cu apelul funcției secvente().

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.