1839 - Memory006: Difference between revisions

Revision as of 18:47, 27 April 2023

Cerinţa

Se dă un şir format din n numere naturale nenule. Să se afle numărul secvenţelor din şir care au produsul elementelor egal cu 2k, unde k este un număr natural dat.

Date de intrare

Fișierul de intrare memory006.in 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.".

Date de ieșire

Fișierul de ieșire memory006.out va conține pe prima linie numărul S, reprezentând numărul secvenţelor din şir care au produsul elementelor egal cu 2k.

Restricţii şi precizări

1 ≤ n ≤ 500.000
1 ≤ k ≤ 10.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mari decât 1 şi mai mici decât 10^18

Exemplu

Intrare: 5 3; 7 4 2 4 5
Ieșire: Datele nu corespund restricțiilor impuse.; Datele sunt introduse correct; 2

Rezolvare

Rezolvare ver. 1

1839 - Memory006

def citire_date():

   n = int(input())
   v = list(map(int, input().split()))
   return n, v

def secvmax(n, v):

   st = dr = st_max = dr_max = suma_max = suma = 0
   for i in range(n):
       if v[i] % 2 == 0:
           suma += v[i]
           dr = i
           if suma > suma_max or (suma == suma_max and dr - st > dr_max - st_max):
               suma_max = suma
               st_max = st
               dr_max = dr
       else:
           suma = 0
           st = i + 1
   return st_max + 1, dr_max + 1

def validare(n, v):

   if len(v) != n:
       return False
   for x in v:
       if x < 1 or x > 10**18:
           return False
   return True

if __name__ == '__main__':

   n, v = citire_date()
   if validare(n, v):
       st, dr = secvmax(n, v)
       print("Datele sunt introduse corect.")
       print(st, dr)
   else:
       print("Datele nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicatie Rezolvare

Funcția citeste_date_intrare citește numerele n și k de pe prima linie a fișierului de intrare, apoi citește sirul de n numere de pe a doua linie și le returnează sub formă de tuplu (n, k, sir). Funcția numara_secvente primește numerele n, k și sirul sir și returnează numărul de secvențe ale sir care au produsul egal cu 2 ** k. Pentru a număra secvențele cu produsul egal cu 2 ** k, vom parcurge sirul de la stânga la dreapta și vom menține un produs curent inițial egal cu 1 și un număr de secvențe inițial egal cu 0. La fiecare pas, vom înmulți produsul curent

@@ Line 6: / Line 6: @@
 == Date de intrare ==
-Fișierul de intrare memory006.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule, separate prin spații.
+Fișierul de intrare memory006.in 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."'''.
@@ Line 21: / Line 23: @@
 : 7 4 2 4 5
 ; Ieșire
+: Datele nu corespund restricțiilor impuse.
+: Datele sunt introduse correct
 : 2
@@ Line 28: / Line 32: @@
 # 1839 - Memory006
-def citeste_date_intrare():
+def citire_date():
-     # Citeste n si k
+     n = int(input())
-     n, k = map(int, input().split())
+     v = list(map(int, input().split()))
+    return n, v
-    # Citeste sirul de n numere
+def secvmax(n, v):
-    sir = list(map(int, input().split()))
+     st = dr = st_max = dr_max = suma_max = suma = 0
-    return n, k, sir
-def numara_secvente(n, k, sir):
-     # Initializeaza numarul de secvente cu produsul 2k la 0
-    nr_secvente = 0
-    # Initializeaza produsul curent la 1
-    produs = 1
-    # Parcurge sirul de la stanga la dreapta
      for i in range(n):
-         # Inmulteste produsul curent cu elementul curent din sir
+         if v[i] % 2 == 0:
-        produs *= sir[i]
+            suma += v[i]
+            dr = i
+            if suma > suma_max or (suma == suma_max and dr - st > dr_max - st_max):
+                suma_max = suma
+                st_max = st
+                dr_max = dr
+        else:
+            suma = 0
+            st = i + 1
+    return st_max + 1, dr_max + 1
-        # Cat timp produsul este mai mare decat 2k, imparte produsul la primul element din sir
+def validare(n, v):
-        # si avanseaza indicele de inceput al secventei cu 1
+     if len(v) != n:
-        while produs > (2 ** k):
-            produs //= sir[i - nr_secvente]
-            nr_secvente += 1
-        # Daca produsul este egal cu 2k, incrementeaza numarul de secvente cu produsul 2k
-        if produs == (2 ** k):
-            nr_secvente += 1
-    return nr_secvente
-def valideaza_date(n, k, sir):
-    # Verifica daca n si k sunt in limitele impuse
-     if not (1 <= n <= 500000 and 1 <= k <= 10000):
          return False
+     for x in v:
-     # Verifica daca sirul contine n numere naturale nenule
+        if x < 1 or x > 10**18:
-    if not all(1 <= x <= 10**18 for x in sir):
+            return False
-        return False
      return True
 if __name__ == '__main__':
-    # Citeste datele de intrare
+     n, v = citire_date()
-     n, k, sir = citeste_date_intrare()
+     if validare(n, v):
+        st, dr = secvmax(n, v)
-    # Valideaza datele de intrare
+         print("Datele sunt introduse corect.")
-     if not valideaza_date(n, k, sir):
+        print(st, dr)
-         print("Date de intrare invalide")
      else:
-         # Numara secventele cu produsul 2k
+         print("Datele nu corespund restricțiilor impuse.")
-        nr_secvente = numara_secvente(n, k, sir)
-        # Afiseaza numarul de secvente
-        print(nr_secvente)