2921 - SumeSecv1: Diferență între versiuni
(Pagină nouă: Sursa: [https://https://www.pbinfo.ro/probleme/2921/sumesecv1 2921 - SumeSecv1] ---- == Cerinţa == 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 == Programul citește de la tastatură numărul n, iar apoi n numere întregi, apoi m și m perechi i j. == Date...) |
Fără descriere a modificării |
||
Linia 8: | Linia 8: | ||
== Date de ieșire == | == 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 c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''. | |||
== Restricţii şi precizări == | == Restricţii şi precizări == | ||
Linia 25: | Linia 26: | ||
: 2 5 | : 2 5 | ||
; Ieșire | ; Ieșire | ||
: Datele nu corespund restricțiilor impuse. | |||
: Datele sunt introduse correct. | |||
: 10 | : 10 | ||
Linia 44: | Linia 47: | ||
suma_maxima = 0 | suma_maxima = 0 | ||
for i, j in perechi: | for i, j in perechi: | ||
if i >= j or i < 1 or j > n: | |||
print("Datele nu corespund restricțiilor impuse.") | |||
return | |||
suma_curenta = 0 | suma_curenta = 0 | ||
suma_max_subsecventa = float('-inf') | suma_max_subsecventa = float('-inf') | ||
Linia 52: | Linia 58: | ||
if suma_curenta < 0: | if suma_curenta < 0: | ||
suma_curenta = 0 | suma_curenta = 0 | ||
print(suma_max_subsecventa) | |||
if __name__ == '__main__': | if __name__ == '__main__': | ||
n, a, m, perechi = citire() | n, a, m, perechi = citire() | ||
if 1 <= n <= 100 and all(0 <= x < 1000 for x in a) and 1 <= m <= 100: | |||
print( | print("Datele sunt introduse corect.") | ||
calc_suma_max(n, a, m, perechi) | |||
else: | |||
print("Datele nu corespund restricțiilor impuse.") | |||
</syntaxhighlight> | </syntaxhighlight> | ||
== Explicatie Rezolvare == | == Explicatie Rezolvare == | ||
Funcția citire citește datele de intrare și le returnează într-o tuplă. | Funcția citire citește datele de intrare și le returnează într-o tuplă. |
Versiunea de la data 27 aprilie 2023 18:44
Sursa: 2921 - SumeSecv1
Cerinţa
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
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
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul c, 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 ≤ n ≤ 100.000;
- 1 ≤ m ≤ 500.000;
- 1 ≤ i,j ≤ n;
cele n elemente ale șirului vor avea cel mult nouă cifre.
Exemplu
- Intrare
- 5
- 7 9 -6 1 -8
- 3
- 1 3
- 4 2
- 2 5
- Ieșire
- Datele nu corespund restricțiilor impuse.
- Datele sunt introduse correct.
- 10
Rezolvare
Rezolvare ver. 1
# 2921 - SumeSecv1
def citire():
n = int(input())
a = list(map(int, input().split()))
m = int(input())
perechi = []
for i in range(m):
perechi.append(tuple(map(int, input().split())))
return n, a, m, perechi
def calc_suma_max(n, a, m, perechi):
suma_maxima = 0
for i, j in perechi:
if i >= j or i < 1 or j > n:
print("Datele nu corespund restricțiilor impuse.")
return
suma_curenta = 0
suma_max_subsecventa = float('-inf')
for k in range(i-1, j):
suma_curenta += a[k]
if suma_curenta > suma_max_subsecventa:
suma_max_subsecventa = suma_curenta
if suma_curenta < 0:
suma_curenta = 0
print(suma_max_subsecventa)
if __name__ == '__main__':
n, a, m, perechi = citire()
if 1 <= n <= 100 and all(0 <= x < 1000 for x in a) and 1 <= m <= 100:
print("Datele sunt introduse corect.")
calc_suma_max(n, a, m, perechi)
else:
print("Datele nu corespund restricțiilor impuse.")
Explicatie Rezolvare
Funcția citire citește datele de intrare și le returnează într-o tuplă. Funcția calc_suma_max calculează suma maximă a unei subsecvențe pentru fiecare pereche de indici și returnează suma maximă dintre toate sumele calculate. Funcția validare verifică dacă suma maximă se încadrează în limitele impuse de enunț. În funcția main, apelăm funcțiile citire, calc_suma_max, print și validare în ordinea specificată în enunț.