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

Programul va afișa pe ecran indicii st dr ai capetelor secvenței determinate, separați printr-un spațiu.

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

Intrare

10

0 1 0 0 0 5 0 0 0 2

Ieșire

3 5

Rezolvare

Rezolvare ver. 1

# 0518 - SecvZero

def validate_input(n, v):
    if n < 1 or n > 1000:
        print("n nu respecta restrictiile impuse")
        return False
    for i in range(n):
        if v[i] >= 1000:
            print("elementul", i+1, "nu respecta restrictiile impuse")
            return False
    if all(elem != 0 for elem in v):
        print("vectorul nu contine elemente nule")
        return False
    return True

def find_longest_sequence(n, v):
    max_len = 0
    start = 0
    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
            i = j
    return (start+1, start+max_len)

def read_input():
    n = int(input())
    v = list(map(int, input().split()))
    if not validate_input(n, v):
        exit()
    return n, v

if __name__ == '__main__':
    n, v = read_input()
    start, end = find_longest_sequence(n, v)
    print(start, end)

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().