0166 - SecvMax: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 24: Line 24:
: 2 6 4 5 8 8 6 3 4
: 2 6 4 5 8 8 6 3 4
; Ieșire
; Ieșire
: Datele sunt introduse corect.
: secvk.out
: secvk.out
: Datele sunt introduse corect.
: 5 7
: 5 7


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


Line 43: Line 43:
#0166 - SecvMax
#0166 - SecvMax


def citire_date():
def secv_max(n, v):
     n = int(input())
     # verificam daca datele de intrare sunt valide
     v = list(map(int, input().split()))
     for x in v:
    return n, v
        if x >= 1000:
 
            print("Datele nu corespund restricțiilor impuse.")
def secvmax(n, v):
            return
     st = dr = st_max = dr_max = suma_max = suma = 0
   
    # cautam cea mai lunga secventa de elemente pare
     start, end, max_len = 0, 0, 0
     for i in range(n):
     for i in range(n):
         if v[i] % 2 == 0:
         if v[i] % 2 == 0:
             suma += v[i]
             j = i
             dr = i
            while j < n and v[j] % 2 == 0:
            if suma > suma_max or (suma == suma_max and dr - st > dr_max - st_max):
                j += 1
                suma_max = suma
             if j - i > max_len:
                st_max = st
                start, end, max_len = i, j, j - i
                dr_max = dr
   
        else:
    # calculam suma elementelor secventei
            suma = 0
    max_sum = sum(v[start:end])
             st = i + 1
   
     return st_max + 1, dr_max + 1
    # cautam secventele cu lungime maxima si suma maxima
    for i in range(start, end):
        if v[i] % 2 == 0 and sum(v[i:end]) == max_sum:
            start = i
            break
   
    # afisam secventa gasita
    print("Datele sunt introduse corect.")
    for i in range(start, end):
        if v[i] % 2 == 0:
             print(v[i], end=' ')
     print()


def validare(n, v):
if __name__ == "__main__":
     if len(v) != n:
     # citim datele de intrare din fisier
         print("Datele nu corespund restricțiilor impuse.")
    with open("secvk.in", "r") as f:
         return False
         n = int(f.readline().strip())
    for x in v:
         v = []
        if x < 0 or x > 1000:
        for line in f:
             print("Datele nu corespund restricțiilor impuse.")
             v += list(map(int, line.strip().split()))
            return False
   
     print("Datele sunt introduse corect.")
    # apelam functia de rezolvare
    return True
     secv_max(n, v)


if __name__ == '__main__':
    n, v = citire_date()
    if validare(n, v):
        st, dr = secvmax(n, v)
        print(st, dr, sep="\n")


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Funcția citire_date primește de la tastatură numărul de elemente ale vectorului și apoi vectorul propriu-zis, pe care îl returnează sub formă de tuplu.
Funcția secv_max(n, v) primește doi parametri: n - numărul de elemente din vectorul v, iar v - vectorul propriu-zis.
 
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.


Funcția secvmax primește ca argumente numărul de elemente ale vectorului și vectorul și calculează cea mai lungă secvență de elemente pare din vector, folosind variabilele st și dr pentru a păstra indicii de început și de sfârșit ai secvenței curente și variabilele st_max și dr_max pentru a păstra indicii de început și de sfârșit ai secvenței cu suma maximă și variabila suma pentru a păstra suma elementelor din secvența curentă și variabila suma_max pentru a păstra suma elementelor din secvența cu suma maximă.
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.


Funcția validare primește ca argumente numărul de elemente ale vectorului și vectorul și verifică dacă datele de intrare respectă condițiile impuse de cerință.
În final, se afișează secvența găsită și un mesaj care confirmă faptul că datele de intrare sunt corecte.


În funcția main, se citește datele de intrare, se validează și se afișează rezultatul dacă datele de intrare sunt valide, sau un mesaj de eroare altfel.
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.

Revision as of 21:49, 13 May 2023

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

Fişierul de ieşire secvmax.out va conţine: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou 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 1

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

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0166 - SecvMax

def secv_max(n, v):

   # verificam daca datele de intrare sunt valide
   for x in v:
       if x >= 1000:
           print("Datele nu corespund restricțiilor impuse.")
           return
   
   # cautam cea mai lunga secventa de elemente pare
   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
   
   # calculam suma elementelor secventei
   max_sum = sum(v[start:end])
   
   # cautam secventele cu lungime maxima si suma maxima
   for i in range(start, end):
       if v[i] % 2 == 0 and sum(v[i:end]) == max_sum:
           start = i
           break
   
   # afisam secventa gasita
   print("Datele sunt introduse corect.")
   for i in range(start, end):
       if v[i] % 2 == 0:
           print(v[i], end=' ')
   print()

if __name__ == "__main__":

   # citim datele de intrare din fisier
   with open("secvk.in", "r") as f:
       n = int(f.readline().strip())
       v = []
       for line in f:
           v += list(map(int, line.strip().split()))
   
   # apelam functia de rezolvare
   secv_max(n, v)


</syntaxhighlight>

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.

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.

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.