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

 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) + " ")

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.