2921 - SumeSecv1

From Bitnami MediaWiki
Revision as of 20:50, 14 May 2023 by Flaviu (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Sursa: 2921 - SumeSecv1


Cerinţa[edit | edit source]

Se dă un șir cu n elemente numere întregi, numerotate de la 1 la n și m perechi de indici i j. Pentru fiecare pereche de indici se calculează suma elementelor din secvență determinată de cei doi indici. Afișați suma maximă obținută.

Date de intrare[edit | edit source]

Programul citește de la tastatură numărul n, iar apoi n numere întregi, apoi m și m perechi i j.


Date de ieșire[edit | edit source]

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 maximă determinată, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări[edit | edit source]

  • 1 ≤ n ≤ 100.000;
  • 1 ≤ m ≤ 500.000;
  • 1 ≤ i,j ≤ n;

cele n elemente ale șirului vor avea cel mult nouă cifre.

Exemplu 1[edit | edit source]

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

Exemplu 2[edit | edit source]

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

Rezolvare[edit | edit source]

Rezolvare ver. 1[edit | edit source]

<syntaxhighlight lang="python" line>

  1. 2921 - SumeSecv1

def validate_input(n, arr, m, pairs):

   if not(1 <= n <= 100000 and 1 <= m <= 500000 and len(arr) == n and len(pairs) == m):
       print("Datele nu corespund restricțiilor impuse.")
       return False
   for num in arr:
       if abs(num) > 10**9:
           print("Datele nu corespund restricțiilor impuse.")
           return False
   for i, j in pairs:
       if not (1 <= i <= j <= n):
           print("Datele nu corespund restricțiilor impuse.")
           return False
   print("Datele sunt introduse corect.")
   return True


def find_max_sum(n, arr, m, pairs):

   if not validate_input(n, arr, m, pairs):
       return
   max_sum = float('-inf')
   for i, j in pairs:
       curr_sum = sum(arr[i-1:j])
       if curr_sum > max_sum:
           max_sum = curr_sum
   print(max_sum)


if __name__ == "__main__":

   n = int(input())
   arr = list(map(int, input().split()))
   m = int(input())
   pairs = []
   for _ in range(m):
       i, j = map(int, input().split())
       pairs.append((i, j))
   find_max_sum(n, arr, m, pairs)


</syntaxhighlight>

Explicatie Rezolvare[edit | edit source]

Funcția `validate_input` este o funcție care primește ca parametrii dimensiunile listei de numere întregi, lista de numere întregi și lista de perechi de indici, verifica dacă datele introduse corespund restricțiilor impuse și afișează un mesaj corespunzător. Aceasta returnează `True` dacă datele sunt corecte și `False` în caz contrar.

Funcția `find_max_sum` primește aceleași parametrii ca și `validate_input`. Verifică dacă datele sunt introduse corect prin apelarea funcției `validate_input` și returnează `None` dacă datele nu sunt corecte. În caz contrar, calculează și afișează suma maximă dintre toate secvențele date de perechile de indici.

Funcția `main` citește datele de intrare, apelează funcția `find_max_sum` și afișează rezultatul.