0299 - SumeSecv: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/299/sumesecv - SumeSecv] ---- == Cerinţa == Se dă un vector cu n elemente numere naturale, numerotate de la 1 la n, și m perechi de indici (i,j), cu 1≤i<j≤n. Să se determine, pentru fiecare pereche (i,j), suma elementelor din secvenţa determinată de i şi j. == Date de intrare == Fişierul de intrare sumesecv.in conţine pe prima linie numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține n...)
 
Fără descriere a modificării
 
(Nu s-au afișat 7 versiuni intermediare efectuate de alți 2 utilizatori)
Linia 8: Linia 8:


== Date de ieșire ==  
== Date de ieșire ==  
Fişierul de ieşire sumesecv.out va conţine pe prima linie cele m sume determinate, separate prin câte un spațiu.
Dacă datele sunt introduse corect, pe ecran se va afișa:
'''"Datele sunt introduse corect."''', apoi fișierul sumesecv.out conține  ''' numărul n. Î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 14: Linia 15:
* elementele vectorului vor fi mai mici decât 1000
* elementele vectorului vor fi mai mici decât 1000
* 1 ≤ m ≤ 100
* 1 ≤ m ≤ 100
== Exemplu ==
== Exemplu 1  ==
; Intrare
; Intrare
:sumesecv.in
: 10
: 10
: 5 5 1 3 6 4 1 2 10 6  
: 5 5 1 3 6 4 1 2 10 6  
Linia 23: Linia 25:
: 6 10  
: 6 10  
; Ieșire
; Ieșire
: Datele sunt introduse correct
: sumesecv.out
: 13 19 23  
: 13 19 23  
== Exemplu 2 ==
; Intrare
: sumesecv.in
: 5
: 1 2 3 4 5
: 2
: 1 5
: 2 4
; Ieșire
: Datele nu corespund restrictiilor impuse


== Rezolvare ==  
== Rezolvare ==  
Linia 30: Linia 46:
# 0304 - Secvente
# 0304 - Secvente


def citeste_date_intrare():
def calculeaza_suma_secvente(n, v, m, perechi):
     n = int(input())
     for pereche in perechi:
    sir = []
        i, j = pereche
    for i in range(n):
        suma = 0
         sir.append(int(input()))
        for k in range(i, j + 1):
    return sir
            suma += v[k - 1]
         print(suma, end=' ')


def numara_secvente_crescatoare(sir):
def valideaza_datele(n, v, m, perechi):
     numar_secvente = 0
     if n != len(v):
    lungime_maxima = 1
         return False
    lungime_curenta = 1
    for i, j in perechi:
    for i in range(1, len(sir)):
         if not (1 <= i < j <= n):
         if sir[i] >= sir[i-1]:
             return False
            lungime_curenta += 1
     return True
         else:
            if lungime_curenta > lungime_maxima:
                lungime_maxima = lungime_curenta
                numar_secvente = 1
            elif lungime_curenta == lungime_maxima:
                numar_secvente += 1
             lungime_curenta = 1
    if lungime_curenta > lungime_maxima:
        lungime_maxima = lungime_curenta
        numar_secvente = 1
    elif lungime_curenta == lungime_maxima:
        numar_secvente += 1
     return numar_secvente


def valideaza(sir, numar_secvente):
if __name__ == '__main__':
     assert len(sir) > 0
    with open('sumesecv.in', 'r') as f:
     assert numar_secvente >= 0
        n = int(f.readline())
        v = list(map(int, f.readline().split()))
        m = int(f.readline())
        perechi = [tuple(map(int, f.readline().split())) for _ in range(m)]
     if valideaza_datele(n, v, m, perechi):
        print('Datele sunt introduse corect.')
        calculeaza_suma_secvente(n, v, m, perechi)
     else:
        print('Datele nu corespund restricțiilor impuse.')


if __name__ == "__main__":
    sir = citeste_date_intrare()
    numar_secvente = numara_secvente_crescatoare(sir)
    valideaza(sir, numar_secvente)
    print(numar_secvente)


</syntaxhighlight>
</syntaxhighlight>


== Explicatie Rezolvare ==  
== Explicatie Rezolvare ==  
Funcția citeste_date_intrare primește datele de intrare de la tastatură și le returnează sub forma unei liste.


Funcția numara_secvente_crescatoare primește lista de numere și numără secvențele maximale cu elemente ordonate crescător din șirul dat. Algoritmul este simplu: parcurgem lista și ținem minte lungimea maximă a unei secvențe cu elemente ordonate crescător și numărul de astfel de secvențe găsite până în acel moment. Când întâlnim un element mai mic decât cel precedent, înseamnă că secvența curentă s-a încheiat, verificăm dacă are lungimea maximă și actualizăm numărul de secvențe dacă e cazul. La final mai facem o verificare dacă ultima secvență a fost maximă.
Funcția calculeaza_suma_secvente primește ca parametri numărul de elemente din vector (n), vectorul (v), numărul de perechi de indici (m) și o listă de perechi de indici (perechi). Aceasta parcurge lista de perechi de indici și pentru fiecare pereche calculează suma elementelor din secvența determinată de indicii respectivi.


Funcția valideaza verifică dacă datele de ieșire sunt valide.
Funcția valideaza_datele primește ca parametri numărul de elemente din vector (n), vectorul (v), numărul de perechi de indici (m) și o listă de perechi de indici (perechi). Aceasta verifică dacă datele introduse sunt valide, adică dacă numărul de elemente din vector corespunde cu n, iar fiecare pereche de indici are valorile corecte.


În blocul if __name__ == "__main__": citim datele de intrare, apelăm funcția numara_secvente_crescatoare și afișăm rezultatul.
În funcția main, se deschide fișierul de intrare, se citesc datele și se verifică dacă sunt valide prin apelarea funcției valideaza_datele. Dacă datele sunt valide, se afișează mesajul "Datele sunt introduse corect." și se calculează suma pentru fiecare pereche de indici prin apelarea funcției calculeaza_suma_secvente. Dacă datele nu sunt valide, se afișează mesajul "Datele nu corespund restricțiilor impuse.".

Versiunea curentă din 14 mai 2023 20:46

Sursa: - SumeSecv

Cerinţa

Se dă un vector cu n elemente numere naturale, numerotate de la 1 la n, și m perechi de indici (i,j), cu 1≤i<j≤n. Să se determine, pentru fiecare pereche (i,j), suma elementelor din secvenţa determinată de i şi j.

Date de intrare

Fişierul de intrare sumesecv.in conţine pe prima linie numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi fișierul sumesecv.out conține numărul n. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

  • 1 ≤ n ≤ 100
  • elementele vectorului vor fi mai mici decât 1000
  • 1 ≤ m ≤ 100

Exemplu 1

Intrare
sumesecv.in
10
5 5 1 3 6 4 1 2 10 6
3
5 8
2 6
6 10
Ieșire
Datele sunt introduse correct
sumesecv.out
13 19 23

Exemplu 2

Intrare
sumesecv.in
5
1 2 3 4 5
2
1 5
2 4
Ieșire
Datele nu corespund restrictiilor impuse


Rezolvare

Rezolvare ver. 1

# 0304 - Secvente

def calculeaza_suma_secvente(n, v, m, perechi):
    for pereche in perechi:
        i, j = pereche
        suma = 0
        for k in range(i, j + 1):
            suma += v[k - 1]
        print(suma, end=' ')

def valideaza_datele(n, v, m, perechi):
    if n != len(v):
        return False
    for i, j in perechi:
        if not (1 <= i < j <= n):
            return False
    return True

if __name__ == '__main__':
    with open('sumesecv.in', 'r') as f:
        n = int(f.readline())
        v = list(map(int, f.readline().split()))
        m = int(f.readline())
        perechi = [tuple(map(int, f.readline().split())) for _ in range(m)]
    if valideaza_datele(n, v, m, perechi):
        print('Datele sunt introduse corect.')
        calculeaza_suma_secvente(n, v, m, perechi)
    else:
        print('Datele nu corespund restricțiilor impuse.')

Explicatie Rezolvare

Funcția calculeaza_suma_secvente primește ca parametri numărul de elemente din vector (n), vectorul (v), numărul de perechi de indici (m) și o listă de perechi de indici (perechi). Aceasta parcurge lista de perechi de indici și pentru fiecare pereche calculează suma elementelor din secvența determinată de indicii respectivi.

Funcția valideaza_datele primește ca parametri numărul de elemente din vector (n), vectorul (v), numărul de perechi de indici (m) și o listă de perechi de indici (perechi). Aceasta verifică dacă datele introduse sunt valide, adică dacă numărul de elemente din vector corespunde cu n, iar fiecare pereche de indici are valorile corecte.

În funcția main, se deschide fișierul de intrare, se citesc datele și se verifică dacă sunt valide prin apelarea funcției valideaza_datele. Dacă datele sunt valide, se afișează mesajul "Datele sunt introduse corect." și se calculează suma pentru fiecare pereche de indici prin apelarea funcției calculeaza_suma_secvente. Dacă datele nu sunt valide, se afișează mesajul "Datele nu corespund restricțiilor impuse.".

Adus de la „http://wiki.universitas.ro/index.php?title=0299_-_SumeSecv&oldid=6456”