0304 - Secvente

Sursa: 0304 - Secvente

---

Cerinţa

Se dă un şir format din n elemente, numere naturale. Determinaţi câte secvenţe maximale cu elementele ordonate crescător conţine şirul.

Date de intrare

Fişierul de intrare secvente.in conţine pe prima linie numărul n; urmează cele n elemente ale vectorului, dispuse pe mai multe linii şi separate prin spaţii.

Date de ieșire

Fişierul de ieşire secvente.out va conţine pe prima linie numărul C, reprezentând numărul de secvenţe cu elementele ordonate crescător din şirul dat.

Restricţii şi precizări

• 1 ≤ n ≤ 1000
• elementele şirului vor avea cel mult 4 cifre
• o secvență cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător

Exemplu

Intrare

8:

12 10 15 17 17

10 12 14

Ieșire

3

Rezolvare

Rezolvare ver. 1

# 0304 - Secvente

def citeste_date_intrare():
    n = int(input())
    sir = []
    for i in range(n):
        sir.append(int(input()))
    return sir

def numara_secvente_crescatoare(sir):
    numar_secvente = 0
    lungime_maxima = 1
    lungime_curenta = 1
    for i in range(1, len(sir)):
        if sir[i] >= sir[i-1]:
            lungime_curenta += 1
        else:
            if lungime_curenta > lungime_maxima:
                lungime_maxima = lungime_curenta
                numar_secvente = 1
            elif lungime_curenta == lungime_maxima:
                numar_secvente += 1
            lungime_curenta = 1
    if lungime_curenta > lungime_maxima:
        lungime_maxima = lungime_curenta
        numar_secvente = 1
    elif lungime_curenta == lungime_maxima:
        numar_secvente += 1
    return numar_secvente

def valideaza(sir, numar_secvente):
    assert len(sir) > 0
    assert numar_secvente >= 0

if __name__ == "__main__":
    sir = citeste_date_intrare()
    numar_secvente = numara_secvente_crescatoare(sir)
    valideaza(sir, numar_secvente)
    print(numar_secvente)

Explicatie Rezolvare

Funcția citeste_date_intrare primește datele de intrare de la tastatură și le returnează sub forma unei liste.

Funcția numara_secvente_crescatoare primește lista de numere și numără secvențele maximale cu elemente ordonate crescător din șirul dat. Algoritmul este simplu: parcurgem lista și ținem minte lungimea maximă a unei secvențe cu elemente ordonate crescător și numărul de astfel de secvențe găsite până în acel moment. Când întâlnim un element mai mic decât cel precedent, înseamnă că secvența curentă s-a încheiat, verificăm dacă are lungimea maximă și actualizăm numărul de secvențe dacă e cazul. La final mai facem o verificare dacă ultima secvență a fost maximă.

Funcția valideaza verifică dacă datele de ieșire sunt valide.

În blocul if __name__ == "__main__": citim datele de intrare, apelăm funcția numara_secvente_crescatoare și afișăm rezultatul.