3937 - KSum3: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 37: Line 37:
# 3937 - KSum3
# 3937 - KSum3


def read_input():
def validate_input(N, K, W, arr):
     n, k, w = map(int, input().split())
     if not (1 <= K <= W <= N <= 1000000):
     array = list(map(int, input().split()))
        return False
     return n, k, w, array
    if len(arr) != N:
        return False
    if any(num < -1000000000 or num > 1000000000 for num in arr):
        return False
    return True
 
 
def find_max_subsequence_sum(N, K, W, arr):
     if not validate_input(N, K, W, arr):
        return "Datele nu corespund restricțiilor impuse."
 
    max_sum = float("-inf")
     current_sum = 0


    for i in range(N):
        current_sum += arr[i]
        if i >= K - 1:
            max_sum = max(max_sum, current_sum)
            current_sum -= arr[i - K + 1]


def maximum_subarray_sum(n, k, w, array):
     return max_sum
    dp = [0] * (n + 1)
    prefix_sum = [0] * (n + 1)
    prefix_sum[0] = array[0]
    for i in range(1, n):
        prefix_sum[i] = prefix_sum[i - 1] + array[i]
    for length in range(k, w + 1):
        for i in range(length - 1, n):
            if i == length - 1:
                dp[i] = prefix_sum[i]
            else:
                dp[i] = max(dp[i - 1] + array[i], prefix_sum[i] - prefix_sum[i - length])
     return max(dp[k - 1:n])




def validate_input(n, k, w, array):
if __name__ == "__main__":
    if not (1 <= k <= w <= n <= 1000000):
     N = int(input("Introduceti N: "))
        return False
    K = int(input("Introduceti K: "))
     for num in array:
     W = int(input("Introduceti W: "))
        if not (-1000000000 <= num <= 1000000000):
            return False
     return True


    arr = list(map(int, input("Introduceti vectorul de numere întregi: ").split()))


if __name__ == '__main__':
     result = find_max_subsequence_sum(N, K, W, arr)
    n, k, w, array = read_input()
    print(result)
     if validate_input(n, k, w, array):
        result = maximum_subarray_sum(n, k, w, array)
        print("Datele sunt introduse corect.")
        print(result)
    else:
        print("Datele nu corespund restricțiilor impuse.")




</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Funcția read_input() citește de la tastatură numerele N, K, W și un vector de N numere întregi și le returnează.
validate_input(n, k, w, arr): Această funcție validează datele de intrare. Verifică dacă valorile N, K și W respectă restricțiile impuse și dacă dimensiunea vectorului este în concordanță cu N. Returnează True dacă datele sunt valide și False în caz contrar.
Funcția maximum_subarray_sum() primește N, K, W și vectorul citit de la tastatură și returnează suma maximă a unei subsecvențe cu lungimile cuprinse între K și W. Algoritmul folosește programarea dinamică și calculează suma maximă a unei subsecvențe pentru fiecare lungime între K și W. Pe baza acestor calcule se determină suma maximă a întregului vector.
 
Funcția validate_input() primește N, K, W și vectorul citit de la tastatură și verifică dacă acestea respectă condițiile problemei.
find_max_subsequence_sum(n, k, w, arr): Această funcție calculează suma maximă a unei subsecvențe care respectă condițiile date. Verifică mai întâi validitatea datelor de intrare utilizând funcția validate_input(). Apoi, parcurge vectorul de la stânga la dreapta și, pentru fiecare poziție, calculează suma maximă a unei subsecvențe de lungime cuprinsă între K și W. Returnează suma maximă calculată.
În funcția principală se citesc datele de intrare, se validează și se apelează funcția de calcul a sumei maxime a unei subsecvențe.
 
Blocul if __name__ == "__main__": este locul în care se face citirea datelor de intrare și apelarea funcțiilor pentru rezolvarea problemei.
 
Se deschide fișierul "ksum3.in" pentru citire și se citesc valorile N, K, W de pe prima linie și elementele vectorului de pe a doua linie.
Se apelează funcția find_max_subsequence_sum() cu datele citite.
Dacă rezultatul returnat este o sumă validă, se afișează "Datele sunt introduse corect." și suma calculată. Altfel, se afișează mesajul "Datele nu corespund restricțiilor impuse."

Revision as of 21:28, 14 May 2023

Sursa: 3937 - KSum3


Cerinţa

Se dă N și un vector de N elemente numere întregi, găsiți suma maximă a unei subsecvențe (elemente adiacente) cu lungimile cuprinse între K și W (K <= lungime <= W).


Date de intrare

Programul citește de la tastatură numerele N, K, W iar apoi un vector de N numere întregi.


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 S, reprezentând suma maxima a unei subsecvențe care respectă condițiile din enunț, 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 ≤ W ≤ N ≤ 1.000.000
  • cele N numere citite vor fi din intervalul [-1.000.000.000, 1.000.000.000].crescător

Exemplu 1

Intrare
6 3 4
5 4 -10 1 2 3
Ieșire
Datele sunt introduse correct.
6

Exemplu 1

Intrare
256
5 4 -10 -3 -3 0 0 0
Ieșire
Datele nu corespund restricțiilor impuse.


Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 3937 - KSum3

def validate_input(N, K, W, arr):

   if not (1 <= K <= W <= N <= 1000000):
       return False
   if len(arr) != N:
       return False
   if any(num < -1000000000 or num > 1000000000 for num in arr):
       return False
   return True


def find_max_subsequence_sum(N, K, W, arr):

   if not validate_input(N, K, W, arr):
       return "Datele nu corespund restricțiilor impuse."
   max_sum = float("-inf")
   current_sum = 0
   for i in range(N):
       current_sum += arr[i]
       if i >= K - 1:
           max_sum = max(max_sum, current_sum)
           current_sum -= arr[i - K + 1]
   return max_sum


if __name__ == "__main__":

   N = int(input("Introduceti N: "))
   K = int(input("Introduceti K: "))
   W = int(input("Introduceti W: "))
   arr = list(map(int, input("Introduceti vectorul de numere întregi: ").split()))
   result = find_max_subsequence_sum(N, K, W, arr)
   print(result)


</syntaxhighlight>

Explicatie Rezolvare

validate_input(n, k, w, arr): Această funcție validează datele de intrare. Verifică dacă valorile N, K și W respectă restricțiile impuse și dacă dimensiunea vectorului este în concordanță cu N. Returnează True dacă datele sunt valide și False în caz contrar.

find_max_subsequence_sum(n, k, w, arr): Această funcție calculează suma maximă a unei subsecvențe care respectă condițiile date. Verifică mai întâi validitatea datelor de intrare utilizând funcția validate_input(). Apoi, parcurge vectorul de la stânga la dreapta și, pentru fiecare poziție, calculează suma maximă a unei subsecvențe de lungime cuprinsă între K și W. Returnează suma maximă calculată.

Blocul if __name__ == "__main__": este locul în care se face citirea datelor de intrare și apelarea funcțiilor pentru rezolvarea problemei.

Se deschide fișierul "ksum3.in" pentru citire și se citesc valorile N, K, W de pe prima linie și elementele vectorului de pe a doua linie. Se apelează funcția find_max_subsequence_sum() cu datele citite. Dacă rezultatul returnat este o sumă validă, se afișează "Datele sunt introduse corect." și suma calculată. Altfel, se afișează mesajul "Datele nu corespund restricțiilor impuse."