0518 - SecvZero

Sursa: 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 gaseste_secventa_maxima(vector):
    lungime_maxima = 0
    pozitie_start = -1
    lungime_curenta = 0

    for i, element in enumerate(vector):
        if element == 0:
            lungime_curenta += 1
        else:
            if lungime_curenta > lungime_maxima:
                lungime_maxima = lungime_curenta
                pozitie_start = i - lungime_maxima
            lungime_curenta = 0

    if lungime_curenta > lungime_maxima:
        lungime_maxima = lungime_curenta
        pozitie_start = len(vector) - lungime_maxima

    return (lungime_maxima, pozitie_start)


# functia main
if __name__ == "__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)

Explicație rezolvare

Funcția validate_input verifică dacă datele introduse de utilizator corespund cerințelor problemei, adică dacă numărul n este în intervalul [1, 1000], toate numerele citite sunt mai mici decât 1000 și vectorul conține cel puțin un element nul. Dacă datele sunt valide, funcția returnează True, altfel returnează False.

Funcția find_longest_sequence_of_zeros primește ca argument vectorul citit și returnează două numere: lungimea celei mai lungi secvențe de elemente nule din vector și poziția de început a acestei secvențe. Pentru a găsi aceste valori, funcția parcurge vectorul și numără lungimea fiecărei secvențe de elemente nule întâlnite. De fiecare dată când găsește o secvență de elemente nule mai lungă decât cea găsită anterior, funcția actualizează lungimea maximă și poziția de început a acestei secvențe.

În main, se citesc datele de intrare de la tastatură, se validează și se apelează funcția find_longest_sequence_of_zeros. Dacă datele introduse sunt valide, se afișează mesajul "Datele sunt introduse corect." și rezultatul returnat de funcția find_longest_sequence_of_zeros. În caz contrar, se afișează mesajul "Datele nu corespund restricțiilor impuse.".