0181 - SecvCresc: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
Linia 9: Linia 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 ==
Linia 19: Linia 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


Linia 26: Linia 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.".

Versiunea de la data 27 aprilie 2023 18:29

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

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

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

Adus de la „http://wiki.universitas.ro/index.php?title=0181_-_SecvCresc&oldid=5052”