0299 - SumeSecv: Difference between revisions

Revision as of 18:42, 27 April 2023

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

Fişierul de ieşire secvente.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 ≤ 100
elementele vectorului vor fi mai mici decât 1000
1 ≤ m ≤ 100

Exemplu

Intrare: 10; 5 5 1 3 6 4 1 2 10 6; 3; 5 8; 2 6; 6 10
Ieșire: Datele nu corespund restricțiilor impuse.; Datele sunt introduse correct; 13 19 23

Rezolvare

Rezolvare ver. 1

0304 - Secvente

def citire_date():

   n = int(input())
   v = list(map(int, input().split()))
   m = int(input())
   perechi = []
   for i in range(m):
       a, b = map(int, input().split())
       perechi.append((a, b))
   return n, v, m, perechi

def suma_secventa(n, v, a, b):

   suma = 0
   for i in range(a-1, b):
       suma += v[i]
   return suma

if __name__ == '__main__':

   n, v, m, perechi = citire_date()
   if 1 <= n <= 100 and 1 <= m <= 100:
       print("Datele sunt introduse corect.")
       for a, b in perechi:
           print(suma_secventa(n, v, a, b))
   else:
       print("Datele nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicatie Rezolvare

Funcția citire_date citește datele de intrare din consolă și le returnează sub formă de tuplu. Funcția suma_secventa primește un vector v, un interval [a, b] și calculează suma elementelor din secvența din vectorul v care începe la poziția a și se termină la poziția b. În funcția principală (__main__), se citesc datele de intrare și se verifică dacă respectă restricțiile impuse. Dacă da, se afișează mesajul "Datele sunt introduse corect." și se calculează suma pentru fiecare pereche de indici. Dacă nu, se afișează mesajul "Datele nu corespund restricțiilor impuse.".

@@ Line 8: / Line 8: @@
 == 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.
+Fişierul de ieşire secvente.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 25: @@
 : 6 10
 ; Ieșire
+: Datele nu corespund restricțiilor impuse.
+: Datele sunt introduse correct
 : 13 19 23
@@ Line 30: / Line 34: @@
 # 0304 - Secvente
-def citeste_date_intrare():
+def citire_date():
      n = int(input())
-     sir = []
+     v = list(map(int, input().split()))
-     for i in range(n):
+    m = int(input())
-         sir.append(int(input()))
+    perechi = []
-     return sir
+     for i in range(m):
+         a, b = map(int, input().split())
+        perechi.append((a, b))
+     return n, v, m, perechi
-def numara_secvente_crescatoare(sir):
+def suma_secventa(n, v, a, b):
-     numar_secvente = 0
+     suma = 0
-    lungime_maxima = 1
+     for i in range(a-1, b):
-    lungime_curenta = 1
+         suma += v[i]
-     for i in range(1, len(sir)):
+     return suma
-         if sir[i] >= sir[i-1]:
-            lungime_curenta += 1
-        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
+     n, v, m, perechi = citire_date()
-    assert numar_secvente >= 0
+     if 1 <= n <= 100 and 1 <= m <= 100:
+        print("Datele sunt introduse corect.")
-if __name__ == "__main__":
+        for a, b in perechi:
-     sir = citeste_date_intrare()
+            print(suma_secventa(n, v, a, b))
-     numar_secvente = numara_secvente_crescatoare(sir)
+     else:
-    valideaza(sir, numar_secvente)
+        print("Datele nu corespund restricțiilor impuse.")
-     print(numar_secvente)
 </syntaxhighlight>
 == Explicatie Rezolvare ==
-Funcția citeste_date_intrare primește datele de intrare de la tastatură și le returnează sub forma unei liste.
+Funcția citire_date citește datele de intrare din consolă și le returnează sub formă de tuplu.
+Funcția suma_secventa primește un vector v, un interval [a, b] și calculează suma elementelor din secvența din vectorul v care începe la poziția a și se termină la poziția b.
-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ă.
+În funcția principală (__main__), se citesc datele de intrare și se verifică dacă respectă restricțiile impuse. Dacă da, se afișează mesajul "Datele sunt introduse corect." și se calculează suma pentru fiecare pereche de indici. Dacă nu, se afișează mesajul "Datele nu corespund restricțiilor impuse.".
-Funcția valideaza verifică dacă datele de ieșire sunt valide.
-În blocul if __name__ == "__main__": citim datele de intrare, apelăm funcția numara_secvente_crescatoare și afișăm rezultatul.