0134 - SecvK: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 23: Line 23:
: 5 6 1 2 6 6 4 3
: 5 6 1 2 6 6 4 3
; Ieșire
; Ieșire
: Datele sunt introduse correct
: secvk.out
: secvk.out
: Datele nu corespund restricțiilor impuse.
: 6 6 4
: 6 6 4
== Exemplu 2 ==
== Exemplu 2 ==
Line 30: Line 30:
: secvk.in
: secvk.in
: 8 3
: 8 3
: 5 6 1 2 6 6 4 3
: 52748
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: secvk.out
: secvk.out
: Datele nu corespund restricțiilor impuse.
: 2 3 4
: 2 3 4


Line 41: Line 41:
# 0134 - SecvK
# 0134 - SecvK


def citire():
def max_sum_sequence(n, k, arr):
     n, k = map(int, input().split())
     if k > n:
     sir = list(map(int, input().split()))
        return None
     return n, k, sir
   
    max_sum = -float('inf')
     max_seq = []
   
    for i in range(n - k + 1):
        seq = arr[i:i+k]
        seq_sum = sum(seq)
       
        if seq_sum > max_sum:
            max_sum = seq_sum
            max_seq = seq
   
     return max_seq


def rezolvare(n, k, sir):
def main():
     if k > n:
     with open('secvk.in', 'r') as fin:
         return None  # Daca k > n, secventa de lungime k nu poate fi formata
         n, k = map(int, fin.readline().split())
    start = 0  # Primul index al secventei curente
        arr = list(map(int, fin.readline().split()))
    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 n != len(arr) or k > n or any(x >= 1000 for x in arr):
    if suma_maxima is None:
         print("Datele nu corespund restricțiilor impuse.")
         print("Datele nu corespund restricțiilor impuse.")
        return
    seq = max_sum_sequence(n, k, arr)
    if seq is None:
        print("Nu exista secventa de lungime k in arr.")
     else:
     else:
         print("Datele sunt introduse corect.")
         print("Datele sunt introduse corect.")
         print(suma_maxima)
         with open('secvk.out', 'w') as fout:
            fout.write(' '.join(map(str, seq)))


if __name__ == '__main__':
if __name__ == '__main__':
     # Teste
     main()
    n, k, sir = citire()
    suma_maxima = rezolvare(n, k, sir)
    afisare(suma_maxima)
 
 
</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Funcția citire() primește datele de intrare de la tastatură și returnează cele trei variabile n, k și sir.
Funcția `max_sum_sequence(n, k, arr)` primește ca argumente numărul de elemente din șir `n`, numărul `k` pentru lungimea secvenței și lista de numere `arr`. Funcția verifică dacă `k` este mai mare decât `n` și, în caz afirmativ, returnează `None`. Apoi, funcția găsește secvența de lungime `k` cu suma maximă din lista `arr`. Variabilele `max_sum` și `max_seq` sunt inițializate cu valori negative și lista goală, respectiv. Pentru fiecare subsecvență de lungime `k` din `arr`, se calculează suma și se compară cu `max_sum`. Dacă este mai mare, atunci valoarea sumei este actualizată, iar lista `max_seq` este setată la subsecvența curentă. La final, funcția returnează lista `max_seq`.
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.
Funcția `main()` începe prin citirea datelor de intrare din fișierul `secvk.in`. Apoi, se verifică dacă datele de intrare respectă restricțiile cerute și se afișează un mesaj corespunzător în cazul în care datele nu corespund. În caz contrar, se calculează secvența de lungime `k` cu suma maximă din lista `arr` folosind funcția `max_sum_sequence()`. Dacă nu există nicio secvență de lungime `k` în `arr`, se afișează un mesaj corespunzător. În caz contrar, se afișează un mesaj de confirmare și se scrie secvența găsită în fișierul `secvk.out`. Funcția `main()` este apelată doar dacă acest script este rulat direct, nu este importat ca modul în alt script, acest lucru se realizează prin instrucțiunea `if __name__ == '__main__':`.

Revision as of 21:45, 13 May 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 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

  • 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 1

Intrare
secvk.in
8 3
5 6 1 2 6 6 4 3
Ieșire
Datele sunt introduse correct
secvk.out
6 6 4

Exemplu 2

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

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0134 - SecvK

def max_sum_sequence(n, k, arr):

   if k > n:
       return None
   
   max_sum = -float('inf')
   max_seq = []
   
   for i in range(n - k + 1):
       seq = arr[i:i+k]
       seq_sum = sum(seq)
       
       if seq_sum > max_sum:
           max_sum = seq_sum
           max_seq = seq
   
   return max_seq

def main():

   with open('secvk.in', 'r') as fin:
       n, k = map(int, fin.readline().split())
       arr = list(map(int, fin.readline().split()))
   if n != len(arr) or k > n or any(x >= 1000 for x in arr):
       print("Datele nu corespund restricțiilor impuse.")
       return
   seq = max_sum_sequence(n, k, arr)
   if seq is None:
       print("Nu exista secventa de lungime k in arr.")
   else:
       print("Datele sunt introduse corect.")
       with open('secvk.out', 'w') as fout:
           fout.write(' '.join(map(str, seq)))

if __name__ == '__main__':

   main()

</syntaxhighlight>

Explicatie Rezolvare

Funcția `max_sum_sequence(n, k, arr)` primește ca argumente numărul de elemente din șir `n`, numărul `k` pentru lungimea secvenței și lista de numere `arr`. Funcția verifică dacă `k` este mai mare decât `n` și, în caz afirmativ, returnează `None`. Apoi, funcția găsește secvența de lungime `k` cu suma maximă din lista `arr`. Variabilele `max_sum` și `max_seq` sunt inițializate cu valori negative și lista goală, respectiv. Pentru fiecare subsecvență de lungime `k` din `arr`, se calculează suma și se compară cu `max_sum`. Dacă este mai mare, atunci valoarea sumei este actualizată, iar lista `max_seq` este setată la subsecvența curentă. La final, funcția returnează lista `max_seq`.

Funcția `main()` începe prin citirea datelor de intrare din fișierul `secvk.in`. Apoi, se verifică dacă datele de intrare respectă restricțiile cerute și se afișează un mesaj corespunzător în cazul în care datele nu corespund. În caz contrar, se calculează secvența de lungime `k` cu suma maximă din lista `arr` folosind funcția `max_sum_sequence()`. Dacă nu există nicio secvență de lungime `k` în `arr`, se afișează un mesaj corespunzător. În caz contrar, se afișează un mesaj de confirmare și se scrie secvența găsită în fișierul `secvk.out`. Funcția `main()` este apelată doar dacă acest script este rulat direct, nu este importat ca modul în alt script, acest lucru se realizează prin instrucțiunea `if __name__ == '__main__':`.