Sovago Rares-Andrei: Pagină nouă: == Cerinţa == Se dă un șir de n numere naturale nenule '''v = {v1 , v2 , v3 ... vn }'''. Se formează șirul '''d = {d1 , d2 , d3 ... dn }''' unde '''di''' = numărul divizorilor lui vi . Notăm '''max''' = cea mai mare valoare din șirul '''d'''. Să se afișeze în ordine crescătoare toate numerele din șirul dat '''v''' care au exact '''max''' divizori. Dacă un număr '''vi''' apare de mai multe ori în șirul '''v''' și numărul divizorilor lui '''vi''' este eg...

2023-04-06T12:24:05Z

Pagină nouă: == Cerinţa == Se dă un șir de n numere naturale nenule '''v = {v1 , v2 , v3 ... vn }'''. Se formează șirul '''d = {d1 , d2 , d3 ... dn }''' unde '''di''' = numărul divizorilor lui vi . Notăm '''max''' = cea mai mare valoare din șirul '''d'''. Să se afișeze în ordine crescătoare toate numerele din șirul dat '''v''' care au exact '''max''' divizori. Dacă un număr '''vi''' apare de mai multe ori în șirul '''v''' și numărul divizorilor lui '''vi''' este eg...

New page

== Cerinţa ==
Se dă un șir de n numere naturale nenule '''v = {v1 , v2 , v3 ... vn }'''.

Se formează șirul '''d = {d1 , d2 , d3 ... dn }''' unde '''di''' = numărul divizorilor lui vi .

Notăm '''max''' = cea mai mare valoare din șirul '''d'''.

Să se afișeze în ordine crescătoare toate numerele din șirul dat '''v''' care au exact '''max''' divizori. Dacă un număr '''vi''' apare de mai multe ori în șirul '''v''' și numărul divizorilor lui '''vi''' este egal cu '''max''', atunci '''vi''' se va afișa o singură dată.
== Date de intrare ==
Fișierul de intrare '''masterpiece001.in''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere naturale nenule separate prin spații.
== Date de ieșire ==
Dacă datele sunt introduse corect, pe ecran:
"Datele sunt introduse corect.",fișierul de ieșire '''masterpiece001.out''' va conține numerele din șirul dat '''v''' care au exact max divizori, în ordine crescătoare, separate prin spații. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".
== Restricţii şi precizări ==
*1 ≤ n ≤ m ≤ 1.000.000
*numerele de pe a doua linie a fișierului de intrare vor fi mai mici sau egale cu 400.000
== Exemple ==
===Exemplul 1===
; ''masterpiece001.in''
:10
:12 3 12 4 12 18 31 101 31 31
; ''ecran''
:Datele sunt introduse corect.
; ''masterpiece001.out''
:12 18
===Exemplul 2===
; ''memory009.in''
:5
:2 3 5 7 11
; ''ecran''
:Datele sunt introduse corect.
; ''memory009.out''
:2 3 5 7 11
===Exemplul 3===
; ''memory009.in''
:6
:2 3 5 7 11 500000
; ''ecran''
:Datele nu corespund restricțiilor impuse.
; ''memory009.out''
:
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 2366 - Masterpiece 001
import sys

def validare(n, lista):
if n < 1 or n > 1000000 or any(x < 1 or x > 400000 for x in lista):
print("Datele nu corespund restricțiilor impuse.")
sys.exit(0)
return True
def nrdiv(n):
d, cnt, d2 = 2, 1, 0
while n % 2 == 0:
d2 += 1
n //= 2
cnt = d2 + 1
d = 3
while n > 1:
p = 0
while n % d == 0:
n //= d
p += 1
if p > 0:
cnt *= (p + 1)
d += 2
if d * d > n:
d = n
return cnt

def rezolvare(n, lista):
a = [False] * 400001
nrmaxdiv = 0
nrmin = 400000
nrmax = 0
for i in range(n):
x = lista[i]
if x > 400000:
continue
a[x] = True
if x < nrmin:
nrmin = x
if x > nrmax:
nrmax = x
for y in range(nrmin, nrmax + 1):
if a[y]:
nd = nrdiv(y)
if nd > nrmaxdiv:
nrmaxdiv = nd
nrmin = y
elif nd == nrmaxdiv:
nrmax = y
result = []
for i in range(nrmin, nrmax + 1):
if a[i] and nrdiv(i) == nrmaxdiv:
result.append(i)
return result

if __name__ == '__main__':
n, lista = 0, []
with open('masterpiece001.in', 'r') as fin:
n = int(fin.readline())
lista = [int(x) for x in fin.readline().split()]
if validare(n, lista):
result = rezolvare(n, lista)
with open('masterpiece001.out', 'w') as fout:
for x in result:
fout.write(str(x) + ' ')
fout.write('\n')
print("Datele sunt introduse corect.")
else:
print("Datele nu corespund restricțiilor impuse.")

</syntaxhighlight>

==Explicatie==

validare(n, lista): Aceasta functie are rolul de a verifica daca datele de intrare respecta restrictiile impuse. Functia primeste ca parametri n, numarul de elemente din lista, si lista, o lista de numere. Daca numarul de elemente n nu se afla in intervalul [1, 1000000] sau daca exista cel putin un element din lista care nu se afla in intervalul [1, 400000], functia afiseaza mesajul "Datele nu corespund restricțiilor impuse." si iese din program cu sys.exit(0). In caz contrar, functia returneaza valoarea True.

nrdiv(n): Aceasta functie calculeaza numarul de divizori ai unui numar dat. Functia primeste ca parametru n, numarul pentru care se calculeaza numarul de divizori. Algoritmul folosit este bazat pe factorizarea lui n in factori primi si calcularea numarului de divizori in functie de exponentii lor. Functia returneaza numarul de divizori ai lui n.

rezolvare(n, lista): Aceasta functie rezolva problema data, adica determina numerele din lista care au exact numarul maxim de divizori si le returneaza intr-o lista sortata in ordine crescatoare. Functia primeste ca parametri n, numarul de elemente din lista, si lista, o lista de numere. Pentru fiecare numar x din lista care se afla in intervalul [1, 400000], se calculeaza numarul de divizori nd folosind functia nrdiv(), si se retine numarul minim nrmin si numarul maxim nrmax din lista. Dupa aceea, se parcurg numerele din intervalul [nrmin, nrmax] si se calculeaza numarul de divizori pentru fiecare numar y care apare in lista. Daca numarul de divizori este mai mare decat nrmaxdiv, se actualizeaza nrmaxdiv si se retine numarul minim nrmin. Daca numarul de divizori este egal cu nrmaxdiv, se actualizeaza numarul maxim nrmax. In final, se parcurg din nou numerele din intervalul [nrmin, nrmax] si se adauga in lista result numerele care au exact numarul maxim de divizori. Functia returneaza lista result.

2366 - Masterpiece 001 - Revision history