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

Datele sunt introduse correct.

secvente.out

3

Exemplu 2

Intrare

secvente.in

...

10 12 14

Ieșire

Datele nu corespund restricțiilor impuse.

secvente.out

Datele sunt introduse incorrect

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0304 - Secvente

def count_increasing_sequences(n, a):

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

if __name__ == "__main__":

   try:
       with open("secvente.in", "r") as f:
           n = int(f.readline())
           a = []
           for line in f:
               a += list(map(int, line.strip().split()))
           if len(a) != n:
               print("Datele nu corespund restricțiilor impuse.")
           else:
               print("Datele sunt introduse corect.")
               with open("secvente.out", "w") as g:
                   g.write(str(count_increasing_sequences(n, a)))
   except FileNotFoundError:
       print("Fisierul secvente.in nu exista.") 

</syntaxhighlight>

Explicatie Rezolvare

Functia def count_increasing_sequences primeste 2 parametri:

n: reprezintă numărul de elemente din lista a a: lista de n elemente Funcția utilizează o metodă iterativă pentru a număra secvențele maximale în care elementele sunt ordonate crescător. Aceasta lucrează astfel:

Inițializăm o variabilă cnt cu 0. Parcurgem lista a utilizând un iterator i în intervalul [0, n-1] Inițializăm un alt iterator j cu valoarea lui i Utilizând un ciclu while verificăm dacă următorul element din lista a (a[j+1]) este mai mare decât elementul curent (a[j]). Dacă da, incrementăm iteratorul j și continuăm să verificăm dacă elementele sunt în ordine crescătoare. Dacă j este mai mare decât i, adăugăm 1 la valoarea lui cnt. Acest lucru se face deoarece avem o secvență maximă crescătoare în această secvență, începând de la poziția i și terminând la poziția j. La final, funcția returnează valoarea lui cnt, care reprezintă numărul de secvențe maximale crescătoare găsite în lista a.

În ceea ce privește blocul if __name__ == "__main__":, acesta verifică dacă fișierul de intrare există și, dacă da, citesc datele din fișierul de intrare secvente.in și le pasează la funcția count_increasing_sequences(). Funcția apoi scrie rezultatul în fișierul de ieșire secvente.out, împreună cu un mesaj corespunzător în cazul în care datele sunt sau nu sunt introduse corect.