Editing 1350 - produs2

Sursa: [https://www.pbinfo.ro/probleme/1350/produs2 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 pe prima linie numărul S, reprezentând numărul secvenţelor din şir având produsul mai mic decât p.

== 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
: 9

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 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())
    assert cnt == rezultat_corect, f"rezultatul {cnt} nu este corect"


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.