1350 - produs2: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 25: Line 25:
: 1 2 3 4 2
: 1 2 3 4 2
; Ieșire
; Ieșire
: Datele sunt introduse correct.
: produs2.out
: produs2.out
: Datele sunt introduse correct.
: 9
: 9
== Exemplu 2 ==
== Exemplu 2 ==
Line 34: Line 34:
: 21 57 44 90
: 21 57 44 90
; Ieșire
; Ieșire
: produs2.out
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.


Line 42: Line 41:
# 1350 - produs2
# 1350 - produs2


def citire():
def validate_input(n, p, arr):
     n, p = map(int, input().split())
     if not (1 <= n <= 1000000):
     a = list(map(int, input().split()))
        return False
     return n, p, a
    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


def rezolvare(n, p, a):
    cnt = 0
    produs = 1
    j = 0
     for i in range(n):
     for i in range(n):
         while j < n and produs * a[j] < p:
         product *= arr[i]
            produs *= a[j]
            j += 1
        cnt += j - i
        produs //= a[i]
    return cnt


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


def validare(cnt):
     return count
     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__":
if __name__ == "__main__":
     n, p, a = citire()
     file_name = "produs2.in"
     cnt = rezolvare(n, p, a)
    with open(file_name, "r") as file:
     print(cnt)
        n, p = map(int, file.readline().split())
    validare(cnt)
        arr = list(map(int, file.readline().split()))
 
     result = count_sequences(n, p, arr)
     print(result)




</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Funcția citire citește datele de intrare de la tastatură și le returnează sub formă de tuplu.
Funcția validate_input(n, p, arr):


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.
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):


Funcția validare verifică dacă rezultatul obținut este același cu cel din fișierul de ieșire.
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.
Verifică dacă product este mai mic decât p. Dacă da, înseamn

Revision as of 21:23, 14 May 2023

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

<syntaxhighlight lang="python" line>

  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)


</syntaxhighlight>

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. Verifică dacă product este mai mic decât p. Dacă da, înseamn