0981 - secventa11

Sursa: 0981 - secventa11

---

Cerinţa

Se dau n numere naturale. Determinaţi lungimea maximă a unei secvenţe de numere din şir cu proprietatea că în scrierea binară sunt formate doar din cifre de 1.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.

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 L, reprezentând lungimea maximă a unei secvenţe de elemente din şir cu proprietatea dată, 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 ≤ 300.000
• cele n numere citite vor fi mai mici decât 1.000.000
• dacă în șir nu sunt numere formate numai din cifre de 1 în baza 2, se va afișa 0

Exemplu 1

Intrare

5

4 6 7 15 88

Ieșire

Datele sunt introduse correct.

2

Exemplu 2

Intrare

1

2 4 13 25

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0981 - secventa11

def validate_input(n, lst):

   for i in range(n):
       if lst[i] < 0 or lst[i] > 1000000:
           return False
   return True

def get_max_ones(n, lst):

   if not validate_input(n, lst):
       print("Datele nu corespund restricțiilor impuse.")
       return 0
   max_ones = 0
   current_ones = 0
   for i in range(n):
       binary = bin(lst[i])[2:]  # convertim numarul in baza 2 si eliminam prefixul "0b"
       if all(digit == '1' for digit in binary):
           current_ones += 1
       else:
           if current_ones > max_ones:
               max_ones = current_ones
           current_ones = 0
   if current_ones > max_ones:  # verificam din nou pentru ultima secventa de 1-uri
       max_ones = current_ones
   print("Datele sunt introduse corect.")
   return max_ones

if __name__ == "__main__":

   n = int(input())
   lst = list(map(int, input().split()))
   print(get_max_ones(n, lst))

</syntaxhighlight>

Explicatie Rezolvare

Functia `validate_data` are rolul de a valida datele de intrare citite de la tastatura. In cazul in care datele nu corespund restrictiilor impuse de problema, se va afisa un mesaj de eroare si se va returna valoarea `False`. In caz contrar, se va returna valoarea `True`.

Functia `max_length_binary_sequence` primeste ca parametru un vector de numere naturale si returneaza lungimea maxima a unei secvente de numere din vector care sunt formate doar din cifre de 1 in scrierea lor binara. Mai intai se parcurge vectorul si se trece prin fiecare element. Pentru fiecare element se verifica daca acesta este format doar din cifre de 1 in scrierea binara. Daca da, se incrementeaza contorul curent de secventa. Daca nu, se verifica daca contorul curent este mai mare decat lungimea maxima a secventei gasite pana in acel moment. Daca da, se actualizeaza lungimea maxima a secventei. La final, se returneaza lungimea maxima a secventei gasita.

În interiorul condiției if __name__ == "__main__", se citesc datele de intrare, apoi se apelează funcția validare() pentru a verifica dacă datele de intrare corespund restricțiilor cerinței. Dacă datele corespund restricțiilor, se afișează mesajul "Datele sunt introduse corect." și se apelează funcția rezolvare() pentru a calcula răspunsul problemei. Dacă datele nu corespund restricțiilor, se afișează mesajul "Datele nu corespund restricțiilor impuse.".