1350 - produs2

Sursa: 1350 - produs2

---

Cerinţa

Se dă un şir cu n numere naturale nenule. Aflaţi câte secvenţe din şir au produsul mai mic decât un număr natural p dat.

Date de intrare

Fișierul de intrare produs2.in conține pe prima linie numerele n şi p, iar pe a doua linie n numere naturale nenule separate prin spații, reprezentând elementele şirului.

Date de ieșire

Fișierul de ieșire produs2.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 ≤ 1.000.000
• 1 < p ≤ 2.000.000.000
• numerele din şir vor fi mai mici decât 1.000

Exemplu

Intrare

5 10

1 2 3 4 2

Ieșire

Datele nu corespund restricțiilor impuse.

Datele sunt introduse correct.

9

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 1350 - produs2

def citire():

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

def rezolvare(n, p, a):

   cnt = 0
   produs = 1
   j = 0
   for i in range(n):
       while j < n and produs * a[j] < p:
           produs *= a[j]
           j += 1
       cnt += j - i
       produs //= a[i]
   return cnt

def validare(cnt):

   with open("produs2.out") as f:
       rezultat_corect = int(f.read().strip())
   if cnt == rezultat_corect:
       print("Datele sunt introduse corect.")
   else:
       print("Datele nu corespund restricțiilor impuse.")

if __name__ == "__main__":

   n, p, a = citire()
   cnt = rezolvare(n, p, a)
   print(cnt)
   validare(cnt)

</syntaxhighlight>

Explicatie Rezolvare

Funcția citire citește datele de intrare de la tastatură și le returnează sub formă de tuplu.

Funcția rezolvare parcurge șirul a și pentru fiecare poziție i calculează câte secvențe care încep în i au produsul mai mic decât p. Pentru a face aceasta, se folosește o variabilă produs care ține produsul elementelor din secvență și un indice j care indică poziția până la care s-a mers cu secvența curentă. În fiecare iterație se avansează indicele j cât timp produsul secvenței nu depășește p, apoi se adaugă numărul de secvențe care încep în i (adică j - i) la numărul total de secvențe cnt. Se împărțește produsul de la începutul secvenței la elementul curent pentru a calcula produsul secvenței următoare.

Funcția validare verifică dacă rezultatul obținut este același cu cel din fișierul de ieșire.