0523 - SecvEgale

From Bitnami MediaWiki
Revision as of 20:58, 13 May 2023 by Flaviu (talk | contribs)

Sursa: 0523 - SecvEgale


Cerinţa

Se dă un vector cu n elemente, numere naturale. Determinați cea mai lungă secvență de elemente egale din vector. Dacă în vector există mai multe secvențe de elemente egale de lungime maximă se va determina cea mai din dreapta.

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 numărul c, 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 1000
  • indicii elementelor vectorului sunt cuprinși între 1 și n

Exemplu

Intrare
10
5 5 1 1 1 1 2 2 2 2
Ieșire
Datele nu corespund restricțiilor impuse.
7 10

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0523 - SecvEgale

def longest_equal_sequence(n, v):

   max_len = 1
   max_pos = n - 1
   curr_len = 1
   
   for i in range(1, n):
       if v[i] == v[i-1]:
           curr_len += 1
           if curr_len > max_len:
               max_len = curr_len
               max_pos = i
       else:
           curr_len = 1
   
   return max_pos - max_len + 2, max_pos + 1

def main():

   n = int(input())
   if n < 1 or n > 1000:
       print("Datele nu corespund restricțiilor impuse.")
       return
   
   v = list(map(int, input().split()))
   for x in v:
       if x < 0 or x >= 1000:
           print("Datele nu corespund restricțiilor impuse.")
           return
   
   start, end = longest_equal_sequence(n, v)
   print("Datele sunt introduse corect.")
   print(end - start)


</syntaxhighlight>

Explicație rezolvare

În funcția main se citește numărul de elemente din vector și apoi vectorul însuși, apoi se apelează funcția find_longest_sequence cu vectorul ca argument.

Funcția find_longest_sequence primește un vector și determină cea mai lungă secvență de elemente egale. În primul rând, se initializează o variabilă current_count cu 1 și o variabilă max_count cu 1, pentru a contoriza câte elemente consecutive egale avem în momentul de față și, respectiv, câte elemente egale consecutive sunt în cea mai lungă secvență găsită până acum. De asemenea, se initializează o variabilă last_index cu -1 pentru a reține ultimul index la care am întâlnit o secvență de elemente egale de lungime maximă.

În continuare, se parcurge vectorul cu un for și se compară fiecare element cu elementul anterior, dacă sunt egale, incrementăm current_count, altfel resetăm current_count la 1. Dacă current_count este mai mare sau egal decât max_count, actualizăm valoarea lui max_count și reținem indexul curent în last_index.

La final, returnăm valoarea lui max_count și last_index. Aceste valori sunt apoi afișate în funcția main, dacă datele de intrare sunt corecte, altfel se afișează mesajul "Datele nu corespund restricțiilor impuse."