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

Datele sunt introduse correct.

produs2.out

9

Exemplu 2

Intrare

produs2.in

1 2 3 4 5

21 57 44 90

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

# 1350 - produs2

def validate_input(n, p, arr):
    if not (1 <= n <= 1000000):
        return False
    if not (1 < p <= 2000000000):
        return False
    if len(arr) != n:
        return False
    if any(num >= 1000 for num in arr):
        return False
    return True


def count_sequences(n, p, arr):
    if not validate_input(n, p, arr):
        return "Datele nu corespund restricțiilor impuse."

    count = 0
    product = 1

    for i in range(n):
        product *= arr[i]

        if product < p:
            count += 1
        else:
            product //= arr[i - count]
            count -= 1

    return count


if __name__ == "__main__":
    file_name = "produs2.in"
    with open(file_name, "r") as file:
        n, p = map(int, file.readline().split())
        arr = list(map(int, file.readline().split()))

    result = count_sequences(n, p, arr)
    print(result)

Explicatie Rezolvare

Funcția validate_input(n, p, arr):

Această funcție primește trei parametri: n - numărul de elemente din șir, p - limita produsului și arr - lista de numere. Verifică dacă valorile n și p se încadrează în intervalele valide specificate în cerință și dacă lungimea listei arr este egală cu n. Verifică, de asemenea, dacă există vreun număr din lista arr care este mai mare sau egal cu 1000. Dacă da, se returnează False, semnalând că datele nu corespund restricțiilor impuse. Dacă toate verificările sunt trecute cu succes, înseamnă că datele de intrare sunt valide, astfel că se returnează True. Funcția count_sequences(n, p, arr):

Această funcție primește trei parametri: n - numărul de elemente din șir, p - limita produsului și arr - lista de numere. Verifică mai întâi validitatea datelor de intrare folosind funcția validate_input(n, p, arr). Dacă datele nu sunt valide, returnează un mesaj corespunzător. Inițializează variabila count cu valoarea 0, care va fi utilizată pentru a număra secvențele cu produs mai mic decât p. Inițializează variabila product cu valoarea 1, care reprezintă produsul curent al secvenței. Parcurge lista arr și în fiecare pas înmulțește product cu elementul curent. Functia if __name__ == '__main__' se dechisde fisierul din care se citesc datele pentru a se rezolva problema