Все задачи
Сложно Решено: 0 Процент решений: 0%

Цепочки факториалов цифр

Посчитайте начальные числа, цепочка факториалов цифр которых содержит ровно заданное количество различных членов.

Чему вы научитесь

  • Идти по цепочке, пока значение не повторится
  • Находить длины цепочек внутри цикла и до него
  • Повторно использовать сохранённые длины

Условие

Заменим число суммой факториалов его цифр: 145 даёт 1! + 4! + 5! = 145, то есть снова себя, а 69 даёт 6! + 9! = 363600. Если повторять эту операцию, рано или поздно получится цикл. Цепочка начального числа - это все члены до первого повтора: 69, 363600, 1454, 169, 363601, а затем снова 1454, так что у 69 пять различных членов. Посчитайте начальные числа от 1 до limit, цепочка которых содержит ровно length различных членов.

Реализуйте digit_factorial_chains(limit, length).

Многие цепочки приходят к одним и тем же числам. Сохраняйте длину цепочки для каждого числа, как только она станет известна, и используйте её повторно.

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

limit: наибольшее начальное число.

length: нужное количество различных членов, включая начальное число.

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

Верните количество начальных чисел n, 1 ≤ n ≤ limit, в цепочке которых ровно length различных членов.

Ограничения

1 ≤ limit ≤ 100 000; 1 ≤ length ≤ 70

Примеры

Пример 1
Ввод:
limit = 2
length = 1

Ожидаемый вывод:
expected = 2
Ввод:
long long limit = 2;
long long length = 1;

Ожидаемый вывод:
long long expected = 2;
Ввод:
long limit = 2;
long length = 1;

Ожидаемый вывод:
long expected = 2;

Пояснение

1! = 1 и 2! = 2, поэтому 1 и 2 переходят сами в себя, и их цепочка состоит из одного члена. Ответ 2.

Пример 2
Ввод:
limit = 10
length = 2

Ожидаемый вывод:
expected = 1
Ввод:
long long limit = 10;
long long length = 2;

Ожидаемый вывод:
long long expected = 1;
Ввод:
long limit = 10;
long length = 2;

Ожидаемый вывод:
long expected = 1;

Пояснение

3 даёт 6, затем 720, 5043, ..., так что цепочка длинная. 10 даёт 1! + 0! = 2, а затем снова 2: два члена. Ровно 2 члена только у 10, поэтому ответ 1.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Заранее вычислите факториалы от 0! до 9!.

Подсказка 2

Запоминайте номер шага каждого значения в текущей цепочке; повтор покажет, где начинается цикл.

Подсказка 3

У всех значений в цикле длина равна длине цикла, а у каждого значения перед циклом длина на один больше, чем у следующего.

Ожидаемая сложность

время O(limit × log limit) с мемоизацией, доп. память O(limit)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.