Editing 0299 - SumeSecv

Sursa: [https://www.pbinfo.ro/probleme/299/sumesecv - SumeSecv]
----
== Cerinţa ==
Se dă un vector cu n elemente numere naturale, numerotate de la 1 la n, și m perechi de indici (i,j), cu 1≤i<j≤n. Să se determine, pentru fiecare pereche (i,j), suma elementelor din secvenţa determinată de i şi j.

== Date de intrare ==
Fişierul de intrare sumesecv.in conţine pe prima linie numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j.

== Date de ieșire == 
Fişierul de ieşire sumesecv.out va conţine pe prima linie cele m sume determinate, separate prin câte un spațiu.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 100
* elementele vectorului vor fi mai mici decât 1000
* 1 ≤ m ≤ 100
== Exemplu ==
; Intrare
: 10
: 5 5 1 3 6 4 1 2 10 6 
: 3
: 5 8 
: 2 6 
: 6 10 
; Ieșire
: 13 19 23 

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 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)

</syntaxhighlight>

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