Индийский математик Д. Р. Капрекар известен своими
работами по теории чисел. Одна из его работ посвящена так называемому
преобразованию Капрекара. Рассмотрим следующую операцию. Пусть задано число 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 ≤ 109).
Выход. Выведите K(x).
|
Пример входа 1 |
Пример выхода 1 |
|
100 |
099 |
|
|
|
|
Пример входа 2 |
Пример выхода 2 |
|
2414 |
3177 |
строки
Для получения
чисел M и m будем
хранить число x как строку. Тогда
отсортировав символы строки по возрастанию, получим m. Отсортировав символы строки по убыванию, получим M. Остается полученные отсортированные строки
преобразовать в числа и вывести разницу M
– m, дополненную ведущими нулями как требуется в условии задачи.
Реализация алгоритма
Читаем
входное значение x как строку s.
cin >> s;
Сортируем цифры числа по возрастанию. Получаем наименьшее
число a, которое можно получить из цифр числа x.
sort(s.begin(),
s.end());
a =
stoi(s);
Обернем строку s. Теперь цифры числа x
отсортированы по убыванию. Получаем наибольшее число b, которое
можно получить из цифр числа x.
reverse(s.begin(),
s.end());
b =
stoi(s);
Выводим ответ – разницу b – a
с ведущими нулями. Выводим столько же цифр, сколько их в числе x.
cout.fill('0');
cout.width(s.size());
cout << b - a << endl;