0524 - SecvEgale1

From Bitnami MediaWiki
Revision as of 20:04, 14 May 2023 by Flaviu (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

<syntaxhighlight lang="python" line>

  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.")



</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.