Unilecs #137. Multiplication of digits

disc.txt

Задача: дано натуральное число N. Необходимо найти наименьшее натуральное число, в ктр произведение его цифр было бы равно N. Если такого числа не существует, вывести -1.

Входные данные: N - натуральное число от 1 до 10^9.

Вывод: наименьшее натуральное число, произведение цифр ктр было бы равно N. -1 - если такого числа нет.

Пример:

N = 11; Answer = -1

N = 12; Answer = 26

N = 14; Answer = 27

task137.cpp

#include <iostream>
#include <cmath>

/*
  В целом это почти то же самое, что и на питоне.
  Используется тот же самый алгоритм.
  Незначительные различия с кодом на питоне упомянуты на месте.
*/

int main()
{
  int n;
  scanf("%d", &n);
  if (n <= 1)
  {
    printf("%d\n", -1);
    return 0;
  }
  int dividers[8] = {0};
  int devider, edge;
  edge = (int)ceil(sqrt(n));
  devider = 2;
  /*
    Ниже тот же самый алгоритм факторизации,
    только тут корень вычесляется один раз,
    а не на каждой итерации.
  */
  while (devider <= edge && n > 1)
  {
    if (devider > 7)
      // Если делитель >7 то он не однозначный
    {
      printf("%d\n", -1);
      return 0;
    }
    while (n % devider == 0)
    {
      dividers[devider-2]++;
      n /= devider;
    }
    devider++;
  }
  if (n <= 7)
    dividers[n-2]++;
  else
  {
    printf("%d\n", -1);
    return 0;
  }

  /*
      На питоне используется словарь для хранения множителей.
      Тут массив с индексами от 0 до 7. Истинный делитель: индекс + 2
  */
  dividers[7] = dividers[1] / 2;
  dividers[1] %= 2;

  dividers[6] = dividers[0] / 3;
  dividers[0] %= 3;

  dividers[4] = std::min(dividers[0], dividers[1]);
  dividers[0] -= dividers[4];
  dividers[1] -= dividers[4];

  dividers[2] = dividers[0] / 2;
  dividers[0] %= 2;

  for (int i = 2; i <= 9; i++)
  {
    for (int j = 0; j < dividers[i-2]; j++)
      printf("%d", i);
  }
  putchar('\n');
  return 0;
}

task137.py

from isqrt.isqrt import isqrt

def factors(n):
    """
    Алгоритм факторизации числа n.
    Использована функция isqrt из pip для
    быстрого вычисления целой части квадратного корня.
    """
    while n > 1:
        for i in range(2, isqrt(n) + 1):
            if n % i == 0:
                n //= i
                yield i
                break
        else:
            if n > 1:
                yield n
                break
def task137(n: int):
    """
        Пусть n - введенное число.
        Пусть p - число, которое требуется составить.
        Подобную задачу можно свести к более строгому условию:
        необходимо найти такое сочетание цифр от 2 до 9, произведение
        которых даст какое-то определенное число n. Далее необходимо составить
        из найденных цифр минимально возможное число p.
        Я исключаю из этого диапазона 1 и 0, так как 1 результат произведения не
        изменит, а 0 - превратит его в 0. 
        По основной теореме арифметики есть только один способ
        разложить число на простые делители. Этим и воспользуемся:
        найдем простые делители числа n факторизацией и будем пробовать
        составить число p из этих простых чисел.
        Логично, что перемножение простых делителей числа n даст нам
        само число n, остается только определить, что если хотя бы один из простых
        делителей не однозначен (т.е двухзначен, трехзначен и т.д.) то
        по такому числу n число p составить невозможно.
        Таким образом, мы можем работать только с однозначными
        простыми делителями, т.е. только с делителями 2, 3, 5, 7 - это единственные
        однозначные простые числа.
        У нас есть определение случая, когда задача не решаема. Когда задача решаема,
        у нас есть набор простых однозначных чисел, из который надо составить число p.

        Всего у нас может получится 8 цифр в числе p:
        9 - 3*3
        8 - 2^3
        7 - есть изначально
        6 - 2*3
        5 - есть изначально
        4 - 2^2
        3 - есть изначально
        2 - есть изначально
        Наша задача сначала найти количество 9, потом 8, и т.д. от большего у меньшему.
        Изначально в цикле мы просто подсчитываем количество цифр 2,3,5,7.
        Далее, вычисляем количество 9: это количество пар троек (не забываем уменьшить кол-во троек)
        и так далее.
        Потом выводим в одну строчку все наши возможные цифры от меньшей к большей.
        Число p вычислено.
    """
    if n <= 1:
        return n
    nums = {}
    nums[9] = 0
    nums[8] = 0
    nums[7] = 0
    nums[6] = 0
    nums[5] = 0
    nums[4] = 0
    nums[3] = 0
    nums[2] = 0
    for factor in factors(n):
        if factor // 10 != 0:
            return -1
        nums[factor] += 1
        
    nums[9] = nums[3] // 2
    nums[3] %= 2

    nums[8] = nums[2] // 3
    nums[2] %= 3

    nums[6] = min(nums[2], nums[3])
    nums[2] -= nums[6]
    nums[3] -= nums[6]

    nums[4] = nums[2] // 2
    nums[2] %= 2
    result = ''
    for i in 2, 3, 4, 5, 6, 7, 8, 9:
        for _ in range(nums[i]):
            result += str(i)
    return int(result)

task137_unittest.py

import unittest
import task137

class Task317TestMethods(unittest.TestCase):
    def test(self):
        self.assertEqual(task137.task137(1), 1)
        self.assertEqual(task137.task137(2), 2)
        self.assertEqual(task137.task137(3), 3)
        self.assertEqual(task137.task137(4), 4)
        self.assertEqual(task137.task137(5), 5)
        self.assertEqual(task137.task137(6), 6)
        self.assertEqual(task137.task137(7), 7)
        self.assertEqual(task137.task137(8), 8)
        self.assertEqual(task137.task137(9), 9)
        self.assertEqual(task137.task137(10), 25)
        self.assertEqual(task137.task137(11), -1)
        self.assertEqual(task137.task137(12), 26)
        self.assertEqual(task137.task137(13), -1)
        self.assertEqual(task137.task137(14), 27)
        self.assertEqual(task137.task137(15), 35)
        self.assertEqual(task137.task137(16), 28)
        self.assertEqual(task137.task137(34), -1)
        self.assertEqual(task137.task137(100), 455)
        self.assertEqual(task137.task137(168), 378)
        self.assertEqual(task137.task137(216), 389)
        self.assertEqual(task137.task137(324), 499)
        self.assertEqual(task137.task137(330), -1)
        self.assertEqual(task137.task137(432), 689)
        self.assertEqual(task137.task137(648), 899)
        self.assertEqual(task137.task137(1000), 5558)
        self.assertEqual(task137.task137(2520), 5789)
        self.assertEqual(task137.task137(4212), -1)
        self.assertEqual(task137.task137(7350), 55677)
        self.assertEqual(task137.task137(21600), 255689)
        self.assertEqual(task137.task137(30240), 256789)
        self.assertEqual(task137.task137(1000000), 55555588)
if __name__ == '__main__':
    unittest.main()