3481 - Sort Div

Cerinţa

Se dau n numere naturale. Să se afișeze acestea în ordinea crescătoare a numărului de divizori ai fiecăruia, la același număr de divizori crescător după cifra de control, la aceeași cifră de control crescător după prima cifră, iar dacă și prima cifră este aceeași atunci numerele se vor afișa în ordinea crescătoare a valorii lor.

Date de intrare

Fișierul de intrare sort_div.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieşire

Fișierul de ieșire sort_div.out va conține pe prima linie cele n numere separate prin câte un spațiu, ordonate crescător pe baza criteriilor din enunț.

Restricții și precizări

• 1 ⩽ n ⩽ 10000
• numerele de pe a doua linie a fișierului de intrare vor fi distincte și mai mici decât 1.000.000
• cifra de control a unui număr se obţine efectuând suma cifrelor sale, apoi suma cifrelor acestei sume etc. până se obţine o sumă formată dintr-o singură cifră. De exemplu, cifra de control a numărului 645 este 6. (6+4+5=15, 1+5=6)

Exemplu

sort_div.in

5

6 8 3 10 5

sort_div.out

3 5 10 6 8

Explicaţii

3 și 5 au ambele 2 divizori, deci se afișează în ordine crescătoare după cifra de control. La fel și 6, 8 și 10 care au fiecare câte 4 divizori.

Rezolvare

# Funcția numar_divizori calculează numărul de divizori ai unui număr.
def numar_divizori(n):
    count = 0
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            if n / i == i:
                count += 1
            else:
                count += 2
    return count

# Funcția cifra_de_control calculează cifra de control a unui număr.
def cifra_control(n):
    while n > 9:
        n = sum(int(digit) for digit in str(n))
    return n

# Funcția sortare sortează lista de numere în funcție de criteriile specificate.
def sortare(n, numere):
    numere.sort(key=lambda x: (numar_divizori(x), cifra_control(x), int(str(x)[0]), x))

# Funcția citire citește datele de intrare din fișierul sort_div.in.
def citire():
    with open('sort_div.in', 'r') as f:
        n = int(f.readline().strip())
        numere = list(map(int, f.readline().split()))
    return n, numere

# Funcția scriere scrie rezultatele în fișierul sort_div.out.
def scriere(n, numere):
    with open('sort_div.out', 'w') as f:
        f.write(' '.join(map(str, numere)))

# Citim datele de intrare din fișierul sort_div.in.
n, numere = citire()
# Sortăm lista de numere în funcție de criteriile specificate.
sortare(n, numere)
# Scriem rezultatele în fișierul sort_div.out.
scriere(n, numere)