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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi fișierul secv.out conține 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.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0304 - Secvente

def count_maximal_sequences(n, arr):

   sequences = 0
   i = 0
   while i < n:
       j = i + 1
       while j < n and arr[j] > arr[j-1]:
           j += 1
       sequences += j - i
       i = j
   return sequences

def validate_input(n, arr):

   if not 1 <= n <= 1000:
       return False
   for x in arr:
       if not 1 <= x <= 9999:
           return False
   return True

if __name__ == "__main__":

   try:
       with open("secvente.in", "r") as f_in:
           n = int(f_in.readline().strip())
           arr = []
           for _ in range(n):
               arr += list(map(int, f_in.readline().strip().split()))
       if validate_input(n, arr):
           with open("secvente.out", "w") as f_out:
               f_out.write(str(count_maximal_sequences(n, arr)))
               print("Datele sunt introduse corect.")
       else:
           print("Datele nu corespund restricțiilor impuse.")
   except FileNotFoundError:
       print("Nu exista fisierul de intrare!") 

</syntaxhighlight>

Explicatie Rezolvare

Functia count_maximal_sequences() calculeaza numarul de secvente maximale cu elementele ordonate crescator din sirul de intrare. Folosim doua variabile, i si j, pentru a parcurge sirul. Variabila i marcheaza inceputul unei secvente, iar variabila j cauta finalul secventei. Atunci cand gasim finalul secventei, adaugam la numarul de secvente maximale lungimea secventei curente, adica j-i. Apoi setam variabila i la valoarea lui j pentru a cauta urmatoarea secventa.

Functia validate_input() valideaza datele de intrare conform restrictiilor problemei. Returneaza True daca datele sunt corecte si False in caz contrar.

In functia principala if __name__ == "__main__": citim datele de intrare din fisierul secvente.in. Apoi verificam daca datele sunt valide folosind functia validate_input(). Daca datele sunt valide, apelam functia count_maximal_sequences() pentru a calcula numarul de secvente maximale si scriem rezultatul in fisierul secvente.out. Afisam mesajul "Datele sunt introduse corect." daca totul a functionat bine. In caz contrar, afisam mesajul "Datele nu corespund restricțiilor impuse." sau "Nu exista fisierul de intrare!" daca fisierul de intrare nu exista.