Задача
Можно найти перестановки куба 41063625 (345^3), чтобы получить ещё два куба: 56623104 (384^3) и 66430125 (405^3). К слову, 41063625 является наименьшим кубом, для которого ровно три перестановки также являются кубами.
Найдите наименьший куб, для которого ровно пять перестановок также являются кубами.
Решение
Задача имеет сложность 15% и подвох. Так как там содержится слово "перестановка", давайте представим, на что нас хотят развести:
- Вычисляем следующий куб
- Переставляем цифры в этом кубе всеми возможными способами
- Для каждой перестановки проверяем, является ли она кубом, и если да, то увеличиваем счётчик перестановок
Формально это рабочее решение, но числа уже понятно что будут 8- и более значные, а перестановок только в одном таком числе будет огромное количество, так что проверять мы их будем долго. Плюс ещё проверка на кубичность предполагает извлечение корня 3-й степени, что тоже небыстро.
Можно немного подумать и понять, что если какое-то число является перестановкой другого, то нас не интересует точный вид этой перестановки. Достаточно только одного признака, "отпечатка" (fingerprint). Если два числа являются перестановками друг друга, то они содержат одинаковое количество одинаковых цифр. Это и есть отпечаток.
Далее получается так:
Берём очередной куб. Так как числа перебираются по порядку, то будем считать это число наименьшим кубом, с которого начинается цепочка перестановок. Вычисляем для него отпечаток – набор счётчиков для каждой цифры. Далее отдельным циклом проверяем следующие после него кубы, сравнивая их отпечатки с текущим.
Если мы получили 5 совпадений, это наш ответ. Но есть дополнительное ограничение. Таких совпадений должно быть ровно 5. Как мы поймём, что их не больше?
У чисел, участвующих в перестановках, есть нижняя и верхняя граница. Например, перестановки числа 3241 имеют нижнюю границу 1234 и верхнюю границу 4321. Всё, что мы найдём между 1234 и 4321, будет посчитано. А всё, что вне – уже заведомо не подходит.
Нижняя граница у нас получается автоматически, так как перебирая числа по возрастанию, мы обязательно начнём цепочку с самого малого числа. А сравнения со следующими числами будем делать до тех пор, пока очередной кандидат не перейдёт верхнюю границу.
Почему бы тогда не посчитать отпечаток сразу в виде верхней границы, чтобы он выполнял две функции? Для этого получим счётчики цифр числа и затем составим из этих счётчиков новое число, где цифры идут в порядке убывания.
(Гуру-питонисты, возможно, переведут число в строку и отсортируют символы в строке по убыванию.)
Таким образом, любая перестановка одних и тех же цифр даст один и тот же отпечаток, и он же будет равен верхней границе перестановок.
Теперь осталось организовать циклы перебора:
found это массив, куда мы будем складывать найденные числа. Он не нужен для ответа, так как требуется только минимальный куб, но с ним ответ красивее.
cnt это счётчик найденных совпадений, и как видно, цикл по i будет работать, пока этот счётчик не равен CNT (в нашем случае CNT = 5).
Начинаем перебор с константы MIN, которую я установил как 346. Вычисляем куб (cube), для него вычисляем отпечаток (fp), а дальше начинаем перебирать значения кубов cube2 от i+1 и до тех пор, пока очередной куб не превысит верхнюю границу, заданную fp. Опять же вычисляем второй отпечаток fp2 и сравниваем с первым.
Для записи в массив found (который не нужен, но вот для красоты) потребовалось дополнительное условие, так как его размер равен CNT, но совпадений может найтись больше, поэтому пишем в found только пока cnt < CNT.
Ну и потом можно вывести значения из found:
Ссылка на онлайн-компилятор языка C с текстом программы
Программа работает довольно быстро – в онлайн-компиляторе полсекунды или может секунду. Первоначально она была существенно быстрее, потому что я заранее рассчитал массив на 10 тысяч отпечатков. Но в угоду краткости кода решил удалить всё лишнее, ибо и такой скорости достаточно.
Подборка всех задач: