0181 - SecvCresc

Sursa: 0181 - SecvCresc

---

Cerinţa

Se dau n numere naturale, reprezentând elementele unui vector. Determinați cea mai lungă secvență de elemente ordonate strict crescător din vector. Dacă există mai multe astfel de secvențe se va determina cea mai din stânga.

Date de intrare

Fișierul de intrare secvcresc.in conține numărul n și n valori naturale, reprezentând elementele vectorului. Valorile din fișier pot fi dispuse pe mai multe linii.

Date de ieșire

 Dacă datele sunt introduse corect, pe ecran se va afișa: 

"Datele sunt introduse corect." și fișierul de ieșire secvcresc.out va conține pe prima linie numerele st și dr, reprezentând indicii de început și de sfârșit ai secvenței determinate, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 0 < n ≤ 10.000
• elementele vectorului vor fi mai mici decât 1.000.000 și sunt numerotate de la 1

Exemplu 1

Intrare

secvcresc.in

9

2 6 4 5 8 9 6 3 4

Ieșire

Datele sunt introduse correct.

secvcresc.out

3 6

Exemplu 2

Intrare

secvcresc.in

5

1000 200 300 400 500

Ieșire

Datele nu corespund restricțiilor impuse.

secvcresc.out

Iar sevcresc.out nu va fi generat deoarece datele nu sunt crescatoare

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0181 - SecvCresc

def lungime_secventa_crescatoare(n, v):

   """Funcția primește un număr n reprezentând numărul de elemente din vectorul v și un vector v de n elemente.
   Returnează indicii secvenței maxime ordonate crescător din vectorul v."""
   st = dr = 0
   max_len = 0
   len_curenta = 1
   for i in range(1, n):
       if v[i] > v[i-1]:
           len_curenta += 1
       else:
           if len_curenta > max_len:
               max_len = len_curenta
               st = i - max_len
               dr = i - 1
           len_curenta = 1
   if len_curenta > max_len:
       max_len = len_curenta
       st = n - max_len
       dr = n - 1
   return st+1, dr+1

if __name__ == '__main__':

   try:
       with open('secvcresc.in', 'r') as f:
           n = int(f.readline())
           v = []
           for _ in range(n):
               v += list(map(int, f.readline().split()))
   except FileNotFoundError:
       print('Datele nu corespund restricțiilor impuse.')
   else:
       if n > 0 and n <= 10000 and all(elem < 1000000 for elem in v):
           st, dr = lungime_secventa_crescatoare(n, v)
           print('Datele sunt introduse corect.')
           with open('secvcresc.out', 'w') as f:
               f.write(str(st) + ' ' + str(dr) + '\n')
       else:
           print('Datele nu corespund restricțiilor impuse.')

</syntaxhighlight>

Explicatie Rezolvare

Funcția lungime_secventa_crescatoare primește un număr n reprezentând numărul de elemente din vectorul v și un vector v de n elemente și returnează indicii secvenței maxime ordonate crescător din vectorul v. În funcția principală if __name__ == '__main__':: Se încearcă deschiderea fișierului de intrare 'secvcresc.in' și citirea datelor din el. Dacă fișierul nu poate fi deschis, se afișează mesajul "Datele nu corespund restricțiilor impuse." Dacă datele sunt corect introduse (numărul de elemente n este între 1 și 10000 și toate elementele vectorului v sunt mai mici decât 1000000), se calculează indicii secvenței maxime ordonate crescător și se afișează mesajul "Datele sunt introduse corect.". Dacă datele nu corespund restricțiilor impuse, se afișează mesajul "Datele nu corespund restricțiilor impuse.". Indicii secvenței maxime ordonate crescător sunt scriși în fișierul de ieșire 'secvcresc.out'.