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

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

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.