1608 - Sortare Divizori

Cerinţa

Se dau n numere naturale nenule. Ordonați descrescător cele n numere după numărul lor de divizori.

Date de intrare

Fișierul de intrare sortare_divizori.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire sortare_divizori.out va conține cele n numere aflate pe a doua linie a fișierului de intrare ordonate descrescător după numărul de divizori.

Restricţii şi precizări

• 1 ≤ n ⩽ 1.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
• dacă există mai multe numere care au același număr de divizori, acestea vor fi ordonate crescător

Exemplu 1

sortare_divizori.in

5

12 20 4 100 13

sortare_divizori.out

100 12 20 4 13

Rezolvare

<syntaxhighlight lang="python" line>

def numar_divizori(numar):
   divizori = 0
   for i in range(1, numar + 1):
       if numar % i == 0:
           divizori += 1
   return divizori

if __name__ == "__main__":

   # Citim numărul n și lista de numere din fișierul de intrare
   with open("sortare_divizori.in", "r") as f:
       n = int(f.readline().strip())
       numere = list(map(int, f.readline().strip().split()))

   # Verificăm restricțiile impuse pentru numere
   numere = [numar for numar in numere if numar < 1000000000]

   # Calculăm numărul de divizori pentru fiecare număr și sortăm numerele în ordine descrescătoare după numărul de divizori,
   # iar în caz de egalitate, sortăm crescător
   numere.sort(key=lambda x: (numar_divizori(x), -x), reverse=True)

   # Scriem rezultatul în fișierul de ieșire
   with open("sortare_divizori.out", "w") as f:
       for numar in numere:
           f.write(str(numar) + " ")

</syntaxhighlight>

Explicație

12 are 6 divizori, 20 are 6 divizori, 4 are 3 divizori, 100 are 9 divizori, 13 are 2 divizori, 12 și 20 au același număr de divizori. Așadar ordinea va fi 100 12 20 4 13.