UniLecs137.py

# UniLecs 137
# Задача: дано натуральное число N. Необходимо найти наименьшее натуральное
# число, в ктр произведение его цифр было бы равно N. Если такого числа не
# существует, вывести -1.
# Входные данные: N - натуральное число от 1 до 10^9.
# Вывод: наименьшее натуральное число, произведение цифр ктр было
# бы равно N. -1 - если такого числа нет.
# Пример:
# N = 11; Answer = -1
# N = 12; Answer = 26
# N = 14; Answer = 27

# Первый вариант. Сначала разбиваем число на простые множители-цифры (2,3,5,7)
# Потом комбинируем множители в наиболее эффективные комбинации
def genddivs(N):
    # Генерирует разбиение числа на простые числа = цифры
    # Последним в список добавляется неделимый остаток
    # Это может быть 1, если N разлагается на простые множители [2,3,5,7]
    primedig = [2,3,5,7]
    # Сюда будем складывать разложение
    divs = []
    # Тут храним остаток делений
    rest = N
    # Бежим по всем простым делителям
    for p in primedig:
        # Дадим цифре шанс!
        divp = True
        while divp:
            # Если текущий остаток делится на цифру без остатка -- записываем цифру в разложение и даём ещё один шанс 
            if rest % p == 0: 
                divs.append(p)
                rest = rest / p
            else:
                # Иначе увы и ах! идём к следующей цифре 
                divp = False
    # Добавляем остсток к разложению и отдаём его
    divs.append(rest)
    return divs
    
def genmultiple(N):
    # Сгенерируем разлождение
    divs = genddivs(N)
    # Проверяем остаток разлождения -- на последней позиции в списке --
    # Если 1 -- отлично, иначе либо число простое (11), либо в остатке
    # осталось простое большее 9или их комбинация (например 66 => 2*3*11)  
    if (int(divs[-1]) > 1):
        return -1
    # Упрощаем в порядке уменьшения ценности
    # 9 = 3x3
    # 8 = 2x2x2
    # 6 = 2x3
    # 4 = 2x2
    # Сколько к нас троек?    
    uc = divs.count(3)        
    if uc > 2:    # Если больше 2 -- заменяем каждую двойку троек девяткой
        uci = divs.index(3)
        n9 = uc // 2
        divs = divs[:uci] + divs[(uci+n9*2):] + n9*[9][:]
    # Сколько к нас двоек?    
    iki = divs.count(2)
    if iki >= 3:  # Если больше 3 -- заменяем каждую тройку двое восьмёркой
        ikii = divs.index(2)
        n8 = iki // 3
        divs = divs[:ikii] + divs[(ikii+n8*3):] + n8*[8][:]

    # Сколько к нас троек?    
    uc = divs.count(3)
    # Сколько к нас двоек?    
    iki = divs.count(2)
    # Если у нас есть двойка и тройка -- заменяем их шестёркой
    if (uc>0) & (iki>0):
        uci = divs.index(3)
        ikii = divs.index(2)
        divs[ikii]=6
        del(divs[uci])
    # Если у нас есть две двойки -- заменяем их четвёркой. Все другие комбинации двоек обработаны раньше    
    if divs.count(2) == 2:
        divs[divs.index(2)]=4
        del(divs[divs.index(2)])
    # Сортируем массив, чтобы большие делители заняли низшие разряды, потом конвертируем список в число
    divs.sort()
    # map(str, divs) конвертирует элементы в строки, divs[1:] нужно чтобы убьрать единичку-множитель,
    # ''.join слепляет в строку с разделителем '', int конвертирует полученную строку в число 
    result = int(''.join(map(str, divs[1:])))    
    return result

# Вариант 2. Чтобы не мучиться с заменой комбинаций множителей на втором этапе
# просто ищем их в оптимальном порядке: 9(3x3) > 8 (2x2x2) > 6 (2x3) > 4 (2x2) > 3 > 2, остальное (5, 7) неважно, ибо не комбинируется  
def genmultiple_v2(N, verbose = False):
    # оптимальный порядок делителей
    # 9(3x3) > 8 (2x2x2) > 6 (2x3) > 4 (2x2) > 3 > 2, остальное неважно, ибо не комбинируется  
    primedig = [9,8,6,4,3,2,5,7]
    # Сюда будем складывать разложение
    divs = []
    # Тут храним остаток делений
    rest = N
    if verbose:
        print("Сейчас мы будем разлагать число {} на делители в оптимальном порядке".format(N))
    # Бежим по всем простым делителям
    for p in primedig:
        if verbose:
            print("Пробуем деление на {}".format(p))
        # Дадим цифре шанс!
        divp = True
        while divp:
            # Если текущий остаток делится на цифру без остатка -- записываем цифру в разложение и даём ещё один шанс 
            if rest % p == 0:
                divs.append(p)
                rest = rest / p
                if verbose:
                    print("  делится на {}, в остаток идёт {}".format(p,rest))
            else:
                # Иначе увы и ах! идём к следующей цифре 
                divp = False
     
    # Проверяем остаток разлождения. Если 1 -- отлично, иначе либо число простое (11), либо в остатке
    # осталось простое большее 9 или их комбинация (например 66 => 2*3*11)
    if verbose:
        print("В остатке {}".format(rest))
    if (rest>1):
        if verbose:
            print("Не смогли разложить число {} на цифры-делители, в остатке {}, так что -1".format(N, rest))
        return -1
    # Соритируем массив, чтобы большие делители заняли низшие разряды, потом конвертируем список в число
    divs.sort() 
    # map(str, divs) конвертирует элементы в строки, ''.join слепляет в строку с разделителем '',
    # int конвертирует полученную строку в число 
    result = int(''.join(map(str, divs)))
    if verbose:
        print("Всё получилось! Произведение цифр числа {} равно {} = {}".format(result, multlist(divs), N))
    return result

def multlist(list):
    r = 1
    for x in list:
        r *= x
    return r

    
print(genmultiple(11))
print(genmultiple(12))
print(genmultiple(14))
print(genmultiple(21600))
print(genmultiple(1000000000))
#21600 -> 255689
print(genmultiple_v2(11))
print(genmultiple_v2(12))
print(genmultiple_v2(14))
print(genmultiple_v2(21600))
print(genmultiple_v2(21600, True))
print(genmultiple_v2(1000000000))