1364 - produs3: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/1364/produs3 1364 - produs3] ---- == Cerinţa == Se dă un şir cu n numere naturale nenule care sunt divizibile doar cu numerele prime 2, 3 sau 5. Determinaţi numărul secvenţelor din şir pentru care produsul elementelor este pătrat perfect. == Date de intrare == Fișierul de intrare produs3.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule divizibile doar cu numerele prime 2, 3 sau 5, separate pr...
 
Flaviu (talk | contribs)
No edit summary
Line 10: Line 10:


== Date de ieșire ==  
== Date de ieșire ==  
Fișierul de ieșire produs3.out va conține pe prima linie numărul S, reprezentând numărul secvenţelor din şir pentru care produsul elementelor este pătrat perfect.
Fișierul de ieșire produs3.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 ==
== Restricţii şi precizări ==
Line 20: Line 22:
: 12 3 4 5 45
: 12 3 4 5 45
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele sunt introduse correct.
: 6
: 6


Line 53: Line 57:
             x //= 5
             x //= 5
         if x != 1:
         if x != 1:
            print("Numerele din sir nu sunt divizibile doar cu 2, 3 si 5!")
             return False
             return False
     return True
     return True
Line 60: Line 63:
     n, arr = read_input()
     n, arr = read_input()
     if validate(n, arr):
     if validate(n, arr):
        print("Datele sunt introduse corect.")
         print(solve(n, arr))
         print(solve(n, arr))
    else:
        print("Datele nu corespund restricțiilor impuse.")





Revision as of 14:45, 28 April 2023

Sursa: 1364 - produs3


Cerinţa

Se dă un şir cu n numere naturale nenule care sunt divizibile doar cu numerele prime 2, 3 sau 5. Determinaţi numărul secvenţelor din şir pentru care produsul elementelor este pătrat perfect.


Date de intrare

Fișierul de intrare produs3.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule divizibile doar cu numerele prime 2, 3 sau 5, separate prin spații.


Date de ieșire

Fișierul de ieșire produs3.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
  • numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu

Intrare
5
12 3 4 5 45
Ieșire
Datele nu corespund restricțiilor impuse.
Datele sunt introduse correct.
6

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 1364 - produs3

import math

def read_input():

   n = int(input())
   arr = list(map(int, input().split()))
   return n, arr

def solve(n, arr):

   cnt = 0
   for i in range(n):
       prod = 1
       for j in range(i, n):
           prod *= arr[j]
           if math.isqrt(prod) ** 2 == prod:
               cnt += 1
   return cnt

def validate(n, arr):

   for x in arr:
       while x % 2 == 0:
           x //= 2
       while x % 3 == 0:
           x //= 3
       while x % 5 == 0:
           x //= 5
       if x != 1:
           return False
   return True

if __name__ == '__main__':

   n, arr = read_input()
   if validate(n, arr):
       print("Datele sunt introduse corect.")
       print(solve(n, arr))
   else:
       print("Datele nu corespund restricțiilor impuse.")


</syntaxhighlight>

Explicatie Rezolvare

Funcția read_input() citește datele de intrare și le returnează sub forma unei perechi (n, arr), unde n este lungimea șirului, iar arr este un vector cu n elemente reprezentând șirul citit.

Funcția solve(n, arr) primește ca parametri lungimea n și vectorul arr și calculează numărul de subșiruri cu produsul elementelor pătrat perfect. Pentru fiecare poziție i din șir, se calculează produsul elementelor de la poziția i până la sfârșitul șirului, iar pentru fiecare astfel de produs se verifică dacă este pătrat perfect. Dacă da, se incrementează un contor cnt și se trece la următoarea poziție. La final, se returnează valoarea contorului.

Funcția validate(n, arr) primește ca parametri lungimea n și vectorul arr și verifică dacă toate numerele din arr sunt divizibile doar cu 2, 3 sau 5. Pentru fiecare număr, se împarte succesiv la 2, 3 și 5 cât timp este posibil, iar dacă rămâne un rest nenul, se afișează un mesaj de eroare și se returnează False. Altfel, se returnează True.

În cadrul blocului if __name__ == '__main__':, se citesc datele de intrare folosind read_input(). Apoi, se validează datele folosind validate(). Dacă datele sunt valide, se calculează răspunsul folosind solve() și se afișează pe ecran.