0134 - SecvK: Difference between revisions

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


== Date de ieșire ==  
== Date de ieșire ==  
Fişierul de ieşire secvk.out va conţine pe prima linie k numere, reprezentând elementele secvenței cerute.
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 21: Line 22:
: 5 6 1 2 6 6 4 3
: 5 6 1 2 6 6 4 3
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: 6 6 4
: 6 6 4


Line 31: Line 33:
def citire():
def citire():
     n, k = map(int, input().split())
     n, k = map(int, input().split())
     lst = list(map(int, input().split()))
     sir = list(map(int, input().split()))
     return n, k, lst
     return n, k, sir


def secventa_maxima(n, k, lst):
def rezolvare(n, k, sir):
     suma_maxima = 0
     if k > n:
     secventa_maxima = []
        return None  # Daca k > n, secventa de lungime k nu poate fi formata
     for i in range(n-k+1):
    start = 0 # Primul index al secventei curente
         suma = sum(lst[i:i+k])
     suma_curenta = sum(sir[:k])  # Suma elementelor primei secvente
         if suma > suma_maxima:
    suma_maxima = suma_curenta  # Suma maxima gasita pana acum
             suma_maxima = suma
     for i in range(k, n):
            secventa_maxima = lst[i:i+k]
         suma_curenta += sir[i] - sir[start]  # Adaugam un nou element si eliminam cel mai vechi
     return secventa_maxima
        start += 1  # Mutam indexul de inceput al secventei curente
         if suma_curenta > suma_maxima:
             suma_maxima = suma_curenta
     return suma_maxima


def validare(n, k, lst, secventa):
def afisare(suma_maxima):
     assert len(secventa) == k, "Lungimea secventei nu este k"
     if suma_maxima is None:
    assert sum(secventa) == max(sum(lst[i:i+k]) for i in range(n-k+1)), "Suma secventei nu este maxima"
        print("Datele nu corespund restricțiilor impuse.")
     for x in secventa:
     else:
         assert x in lst, "Elementul {} nu se afla in lista initiala".format(x)
         print("Datele sunt introduse corect.")
 
        print(suma_maxima)
if __name__ == "__main__":
    n, k, lst = citire()
    secventa = secventa_maxima(n, k, lst)
    validare(n, k, lst, secventa)
    print(*secventa)


if __name__ == '__main__':
    # Teste
    n, k, sir = citire()
    suma_maxima = rezolvare(n, k, sir)
    afisare(suma_maxima)




</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Funcția citire citește datele de intrare și le returnează sub forma unei tuple (n, k, lst).
Funcția citire() primește datele de intrare de la tastatură și returnează cele trei variabile n, k și sir.
Funcția secventa_maxima calculează secvența de lungime k cu suma maximă din lista lst, utilizând o buclă for și metoda sum. Variabilele suma_maxima și secventa_maxima memorează suma și secvența maximă întâlnită până acum.
Funcția rezolvare(n, k, sir) primește cele trei variabile și calculează suma maximă pentru o secvență de lungime k. Mai întâi verificăm dacă k este mai mare decât n. Dacă da, atunci secvența de lungime k nu poate fi formată, deci returnăm None. Altfel, calculăm suma primelor k elemente și o setăm ca fiind suma maximă găsită până acum. Apoi, parcurgem lista sir de la indexul k până la n-1. La fiecare iterație adăugăm un nou element la secvență și eliminăm cel mai vechi element. Indexul de început al secvenței curente este mutat la dreapta, astfel încât secvența să aibă lungimea k. Dacă suma curentă este mai mare decât suma maximă găsită până acum, o actualizăm. La final, returnăm suma maximă găsită.
Funcția validare verifică corectitudinea secvenței calculate de secventa_maxima în raport cu datele de intrare. Funcția verifică lungimea secvenței, suma elementelor și faptul că fiecare element se află în lista inițială. Dacă validarea eșuează, funcția generează o excepție cu un mesaj corespunzător.
Funcția afisare(suma_maxima) primește suma maximă și afișează un mesaj corespunzător, în funcție de faptul că datele de intrare sunt corecte sau nu. Dacă sunt corecte, atunci afișează suma maximă găsită. Dacă nu sunt corecte, atunci afișează un mesaj de eroare.
În if __name__ == "__main__", apelăm funcțiile citire, secventa_maxima și validare, și apoi afișăm secvența maximă utilizând print(*secventa) (acest lucru afișează elementele secvenței separate prin spații, fără paranteze sau alte simboluri).

Revision as of 18:24, 27 April 2023

Sursa: 0134 - SecvK


Cerinţa

Se dă un șir cu n numere naturale și un număr k. Să se determine o secvență de elemente de lungime k cu suma elementelor maximă.


Date de intrare

Fişierul de intrare secvk.in conţine pe prima linie numerele n și k, iar pe a doua linie n numere naturale separate prin spaţii.

Date de ieșire

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

  • 1 ≤ k ≤ n ≤ 100.000
  • numerele de pe a doua linie a fişierului de intrare vor fi mai mici decât 1000
  • dacă există mai multe secvențe de lungime k cu suma maximă se va afișa prima

Exemplu

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


Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0134 - SecvK

def citire():

   n, k = map(int, input().split())
   sir = list(map(int, input().split()))
   return n, k, sir

def rezolvare(n, k, sir):

   if k > n:
       return None  # Daca k > n, secventa de lungime k nu poate fi formata
   start = 0  # Primul index al secventei curente
   suma_curenta = sum(sir[:k])  # Suma elementelor primei secvente
   suma_maxima = suma_curenta  # Suma maxima gasita pana acum
   for i in range(k, n):
       suma_curenta += sir[i] - sir[start]  # Adaugam un nou element si eliminam cel mai vechi
       start += 1  # Mutam indexul de inceput al secventei curente
       if suma_curenta > suma_maxima:
           suma_maxima = suma_curenta
   return suma_maxima

def afisare(suma_maxima):

   if suma_maxima is None:
       print("Datele nu corespund restricțiilor impuse.")
   else:
       print("Datele sunt introduse corect.")
       print(suma_maxima)

if __name__ == '__main__':

   # Teste
   n, k, sir = citire()
   suma_maxima = rezolvare(n, k, sir)
   afisare(suma_maxima)


</syntaxhighlight>

Explicatie Rezolvare

Funcția citire() primește datele de intrare de la tastatură și returnează cele trei variabile n, k și sir. Funcția rezolvare(n, k, sir) primește cele trei variabile și calculează suma maximă pentru o secvență de lungime k. Mai întâi verificăm dacă k este mai mare decât n. Dacă da, atunci secvența de lungime k nu poate fi formată, deci returnăm None. Altfel, calculăm suma primelor k elemente și o setăm ca fiind suma maximă găsită până acum. Apoi, parcurgem lista sir de la indexul k până la n-1. La fiecare iterație adăugăm un nou element la secvență și eliminăm cel mai vechi element. Indexul de început al secvenței curente este mutat la dreapta, astfel încât secvența să aibă lungimea k. Dacă suma curentă este mai mare decât suma maximă găsită până acum, o actualizăm. La final, returnăm suma maximă găsită. Funcția afisare(suma_maxima) primește suma maximă și afișează un mesaj corespunzător, în funcție de faptul că datele de intrare sunt corecte sau nu. Dacă sunt corecte, atunci afișează suma maximă găsită. Dacă nu sunt corecte, atunci afișează un mesaj de eroare.