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:

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 numărul de secvenţe cu elementele ordonate crescător din şirul dat, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

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 1

Intrare

secvente.in

8

12 10 15 17 17

10 12 14

Ieșire

secvente.out

Datele sunt introduse correct.

3

Exemplu 2

Intrare

secvente.in

8

12 10 15 17 17

10 12 14

Ieșire

secvente.out

Datele nu corespund restricțiilor impuse.

9

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0304 - Secvente

def citire_date():

   n = int(input())
   v = list(map(int, input().split()))
   return n, v

def secvente_crescatoare(n, v):

   numar_secvente = 0
   for i in range(n):
       j = i + 1
       while j < n and v[j] > v[j-1]:
           j += 1
       numar_secvente += j - i
       i = j - 1
   return numar_secvente

def validare(n, v):

   if len(v) != n:
       return False
   for x in v:
       if x < 0 or x > 9999:
           return False
   return True

if __name__ == '__main__':

   n, v = citire_date()
   if validare(n, v):
       print("Datele sunt introduse corect.")
       print(secvente_crescatoare(n, v))
   else:
       print("Datele nu corespund restricțiilor impuse.")

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