0518 - SecvZero

Cerinţa

Se dă un vector cu n elemente numere naturale. Determinați cea mai lungă secvență de elemente nule din vector. Dacă în vector există mai multe secvențe de elemente nule 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 numărul de perechi care îndeplinesc condițiile cerute, 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
vectorul va conține cel puțin un element nul

Exemplu 1

Intrare: 10; 0 1 0 0 0 5 0 0 0 2
Ieșire: Datele sunt introduse correct.; 3 5

Exemplu 2

Intrare: 2; 2 1 1 0 0 3 4
Ieșire: Datele nu corespund restricțiilor impuse.; 2 5

Rezolvare

Rezolvare ver. 1

0518 - SecvZero

def validate_input(n, v):

   if n < 1 or n > 1000:
       print("n nu respecta restricțiile impuse")
       return False
   if all(elem == 0 for elem in v):
       print("vectorul nu poate contine doar elemente nule")
       return False
   for i in range(n):
       if v[i] < 0 or v[i] > 1000000:
           print("valorile din v trebuie sa fie in intervalul [0, 1000000]")
           return False
   return True

def find_longest_sequence(n, v):

   max_len = 0
   start = -1
   end = -1
   i = 0
   while i < n:
       if v[i] == 0:
           i += 1
       else:
           j = i
           while j < n and v[j] != 0:
               j += 1
           if j - i > max_len:
               max_len = j - i
               start = i
               end = j-1
           i = j
   return (start+1, end+1)

def read_input():

   try:
       n = int(input("Introduceti valoarea lui n: "))
       v = list(map(int, input("Introduceti valorile vectorului, separate prin spatiu: ").split()))
       if not validate_input(n, v):
           print("Datele nu corespund restricțiilor impuse.")
           return None, None
       print("Datele sunt introduse corect.")
       return n, v
   except ValueError:
       print("Datele nu corespund formatului așteptat.")
       return None, None

if __name__ == '__main__':

   n, v = read_input()
   if n is not None and v is not None:
       start, end = find_longest_sequence(n, v)
       print(start, end)

</syntaxhighlight>

Explicație rezolvare

validate_input(n, v) valideaza datele de intrare. Se verifica daca n este in intervalul permis, daca fiecare element din v este mai mic decat 1000 si daca vectorul contine cel putin un element 0. Daca una dintre aceste conditii nu este indeplinita, se afiseaza un mesaj de eroare si se returneaza False. find_longest_sequence(n, v) determina cea mai lunga secventa de elemente nule din vector. Se foloseste o metoda de tip "sliding window", unde se parcurge vectorul, se identifica toate secventele de elemente nule si se retine cea mai lunga si pozitia ei de inceput. Deoarece dorim sa identificam cea mai din stanga secventa de lungime maxima, pozitia de inceput a secventei se retine prin variabila start. Se returneaza o pereche de indici, reprezentand capetele secventei. read_input() citeste datele de intrare si le valideaza cu ajutorul functiei validate_input(). Daca datele sunt valide, functia returneaza n si v. In if __name__ == '__main__' se citesc datele de intrare cu ajutorul functiei read_input() si se apeleaza functia find_longest_sequence(), care determina cea mai lunga secventa de elemente nule din vector. Indicii capetelor secventei se afiseaza cu ajutorul functiei print().