Задача
Возьмем число 192 и умножим его по очереди на 1, 2 и 3:
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
Объединяя все три произведения, получим девятизначное число 192384576 из цифр от 1 до 9 (пан-цифровое число). Будем называть число 192384576 объединённым произведением 192 и (1,2,3).
Таким же образом можно начать с числа 9 и по очереди умножать его на 1, 2, 3, 4 и 5, что в итоге дает пан-цифровое число 918273645, являющееся объединенным произведением 9 и (1,2,3,4,5).
Какое самое большое девятизначное пан-цифровое число можно образовать как объединенное произведение целого числа и (1,2, ... , n), где n > 1?
Решение
Для начала обозначим самое маленькое пан-цифровое число. Это объединение 1 и (1, 2, 3, 4, 5, 6, 7, 8, 9), что даст нам 123456789.
Какие будут самые большие число и серия множителей?
Объединение будет считаться последовательно с множителями 1, 2, 3 и т.д., и как только его длина превысит 9, можно сразу отбрасывать этот вариант. Также можно видеть, что если длина объединения стала больше 9, то в нём появились одинаковые цифры. Они могут появиться и раньше, что тоже делает вариант негодным.
Значит, для серии множителей можно не ставить никаких лимитов. Достаточно просто отслеживать, какие цифры были использованы в объединении, и при возникновении дубликата отбрасывать этот вариант в любой момент.
Теперь число. Максимальное объединение это 987654321, и максимальное число, чтобы его получить, будет в районе 4-х знаков. Т.е. скажем 9999 * 1 добавить 9999 * 2 это впритык 9 знаков, так что предел для числа будет 9999.
Определение занятых цифр
В предыдущих задачах я использовал массив из 9 элементов как маску занятости. Но его надо было очищать перед каждым новым использованием с помощью memset(). Хотя это быстрый метод, на этот раз я сделал по-другому. Теперь это можно сказать битовый массив, то есть просто одно int-число, где каждый бит обозначает занятость цифры (цифра соответствует порядковому номеру бита). Чтобы иметь доступ к отдельным битам, я также завёл битовые маски в виде массива:
int digit_mask[9] = { 1, 2, 4, 8, 16, 32, 64, 128, 256 };
Вроде то же самое, вид сбоку, но теперь, чтобы обнулить маску, надо просто обнулить одно число, а не массив.
Также я теперь могу за одну операцию проверить, все ли цифры в маске заняты. Для этого я сравниваю её с числом, равным сумме всех битовых масок.
#define ALL_DIGITS (1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256)
Проверка числа
В функцию check() передаются: число n, указатель на маску занятости digits, и массив битовых масок digit_mask.
Число разбивается на цифры путём взятия остатка от деления на 10. Если получилась цифра 0, это сразу не годится. Далее по номеру цифры берётся битовая маска. Эта битовая маска сравнивается с маской занятости через бинарное "и". Если бит в этой позиции уже установлен, то значит цифра повторилась, это тоже не годится. В противном случае помечаем бит как занятый, делим n на 10 для следующей итерации, и умножаем переменную mul на 10. Она будет возвращаться как результат, и нужна для того, чтобы знать, сколько разрядов в числе. Например, если n = 123, то mul будет равно 1000. Это понадобится позже.
Цикл с множителями
Перебираются числа от 1 до 9999, с каждым числом перебираются множители от 1 до 9. Произведение числа и множителя в случае успеха добавляется в переменную merged. Здесь и требуется mul, который возвращает функция check(). Чтобы дописать например 123 к уже существующему числу, это число надо умножить на 1000 и добавить 123.
Далее проверяем, если после очередного добавления все цифры в маске заняты, то это нам подходит. И ищем максимум.
Ссылка на онлайн-компилятор языка C с текстом программы
Подборка всех задач: