2366 - Masterpiece 001

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

Rezolvare

<syntaxhighlight lang="python" line="1">

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.