0134 - SecvK: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/134/secvk 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 == Fişierul de ieşire secvk.out va conţine pe prima linie k numere, reprezentâ...
 
Flaviu (talk | contribs)
No edit summary
Line 29: Line 29:
# 0134 - SecvK
# 0134 - SecvK


# citim valorile de n și k
def citire():
n, k = map(int, input().split())
    n, k = map(int, input().split())
    lst = list(map(int, input().split()))
    return n, k, lst


# citim șirul de numere
def secventa_maxima(n, k, lst):
a = list(map(int, input().split()))
    suma_maxima = 0
    secventa_maxima = []
    for i in range(n-k+1):
        suma = sum(lst[i:i+k])
        if suma > suma_maxima:
            suma_maxima = suma
            secventa_maxima = lst[i:i+k]
    return secventa_maxima


# calculăm suma primelor k elemente și o considerăm inițial ca fiind suma maximă
def validare(n, k, lst, secventa):
max_sum = sum(a[:k])
    assert len(secventa) == k, "Lungimea secventei nu este k"
max_seq = a[:k]
    assert sum(secventa) == max(sum(lst[i:i+k]) for i in range(n-k+1)), "Suma secventei nu este maxima"
    for x in secventa:
        assert x in lst, "Elementul {} nu se afla in lista initiala".format(x)


# calculăm suma pentru fiecare secvență de lungime k și păstrăm secvența cu suma maximă
if __name__ == "__main__":
for i in range(n - k):
    n, k, lst = citire()
     seq_sum = sum(a[i+1:i+k+1])
     secventa = secventa_maxima(n, k, lst)
     if seq_sum > max_sum:
     validare(n, k, lst, secventa)
        max_sum = seq_sum
    print(*secventa)
        max_seq = a[i+1:i+k+1]
 
# afișăm secvența cu suma maximă
print(*max_seq)






</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția citire citește datele de intrare și le returnează sub forma unei tuple (n, k, lst).
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 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.
Î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 20:01, 17 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

Fişierul de ieşire secvk.out va conţine pe prima linie k numere, reprezentând elementele secvenței cerute.

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
6 6 4


Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0134 - SecvK

def citire():

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

def secventa_maxima(n, k, lst):

   suma_maxima = 0
   secventa_maxima = []
   for i in range(n-k+1):
       suma = sum(lst[i:i+k])
       if suma > suma_maxima:
           suma_maxima = suma
           secventa_maxima = lst[i:i+k]
   return secventa_maxima

def validare(n, k, lst, secventa):

   assert len(secventa) == k, "Lungimea secventei nu este k"
   assert sum(secventa) == max(sum(lst[i:i+k]) for i in range(n-k+1)), "Suma secventei nu este maxima"
   for x in secventa:
       assert x in lst, "Elementul {} nu se afla in lista initiala".format(x)

if __name__ == "__main__":

   n, k, lst = citire()
   secventa = secventa_maxima(n, k, lst)
   validare(n, k, lst, secventa)
   print(*secventa)


</syntaxhighlight>

Explicatie Rezolvare

Funcția citire citește datele de intrare și le returnează sub forma unei tuple (n, k, lst). 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 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. Î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).