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: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul c, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

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: Datele nu corespund restricțiilor impuse.; Datele sunt introduse correct.; 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)
   with open("secmax.out", "w") as f:
       f.write(str(cnt))
   try:
       validare(cnt)
       print("Datele sunt introduse corect.")
   except AssertionError as e:
       print("Datele nu corespund restricțiilor impuse.")
       print(e)

</syntaxhighlight>

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.