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.

9

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0981 - secventa11

def is_binary_string(num):

   """Verifică dacă un număr dat în baza 10 poate fi scris în baza 2 doar cu cifrele 1."""
   binary_str = bin(num)[2:]  # conversia în binar elimină prefixul "0b"
   return set(binary_str) == {'1'}

def max_length_of_ones_sequence(numbers):

   """Determină lungimea maximă a unei secvențe de numere din șir cu proprietatea că în scrierea binară
   sunt formate doar din cifre de 1."""
   max_len = 0
   cur_len = 0

   for num in numbers:
       if is_binary_string(num):
           cur_len += 1
           max_len = max(max_len, cur_len)
       else:
           cur_len = 0

   return max_len

def main():

   n = int(input())
   vector = input().split()

   # validare date de intrare
   if n <= 0 or n > 1000 or len(vector) != n:
       print("Datele nu corespund restricțiilor impuse.")
   else:
       try:
           vector = [int(elem) for elem in vector]
       except ValueError:
           print("Datele nu corespund restricțiilor impuse.")
           exit(0)

       if max(vector) >= 1000:
           print("Datele nu corespund restricțiilor impuse.")
       else:
           lungime_maxima, pozitie_start = gaseste_secventa_maxima(vector)
           print("Datele sunt introduse corect.")
           print(lungime_maxima, pozitie_start)

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicatie Rezolvare

Funcția is_binary_string primește un număr natural num și returnează True dacă reprezentarea binară a acestuia conține doar cifra 1, False în caz contrar. Funcția max_length_of_ones_sequence primește o listă de numere naturale și returnează lungimea maximă a unei secvențe de numere din această listă cu proprietatea că reprezentarea binară a fiecărui număr este formată doar din cifra 1. Algoritmul este implementat astfel: se parcurg numerele din listă și se ține evidența lungimii secvenței curente de numere cu proprietatea dată. Dacă numărul curent respectă proprietatea, lungimea secvenței curente se mărește cu 1 și se actualizează lungimea maximă găsită până în acel moment. În caz contrar, secvența curentă se întrerupe. Funcția main citește datele de intrare și validează restricțiile impuse de problemă. Dacă datele sunt introduse corect, se apelează funcția max_length_of_ones_sequence și se afișează rezultatul. Functia def main() este incapsulata in functia if __name__ == "__main__ pentru că funcția gaseste_secventa_maxima nu este definită și nici nu poate fi definită în acest mod. Prin urmare, funcția main() trebuie păstrată.