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

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 8 мес., 2 нед. назад.

  • Автор
    Сообщения
  • #4618
    @admin

    Задача взята с acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 42%)

    Задача на внимательность.

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

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

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

    Пример 1:
    INPUT.TXT: 10
    OUTPUT.TXT : 25

    Пример 2:
    INPUT.TXT: 13
    OUTPUT.TXT : -1

    Пример 3:
    INPUT.TXT: 90
    OUTPUT.TXT : 259

    Итак, от нас требуют найти минимальное число, произведение цифр которого равно заданному значению. Первая мысль, которая может возникнуть — перебирать числа в порядке возрастания, делить их на цифры и перемножать. Однако, с учетом допустимых диапазонов входных данных — работать это будет слишком долго.

    На самом деле, в задаче есть смысл стараться подобрать делители числа N. Можно заметить, что если число делится на 8 — то его делителями будут также 2 и 4, однако, 2 разряда дадут однозначно большее число, чем один (8 < 24). Поэтому по возможности надо выбирать как можно большие цифры. Тогда логика решения заключается в том, чтобы делить число на 9 пока делится нацело и считать число девяток, потом на 8 и т.д. Если в результате такой операции получается единица - вывод осуществляется в обратном порядке (от двойки к девятке выводится количество цифр). Если же единицу получить не удалось - выводим -1 (искомого Q не существует). Дальше остается только учесть все детали. Первое - допустимым значением является ноль, но для такого значения наш алгоритм зациклится - его необходимо обработать отдельно. Кроме того, минимальным натуральным числом, таким, что произведение его цифр равно нулю является 10 (вычислить такое значение никак не получилось бы без перебора). Другая проблема - если исходное число равно единице. По описанному выше алгоритму мы продолжаем делить число на цифры пока не получим единицу, но если мы получили ее сразу - то у нас нет ни одной цифры и в файл мы ничего не выведем. Поэтому такой случай также стоит обработать отдельно. Итак, финальный исходный код программы мог бы выглядеть следующим образом:

    #include <fstream>
    #include <algorithm>
    using namespace std;
    
    int main() {
      ifstream ifst("input.txt");
      ofstream ofst("output.txt");
      
      long long n;
      unsigned long long digits[10];
      ifst >> n;
      
      if (0 == n) {
        ofst << 10;
        return 0;
      }
      
      if (1 == n) {
        ofst << 1;
        return 0;
      }
    
      for (int i = 9; i > 1; --i) {
        digits[i] = 0;
        while (n%i == 0) {
          n/=i;
          digits[i]++;
        }
      }
    
      if (n == 1) {
        for (int i = 2; i <= 9; ++i) {
          while (digits[i]) {
            digits[i]--;
            ofst << i;
          }
        }
      }
      else {
        ofst << -1;
      }
    }

Для ответа в этой теме необходимо авторизоваться.