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 S, reprezentând numărul secvenţelor din şir având produsul mai mic decât p, 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 1

Intrare

produs2.in

5 10

1 2 3 4 2

Ieșire

produs2.out

Datele sunt introduse correct.

9

Exemplu 2

Intrare

produs2.in

1 2 3 4 5

21 57 44 90

Ieșire

produs2.out

Datele nu corespund restricțiilor impuse.

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.