1 Тема от aza_inf Отредактировано aza_inf (2010-05-29 08:10:49)

  • aza_inf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-30
  • Сообщений: 78

Тема: Произведение цифр

Требуется найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N.

Входные данные

В единственной строке входного файла INPUT.TXT записано одно целое число N (0 ? N ? 10^9).

Выходные данные

В выходной файл OUTPUT.TXT нужно вывести искомое число Q. В том случае, если такого числа не существует, следует вывести -1.

Примеры

№    INPUT.TXT    OUTPUT.TXT
1    10                     25
2    13                      -1
3    90                      259

who can solve this problem?

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Произведение цифр

Разложим N на простые множители. Если есть хоть один множитель больший 9, ответ -1.
Предположим, что у нас встречаются только множители 2 3 5 7. С 5 и 7 ничего сделать нельзя - они так и пойдут отдельными цифрами. Значит, нам нужно минимизировать количество цифр, составленных из 2 и 3, а при равном количестве минимизировать число, составленное из этих цифр в порядке возрастания. Пока двоек больше трех, комбинируем их в восьмерки. Пока троек больше одной, комбинируем их в девятки. Пока двоек больше одной, комбинируем их в четверки. Если остались и 2 и 3, делаем шестерку, иначе просто добавляем то что осталось к ответу. Затем сортируем в порядке возрастания все полученные цифры и выводим ответ.

3 Ответ от 2rf

  • 2rf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-14
  • Сообщений: 42

Re: Произведение цифр

Кажется, что можно просто делить сначала на 9 пока делится, потом на 8, 7, ..., 2. Если в конце осталось не 1, то ответа нет. Иначе выводим то, на что делили, в обратном порядке. И плюс N=0 и N=1 разобрать отдельно.

4 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Произведение цифр

Да, наверное это тоже будет правильно smile Когда-то на топкодере было что-то такое и я тогда тоже все факторизировал и комбинировал простые множители вместо того чтобы просто делить на 9,8,...,2.