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

Пандигитальные произведения

Сложите произведения, для которых в равенстве a × b = c цифры от 1 до n встречаются ровно по одному разу.

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

  • Генерировать перестановки цифр
  • Перебирать все разбиения на три части
  • Убирать повторы с помощью множества

Условие

Запишите умножение a × b = c и рассмотрите все цифры чисел a, b и c вместе. Равенство называется n-пандигитальным, если это цифры 1, 2, ..., n, каждая ровно по одному разу (нулей нет). Для n = 4 подходит 3 × 4 = 12. Найдите все произведения c, которые встречаются хотя бы в одном n-пандигитальном равенстве.

Реализуйте pandigital_products(n).

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

n: наибольшая используемая цифра.

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

Верните сумму различных произведений c. Произведение, которое получается из нескольких равенств, учитывается один раз. Если таких произведений нет, верните 0.

Ограничения

1 ≤ n ≤ 9

Примеры

Пример 1
Ввод:
n = 4

Ожидаемый вывод:
expected = 12
Ввод:
long long n = 4;

Ожидаемый вывод:
long long expected = 12;
Ввод:
long n = 4;

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

Пояснение

3 × 4 = 12 использует 1, 2, 3, 4 по одному разу, и это единственное такое равенство, поэтому ответ 12.

Пример 2
Ввод:
n = 3

Ожидаемый вывод:
expected = 0
Ввод:
long long n = 3;

Ожидаемый вывод:
long long expected = 0;
Ввод:
long n = 3;

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

Пояснение

С цифрами 1, 2, 3 возможны только разбиения вроде 1 × 2 = 3, а это неверно, поэтому ответ 0.

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

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

Подсказка 1

Каждое n-пандигитальное равенство - это перестановка цифр от 1 до n, разрезанная на три части.

Подсказка 2

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

Подсказка 3

Храните произведения в множестве, чтобы каждое учитывалось один раз.

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

время O(n! × n²), доп. память O(number of products)

Ссылки

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

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

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

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

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

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