e-olymp 8529. Преобразование Капрекара

Задача

Индийский математик Д. Р. Капрекар известен своими работами по теории чисел. Одна из его работ посвящена так называемому преобразованию Капрекара. Рассмотрим следующую операцию. Пусть задано число $x$. Пусть $M$ — наибольшее число, которое можно получить из $x$ перестановкой его цифр, а $m$ — наименьшее число (это число может содержать ведущие нули). Обозначим как $K(x)$ разность $M$ — $m$, дополненную при необходимости ведущими нулями так, чтобы число цифр в ней было равно числу цифр в $x$.

Например $K(100) = 100 — 001 = 099$, $K(2414) = 4421 — 1244 = 3177$.

Капрекар доказал, что если начать с некоторого четырехзначного числа $x$, в котором не все цифры равны между собой, и последовательно применять к нему эту операцию (вычислять $K(x)$, $K(K(x))$, . . . ), то рано или поздно получится число $6174$. Для него верно равенство $K(6174) = 7641 — 1467 = 6174$, поэтому на нем процесс зациклится.

Ваша задача состоит в том, чтобы написать программу, вычисляющую $K(x)$ по числу $x.$

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

Одно целое число без ведущих нулей $x$ ($1$ ≤ $x$ ≤ $10^9$).

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

Выведите $K(x)$.

Тесты

Входные данные Выходные данные
100 099
1000000000 0999999999
2414 3177
6174 6174
5 0
7272 5445
142857 750843
495 495
55 00
56 09
554 099
12345 41976

 

Решение

Объяснение

Поскольку нужно находить минимальную и максимальную комбинацию из цифр числа, удобно в самом начале записать это число в виде массива и отсортировать. Далее найти, собственно, искомые числа, и получить из них само $K(x)$. Потом остаётся проверить количество цифр и вывести, при недостатке, соответствующее количество нулей.

Код на ideone
Зачтено на e-olymp

4 thoughts on “e-olymp 8529. Преобразование Капрекара

  1. int *N = new int [11]; Выделять память можно не из кучи, а из стека. int N[11]; Это работает быстрее и удалять в явном виде потом не придется.

    Вы вычисляете все степени двойки десятки от 0 до n-1 фактически за n2. Можно явно быстрее.

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

    Данный участок кода в объяснении по сути пропущен, однако он представляет собой наибольшую загадку. Зачем шифровать число 0 выражением (K_tmp * 10) % 10?

    • По поводу первой рекомендации было немного неясно, но, вроде, разобрался. Оказалось, что я несколько не так представлял разницу между этими способами объявления, чем и был обусловлен выбор. По поводу сортировки и числа 0 всё понял и согласен, спасибо. По поводу двойки, не совсем понял, но, подозреваю, что имелась ввиду 10 и поэтому исправил там.

      • Да, имелось в виду 10.

        Есть кстати красивый способ собрать число из цифр. Может быть, он Вам тоже понравится:

        Исправили обфускацию, но не везде.

        • Да, спасибо, на верху в цикле не заметил. Способ действительно логичнее, понравился. Только не знаю, нужно ли вставлять его в код самой публикации, чтобы не потерялся фрагмент, к которому это было адресовано. То есть, чтобы потенциальному читателю оставалось понятно что к чему написано. Так что пока оставил без изменений. Но постараюсь запомнить, спасибо.

Добавить комментарий