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 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

# 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)

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.