3796 - qtsume: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3796/qtsume 3796 - qtsume] ---- == Cerinţa == Se dă un vector A cu N numere naturale. Pentru Q întrebări de forma (x, y) aflați rezultatul sumei A[x] + 2 * A[x + 1] + ... + (y - x + 1) * A[y]. == Date de intrare == Fișierul de intrare qtsume.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale separate prin spații, reprezentând vectorul A. Pe următoarea linie se află numărul Q. Urmează Q linii, pe fi...
 
Flaviu (talk | contribs)
No edit summary
Line 9: Line 9:


== Date de ieșire ==  
== Date de ieșire ==  
Fișierul de ieșire qtsume.out va conține pe Q linii, pe linia i aflându-se răspunsul la a i-a întrebare în ordinea citirii.
Fișierul de ieșire qtsume.out va conține  
 
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 ==
Line 23: Line 26:
: 2 4
: 2 4
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele sunt introduse correct.
: 5
: 5
: 48
: 48
Line 32: Line 37:
# 3796 - qtsume
# 3796 - qtsume


def citeste_date_intrare():
def citire_date():
     n = int(input())
     n = int(input())
     sir = []
     v = list(map(int, input().split()))
     for i in range(n):
    q = int(input())
         sir.append(int(input()))
    intrebari = []
     return sir
     for i in range(q):
         x, y = map(int, input().split())
        intrebari.append((x, y))
     return n, v, q, intrebari


def numara_secvente_crescatoare(sir):
def validare(n, v, q, intrebari):
     numar_secvente = 0
     if len(v) != n:
    lungime_maxima = 1
        return False
    lungime_curenta = 1
     for x in v:
     for i in range(1, len(sir)):
         if x < 1 or x > 1000000:
         if sir[i] >= sir[i-1]:
             return False
            lungime_curenta += 1
     if q < 1 or q > 100000:
        else:
         return False
            if lungime_curenta > lungime_maxima:
     for x, y in intrebari:
                lungime_maxima = lungime_curenta
         if x < 1 or x > n or y < 1 or y > n or x > y:
                numar_secvente = 1
            return False
             elif lungime_curenta == lungime_maxima:
     return True
                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):
def calc_suma(x, y, v):
     assert len(sir) > 0
     suma = 0
     assert numar_secvente >= 0
    for i in range(x-1, y):
        suma += (i-x+1+1)*v[i]
    return suma
 
if __name__ == '__main__':
    n, v, q, intrebari = citire_date()
     if validare(n, v, q, intrebari):
        print("Datele sunt introduse corect.")
        for x, y in intrebari:
            suma = calc_suma(x, y, v)
            print(suma)
    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 read_input citește datele de intrare și le returnează sub forma unei tuple ce conține n, a și queries. solve primește aceste date și calculează suma pentru fiecare interogare. Funcția validate verifică că rezultatele obținute sunt corecte. În cele din urmă, în funcția main, citim datele de intrare, apelăm funcția solve, validăm rezultatele și le afișăm.
 
Funcția citire_date() citește datele de intrare și le returnează sub forma unor variabile: n pentru numărul de elemente din vectorul A, v pentru vectorul A, q pentru numărul de întrebări și intrebari pentru o listă de tupluri, fiecare tuplu reprezentând o întrebare.
Funcția validare() verifică dacă datele de intrare respectă restricțiile cerute în enunț, returnând True dacă datele sunt valide și False în caz contrar.
Funcția calc_suma() calculează suma cerută pentru o întrebare, pe baza formulei din enunț.
În funcția main(), se verifică dacă datele de intrare sunt valide și se afișează mesajul corespunzător. Dacă datele sunt valide, se calculează suma pentru fiecare întrebare și se afișează rezultatul.

Revision as of 18:53, 27 April 2023

Sursa: 3796 - qtsume


Cerinţa

Se dă un vector A cu N numere naturale. Pentru Q întrebări de forma (x, y) aflați rezultatul sumei A[x] + 2 * A[x + 1] + ... + (y - x + 1) * A[y].


Date de intrare

Fișierul de intrare qtsume.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale separate prin spații, reprezentând vectorul A. Pe următoarea linie se află numărul Q. Urmează Q linii, pe fiecare linie se află două numere naturale separate printr-un spațiu reprezentând x și y.

Date de ieșire

Fișierul de ieșire qtsume.out va conține

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, Q ≤ 100.000
  • 1 ≤ A[i] ≤ 1.000.000
  • 1 ≤ x ≤ y ≤ N
Intrare
5
3 1 2 3 5
3
1 2
1 5
2 4
Ieșire
Datele nu corespund restricțiilor impuse.
Datele sunt introduse correct.
5
48
14

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 3796 - qtsume

def citire_date():

   n = int(input())
   v = list(map(int, input().split()))
   q = int(input())
   intrebari = []
   for i in range(q):
       x, y = map(int, input().split())
       intrebari.append((x, y))
   return n, v, q, intrebari

def validare(n, v, q, intrebari):

   if len(v) != n:
       return False
   for x in v:
       if x < 1 or x > 1000000:
           return False
   if q < 1 or q > 100000:
       return False
   for x, y in intrebari:
       if x < 1 or x > n or y < 1 or y > n or x > y:
           return False
   return True

def calc_suma(x, y, v):

   suma = 0
   for i in range(x-1, y):
       suma += (i-x+1+1)*v[i]
   return suma

if __name__ == '__main__':

   n, v, q, intrebari = citire_date()
   if validare(n, v, q, intrebari):
       print("Datele sunt introduse corect.")
       for x, y in intrebari:
           suma = calc_suma(x, y, v)
           print(suma)
   else:
       print("Datele nu corespund restricțiilor impuse.")


</syntaxhighlight>

Explicatie Rezolvare

Funcția citire_date() citește datele de intrare și le returnează sub forma unor variabile: n pentru numărul de elemente din vectorul A, v pentru vectorul A, q pentru numărul de întrebări și intrebari pentru o listă de tupluri, fiecare tuplu reprezentând o întrebare. Funcția validare() verifică dacă datele de intrare respectă restricțiile cerute în enunț, returnând True dacă datele sunt valide și False în caz contrar. Funcția calc_suma() calculează suma cerută pentru o întrebare, pe baza formulei din enunț. În funcția main(), se verifică dacă datele de intrare sunt valide și se afișează mesajul corespunzător. Dacă datele sunt valide, se calculează suma pentru fiecare întrebare și se afișează rezultatul.