0134 - SecvK: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
 
Linia 26: Linia 26:
: secvk.out
: secvk.out
: 6 6 4
: 6 6 4
== Exemplu 2 ==
== Exemplu 2 ==
; Intrare
; Intrare
Linia 33: Linia 34:
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.
: secvk.out
 
: 2 3 4


== Rezolvare ==  
== Rezolvare ==  
Linia 41: Linia 41:
# 0134 - SecvK
# 0134 - SecvK


def max_sum_sequence(n, k, arr):
def validate_input(n, k, arr):
     if k > n:
     if k > n or n > 100000 or k < 1 or n < 1 or any(x >= 1000 for x in arr):
        return None
         return False
   
     return True
    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):
def find_max_sequence(n, k, arr):
         print("Datele nu corespund restricțiilor impuse.")
     if not validate_input(n, k, arr):
        return
         return "Datele nu corespund restricțiilor impuse.", []


     seq = max_sum_sequence(n, k, arr)
     start = 0
    end = k-1
    max_sum = sum(arr[start:end+1])
    result = arr[start:end+1]
 
    for i in range(k, n):
        start += 1
        end += 1
        current_sum = sum(arr[start:end+1])
        if current_sum > max_sum:
            max_sum = current_sum
            result = arr[start:end+1]
 
    return "Datele sunt introduse corect.", result
 
 
if __name__ == "__main__":
    with open("secvk.in", "r") as f:
        n, k = map(int, f.readline().strip().split())
        arr = list(map(int, f.readline().strip().split()))
 
    message, result = find_max_sequence(n, k, arr)
 
    print(message)
    if message == "Datele sunt introduse corect.":
        with open("secvk.out", "w") as f:
            f.write(" ".join(str(x) for x in result)))


    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>
</syntaxhighlight>
== Explicatie Rezolvare ==
== 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`.
validate_input(n, k, arr) - această funcție primește trei argumente: n și k, reprezentând numărul total de elemente din listă, respectiv numărul de elemente consecutive din listă pe care trebuie să le adunăm, și arr, o listă de numere întregi. Funcția verifică dacă toate aceste valori respectă restricțiile impuse: 1 ≤ k ≤ n ≤ 100.000, iar toate numerele din listă sunt mai mici decât 1000. În cazul în care aceste condiții nu sunt respectate, funcția returnează False, altfel returnează True.
 
find_max_sequence(n, k, arr) - această funcție primește aceiași trei argumente ca și funcția de mai sus, și calculează suma maximă a unei secvențe de k elemente consecutive din lista arr. Pentru a face acest lucru, funcția folosește o metodă de tip sliding window, parcurgând lista arr și determinând suma maximă a unei ferestre glisante de lungime k. Dacă argumentele nu respectă restricțiile impuse, funcția returnează un mesaj de eroare și o listă vidă, altfel returnează un mesaj de succes și lista de k elemente consecutive care au suma maximă.


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__':`.
main() - această funcție deschide fișierul secvk.in, citind valorile n, k și lista arr. Apoi, apelează funcția find_max_sequence() cu aceste argumente și afișează mesajul de eroare sau lista de elemente dacă acestea sunt valabile. În cazul în care lista de elemente este validă, scrie rezultatul în fișierul secvk.out.

Versiunea curentă din 14 mai 2023 20:29

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."ș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

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


Rezolvare

Rezolvare ver. 1

# 0134 - SecvK

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


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

    start = 0
    end = k-1
    max_sum = sum(arr[start:end+1])
    result = arr[start:end+1]

    for i in range(k, n):
        start += 1
        end += 1
        current_sum = sum(arr[start:end+1])
        if current_sum > max_sum:
            max_sum = current_sum
            result = arr[start:end+1]

    return "Datele sunt introduse corect.", result


if __name__ == "__main__":
    with open("secvk.in", "r") as f:
        n, k = map(int, f.readline().strip().split())
        arr = list(map(int, f.readline().strip().split()))

    message, result = find_max_sequence(n, k, arr)

    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

validate_input(n, k, arr) - această funcție primește trei argumente: n și k, reprezentând numărul total de elemente din listă, respectiv numărul de elemente consecutive din listă pe care trebuie să le adunăm, și arr, o listă de numere întregi. Funcția verifică dacă toate aceste valori respectă restricțiile impuse: 1 ≤ k ≤ n ≤ 100.000, iar toate numerele din listă sunt mai mici decât 1000. În cazul în care aceste condiții nu sunt respectate, funcția returnează False, altfel returnează True.

find_max_sequence(n, k, arr) - această funcție primește aceiași trei argumente ca și funcția de mai sus, și calculează suma maximă a unei secvențe de k elemente consecutive din lista arr. Pentru a face acest lucru, funcția folosește o metodă de tip sliding window, parcurgând lista arr și determinând suma maximă a unei ferestre glisante de lungime k. Dacă argumentele nu respectă restricțiile impuse, funcția returnează un mesaj de eroare și o listă vidă, altfel returnează un mesaj de succes și lista de k elemente consecutive care au suma maximă.

main() - această funcție deschide fișierul secvk.in, citind valorile n, k și lista arr. Apoi, apelează funcția find_max_sequence() cu aceste argumente și afișează mesajul de eroare sau lista de elemente dacă acestea sunt valabile. În cazul în care lista de elemente este validă, scrie rezultatul în fișierul secvk.out.