0981 - secventa11: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
 
(Nu s-au afișat 2 versiuni intermediare efectuate de același utilizator)
Linia 7: Linia 7:
== Date de ieșire ==  
== Date de ieșire ==  
Dacă datele sunt introduse corect, pe ecran se va afișa:  
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."'''.
'''"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 ==
== Restricţii şi precizări ==
* 1 ≤ n ≤ 300.000
* 1 ≤ n ≤ 300.000
* cele n numere citite vor fi mai mici decât 1.000.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
* dacă în șir nu sunt numere formate numai din cifre de 1 în baza 2, se va afișa 0
== Exemplu ==
== Exemplu 1 ==
; Intrare
; Intrare
: 5
: 5
: 4 6 7 15 88
: 4 6 7 15 88
; Ieșire
: Datele sunt introduse correct.
: 2
== Exemplu 2 ==
; Intrare
: 1
: 2 4 13 25
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.
: 2
 


== Rezolvare ==  
== Rezolvare ==  
Linia 25: Linia 33:
# 0981 - secventa11
# 0981 - secventa11


def read_input():
def validate_input(n, lst):
    try:
     for i in range(n):
        n = int(input("Introduceți numărul de numere din lista: "))
         if lst[i] < 0 or lst[i] > 1000000:
        numbers = list(map(int, input("Introduceți numerele din lista, separate prin spațiu: ").split()))
        if not validate_input(numbers):
            print("Datele introduse nu respectă restricțiile impuse.")
            return None
        return numbers
     except ValueError:
        print("Datele introduse nu respectă formatul așteptat.")
        return None
 
def validate_input(numbers):
    for num in numbers:
         if num < 0 or num > 10**9:
             return False
             return False
     return True
     return True


def find_longest_binary_ones(numbers):
def get_max_ones(n, lst):
     max_len = 0
     if not validate_input(n, lst):
     current_len = 0
        print("Datele nu corespund restricțiilor impuse.")
     for num in numbers:
        return 0
         binary_num = bin(num)[2:]
    max_ones = 0
         if all(digit == '1' for digit in binary_num):
     current_ones = 0
             current_len += 1
     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:
         else:
             max_len = max(max_len, current_len)
             if current_ones > max_ones:
             current_len = 0
                max_ones = current_ones
     max_len = max(max_len, current_len)
             current_ones = 0
     return max_len
     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


def validate_output(result):
if __name__ == "__main__":
     if result >= 1:
    n = int(input())
        print(result)
     lst = list(map(int, input().split()))
     else:
     print(get_max_ones(n, lst))
        print(0)


if __name__ == '__main__':
    numbers = read_input()
    if numbers is not None:
        result = find_longest_binary_ones(numbers)
        validate_output(result)


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==


Funcția read_input() citește numerele de la tastatură și le returnează sub forma unei liste de întregi.
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`.
Am adăugat o funcție de validare a intrării validate_input pentru a verifica dacă fiecare număr din listă este între 0 și 10^9. Am schimbat funcția read_input pentru a folosi această funcție de validare și pentru a afișa un mesaj adecvat în cazul în care datele introduse nu sunt valide sau nu respectă restricțiile impuse.
 
Funcția find_longest_binary_ones(numbers) primește lista de numere și calculează lungimea celei mai lungi secvențe de numere din șir cu proprietatea că în scrierea binară sunt formate doar din cifre de 1. Pentru fiecare număr din listă, se transformă în baza 2 și se verifică dacă toate cifrele sunt 1. Dacă da, se adaugă la lungimea curentă a secvenței, altfel se compară lungimea curentă cu lungimea maximă și se resetează lungimea curentă. La final, se mai compară o dată lungimea curentă cu lungimea maximă și se returnează lungimea maximă.


Funcția validate_output(result) primește rezultatul și îl validează. Dacă rezultatul este mai mare sau egal cu 1, se afișează pe ecran. Altfel, se afișează 0.
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 if __name__ == '__main__':, citim datele de intrare, apoi apelăm funcția find_longest_binary_ones() și validăm rezultatul apelând funcția validate_output().
Î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.".

Versiunea curentă din 14 mai 2023 19:40

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

# 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))

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