3796 - qtsume: Difference between revisions

Revision as of 18:53, 27 April 2023

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

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.

@@ Line 9: / Line 9: @@
 == 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 ==
@@ Line 23: / Line 26: @@
 : 2 4
 ; Ieșire
+: Datele nu corespund restricțiilor impuse.
+: Datele sunt introduse correct.
 : 5
 : 48
@@ Line 32: / Line 37: @@
 # 3796 - qtsume
-def citeste_date_intrare():
+def citire_date():
      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>
 == 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.