0181 - SecvCresc: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 9: Line 9:


== Date de ieșire ==  
== Date de ieșire ==  
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.
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 '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.
 


== Restricţii şi precizări ==
== Restricţii şi precizări ==
Line 19: Line 21:
: 2 6 4 5 8 9 6 3 4
: 2 6 4 5 8 9 6 3 4
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: 3 6
: 3 6


Line 26: Line 29:
# 0181 - SecvCresc
# 0181 - SecvCresc


def citire():
def citire_date():
     with open("secvcresc.in", "r") as f:
     n = int(input())
        n = int(f.readline())
    v = []
        v = []
    for i in range(n):
        for line in f:
        v.extend(map(int, input().split()))
            v += list(map(int, line.split()))
     return n, v
     return n, v


def rezolvare(n, v):
def secv_cresc(n, v):
     max_length = 1
     st_max = dr_max = 0
     max_start = max_end = start = end = 0
     l_max = 1
     length = 1
     l_crt = 1
     for i in range(1, n):
     for i in range(1, n):
         if v[i] > v[i - 1]:
         if v[i] > v[i-1]:
             length += 1
             l_crt += 1
            end = i
         else:
         else:
             if length > max_length:
             if l_crt > l_max:
                 max_length = length
                 l_max = l_crt
                 max_start, max_end = start, end
                 st_max = i - l_max
            length = 1
                dr_max = i - 1
             start = end = i
             l_crt = 1
     if length > max_length:
     if l_crt > l_max:
         max_length = length
         l_max = l_crt
         max_start, max_end = start, end
        st_max = n - l_max
     return max_start + 1, max_end + 1
         dr_max = n - 1
     return l_max, st_max + 1, dr_max + 1


def validare(n, v, start, end):
def validare(n, v):
     for i in range(start - 1, end - 1):
    if len(v) != n:
         if v[i] >= v[i + 1]:
        return False
     for x in v:
         if x < 1 or x >= 1000000:
             return False
             return False
     return True
     return True


if __name__ == "__main__":
if __name__ == '__main__':
     n, v = citire()
     n, v = citire_date()
     start, end = rezolvare(n, v)
     if validare(n, v):
    with open("secvcresc.out", "w") as f:
        print("Datele sunt introduse corect.")
         f.write(f"{start} {end}\n")
         l, st, dr = secv_cresc(n, v)
    if validare(n, v, start, end):
         print(l)
         print("Rezultat corect!")
     else:
     else:
         print("Rezultat incorect!")
         print("Datele nu corespund restricțiilor impuse.")


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Pentru a rezolva această problemă, putem parcurge vectorul și ține în variabila lungime lungimea secvenței curente. De asemenea, putem ține și variabilele start și end care reprezintă indicele de început și sfârșit al secvenței curente. Dacă găsim o valoare mai mare decât precedenta, atunci lungimea secvenței crește și actualizăm end cu indicele curent. Dacă găsim o valoare mai mică sau egală cu precedenta, atunci secvența curentă se termină și verificăm dacă este mai lungă decât cea maximă găsită până acum. Dacă da, actualizăm variabilele max_start, max_end și max_length
 
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.".

Revision as of 18:29, 27 April 2023

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

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 numărul c, 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

Intrare
9
2 6 4 5 8 9 6 3 4
Ieșire
Datele nu corespund restricțiilor impuse.
3 6

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

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