0166 - SecvMax: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
 
Linia 28: Linia 28:
: 5 7
: 5 7


== Exemplu 1 ==
== Exemplu 2 ==
; Intrare
; Intrare
: secvk.in
: secvk.in
Linia 35: Linia 35:
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.
: secvk.out
 
: 2 3 4 5


== Rezolvare ==  
== Rezolvare ==  
Linia 43: Linia 42:
#0166 - SecvMax
#0166 - SecvMax


def secv_max(n, v):
def validate_input(n, v):
     # verificam daca datele de intrare sunt valide
     if n < 1 or n > 100000 or any(x >= 1000 for x in v):
    for x in v:
         return False
         if x >= 1000:
    return True
            print("Datele nu corespund restricțiilor impuse.")
 
            return
def find_longest_even_sequence(n, v):
   
    if not validate_input(n, v):
    # cautam cea mai lunga secventa de elemente pare
        return "Datele nu corespund restricțiilor impuse.", []
 
     start, end, max_len = 0, 0, 0
     start, end, max_len = 0, 0, 0
     for i in range(n):
     for i in range(n):
Linia 59: Linia 59:
             if j - i > max_len:
             if j - i > max_len:
                 start, end, max_len = i, j, j - i
                 start, end, max_len = i, j, j - i
   
 
    # calculam suma elementelor secventei
     max_sum = sum(v[start:end])
     max_sum = sum(v[start:end])
   
    # cautam secventele cu lungime maxima si suma maxima
     for i in range(start, end):
     for i in range(start, end):
         if v[i] % 2 == 0 and sum(v[i:end]) == max_sum:
         if v[i] % 2 == 0 and sum(v[i:end]) == max_sum:
             start = i
             start = i
             break
             break
   
 
    # afisam secventa gasita
     result = []
     print("Datele sunt introduse corect.")
     for i in range(start, end):
     for i in range(start, end):
         if v[i] % 2 == 0:
         if v[i] % 2 == 0:
             print(v[i], end=' ')
             result.append(v[i])
     print()
 
     return "Datele sunt introduse corect.", result


if __name__ == "__main__":
if __name__ == "__main__":
    # citim datele de intrare din fisier
     with open("secvk.in", "r") as f:
     with open("secvk.in", "r") as f:
         n = int(f.readline().strip())
         n = int(f.readline().strip())
Linia 83: Linia 79:
         for line in f:
         for line in f:
             v += list(map(int, line.strip().split()))
             v += list(map(int, line.strip().split()))
      
 
     # apelam functia de rezolvare
     message, result = find_longest_even_sequence(n, v)
     secv_max(n, v)
 
     print(message)
     if message == "Datele sunt introduse corect.":
        with open("secvk.out", "w") as f:
            f.write(" ".join(str(x) for x in result))




</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Funcția secv_max(n, v) primește doi parametri: n - numărul de elemente din vectorul v, iar v - vectorul propriu-zis.
Functia validate_input(n, v) verifica daca datele de intrare sunt valide si intoarce True daca sunt valide si False altfel.
 
Primul for din funcție verifică dacă valorile din vector depășesc limita superioară a intervalului acceptat și, în caz afirmativ, se afișează mesajul "Datele nu corespund restricțiilor impuse." și se returnează din funcție.
 
Apoi, al doilea for găsește cea mai lungă secvență de numere pare din vector și salvează indicele de început (start), indicele de sfârșit (end) și lungimea (max_len) acestei secvențe.
 
Suma elementelor din secvența găsită (max_sum) se calculează prin funcția sum și se caută toate secvențele cu lungime maximă și suma maximă a elementelor.


În final, se afișează secvența găsită și un mesaj care confirmă faptul că datele de intrare sunt corecte.
Functia find_longest_even_sequence(n, v) rezolva problema conform cerintei, si intoarce un tuplu cu un mesaj si secventa gasita, sau cu un mesaj de eroare si o lista vida.


Partea if __name__ == "__main__": servește pentru a citi datele de intrare din fișier și pentru a apela funcția secv_max() cu aceste date.
In functia principala if __name__ == "__main__", se citesc datele de intrare din fisier si se apeleaza functia find_longest_even_sequence(n, v) pentru a rezolva problema. Daca functia intoarce un mesaj de eroare, acesta se afiseaza, altfel secventa gasita se scrie in fisierul de iesire "secvk.out".

Versiunea curentă din 14 mai 2023 20:32

Sursa: 0166 - SecvMax


Cerinţa

Se dau n numere naturale, reprezentând elementele unui vector.

Determinați cea mai lungă secvență de elemente pare din vector. Dacă există mai multe secvențe cu lungime maximă se va determina cea cu suma elementelor maximă. Dacă există mai multe astfel de secvențe se va determina cea mai din stânga.

Date de intrare

Fişierul de intrare secvmax.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 secvk.out va conţine pe prima linie k numere, reprezentând elementele secvenței cerute, 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 1000 și sunt numerotate de la 1

Exemplu 1

Intrare
secvk.in
9
2 6 4 5 8 8 6 3 4
Ieșire
Datele sunt introduse corect.
secvk.out
5 7

Exemplu 2

Intrare
secvk.in
5
1 2 3 4 5
Ieșire
Datele nu corespund restricțiilor impuse.


Rezolvare

Rezolvare ver. 1

#0166 - SecvMax

def validate_input(n, v):
    if n < 1 or n > 100000 or any(x >= 1000 for x in v):
        return False
    return True

def find_longest_even_sequence(n, v):
    if not validate_input(n, v):
        return "Datele nu corespund restricțiilor impuse.", []

    start, end, max_len = 0, 0, 0
    for i in range(n):
        if v[i] % 2 == 0:
            j = i
            while j < n and v[j] % 2 == 0:
                j += 1
            if j - i > max_len:
                start, end, max_len = i, j, j - i

    max_sum = sum(v[start:end])
    for i in range(start, end):
        if v[i] % 2 == 0 and sum(v[i:end]) == max_sum:
            start = i
            break

    result = []
    for i in range(start, end):
        if v[i] % 2 == 0:
            result.append(v[i])

    return "Datele sunt introduse corect.", result

if __name__ == "__main__":
    with open("secvk.in", "r") as f:
        n = int(f.readline().strip())
        v = []
        for line in f:
            v += list(map(int, line.strip().split()))

    message, result = find_longest_even_sequence(n, v)

    print(message)
    if message == "Datele sunt introduse corect.":
        with open("secvk.out", "w") as f:
            f.write(" ".join(str(x) for x in result))

Explicatie Rezolvare

Functia validate_input(n, v) verifica daca datele de intrare sunt valide si intoarce True daca sunt valide si False altfel.

Functia find_longest_even_sequence(n, v) rezolva problema conform cerintei, si intoarce un tuplu cu un mesaj si secventa gasita, sau cu un mesaj de eroare si o lista vida.

In functia principala if __name__ == "__main__", se citesc datele de intrare din fisier si se apeleaza functia find_longest_even_sequence(n, v) pentru a rezolva problema. Daca functia intoarce un mesaj de eroare, acesta se afiseaza, altfel secventa gasita se scrie in fisierul de iesire "secvk.out".