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

Fișierul de ieșire secvcresc.out: Dacă datele sunt introduse corect, pe ecran se va afișa: '"Datele sunt introduse corect.", apoi pe un rând nou 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: secvcresc.out; Datele sunt introduse correct.; 3 6

Exemplu 2

Intrare: secvcresc.in; 9; 2 6 4 5 8 9 6 3 4
Ieșire: secvcresc.out; Datele nu corespund restricțiilor impuse.; 2 4 5

Rezolvare

Rezolvare ver. 1

0181 - SecvCresc

def citire_date():

   n = int(input())
   v = []
   for i in range(n):
       v.extend(map(int, input().split()))
   return n, v

def secv_cresc(n, v):

   st_max = dr_max = 0
   l_max = 1
   l_crt = 1
   for i in range(1, n):
       if v[i] > v[i-1]:
           l_crt += 1
       else:
           if l_crt > l_max:
               l_max = l_crt
               st_max = i - l_max
               dr_max = i - 1
           l_crt = 1
   if l_crt > l_max:
       l_max = l_crt
       st_max = n - l_max
       dr_max = n - 1
   return l_max, st_max + 1, dr_max + 1

def validare(n, v):

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

if __name__ == '__main__':

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

</syntaxhighlight>

Explicatie Rezolvare

Funcția citire_date() citește valorile din fișier și le salvează într-un vector, iar secv_cresc() găsește cea mai lungă secvență crescătoare din acest vector și returnează lungimea acesteia și pozițiile de început și de sfârșit. Funcția validare() verifică dacă datele de intrare sunt corecte (conform restricțiilor din enunț).

În cadrul funcției secv_cresc() se parcurge vectorul și se verifică dacă fiecare element este mai mare decât elementul precedent. Dacă acesta este cazul, lungimea secvenței curente crește cu 1. Dacă se întâlnește un element care nu este mai mare decât precedentul, se verifică dacă lungimea secvenței curente este mai mare decât lungimea maximă până în acest moment și se actualizează variabilele corespunzătoare.

La final, se verifică dacă ultima secvență de elemente este mai lungă decât cea maximă găsită până acum și se actualizează variabilele corespunzătoare.

Programul afișează "Datele sunt introduse corect." și lungimea celei mai lungi secvențe crescătoare dacă datele de intrare sunt corecte. În caz contrar, se afișează "Datele nu corespund restricțiilor impuse.".