0959 - secmax

Sursa: 0959 - secmax

---

Cerinţa

Scrieți un program care citește numărul N, cele N cifre ale numărului X și care determină numărul total de secvenţe-maxim din numărul X.

Date de intrare

Fișierul de intrare secmax.in conține pe prima linie numărul natural N. Pe următoarea linie se află o succesiune de N cifre X1X2...XN, reprezentând cifrele numărului X.

Date de ieșire

Fișierul de ieșire secmax.out va conține pe prima linie un număr natural, reprezentând numărul total de secvenţe-maxim din numărul X.

Restricţii şi precizări

• 8 ≤ N ≤ 25000
• 0 ≤ X1, X2 , ..., XN ≤ 9
• X1 ≠ 0
• o secvență-maxim este formată din cel puțin trei cifre

Exemplu

Intrare

8

12543644

Ieșire

5

Rezolvare

Rezolvare ver. 1

# 0959 - secmax

def citire():
    with open("secmax.in", "r") as f:
        n = int(f.readline())
        x = list(map(int, f.readline().split()))
    return n, x

def secventa_maxim(x):
    n = len(x)
    cnt = 0
    i = 0
    while i < n-1:
        j = i+1
        while j < n and x[j] < x[j-1]:
            j += 1
        k = j
        while k < n and x[k] > x[k-1]:
            k += 1
        cnt += (k-j)
        i = k-1
    return cnt

def validare(cnt):
    assert cnt >= 0, "Numarul de secvente maxim nu poate fi negativ!"

if __name__ == "__main__":
    n, x = citire()
    cnt = secventa_maxim(x)
    validare(cnt)
    with open("secmax.out", "w") as f:
        f.write(str(cnt))

Explicatie Rezolvare

Funcția citire citește datele de intrare din fișierul "secmax.in" și le returnează sub formă de tuplu (n, x), unde n este lungimea numărului x și x este o listă de n cifre reprezentând numărul dat.

Funcția secventa_maxim calculează numărul total de secvențe-maxim din numărul dat x, folosind o metodă iterativă de explorare a secvențelor. Se pleacă de la prima cifră și se caută o secvență descrescătoare continuă, apoi o secvență crescătoare continuă. Aceste două secvențe formează o secvență-maxim. Se adaugă numărul de elemente din secvența crescătoare la un contor cnt și se continuă explorarea de la finalul secvenței crescătoare. Se repetă până la parcurgerea întregului număr.

Funcția validare verifică dacă numărul de secvențe-maxim calculat este un număr pozitiv sau zero.

În blocul if __name__ == "__main__": se apelează funcțiile citire, secventa_maxim și validare, se scrie rezultatul în fișierul "secmax.out" și se afișează un mesaj de confirmare a terminării programului.