e-olymp
Задачи

Преобразование Капрекара

Преобразование Капрекара

Индийский математик Д. Р. Капрекар известен своими работами по теории чисел. Одна из его работ посвящена так называемому преобразованию Капрекара. Рассмотрим следующую операцию. Пусть задано число 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 (1x109).

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
100
Выходные данные #1
099
Входные данные #2
2414
Выходные данные #2
3177
Источник 2009 Цикл интернет-олимпиад для школьников. Первая олимпиада, базовый уровень, 19 сентября, Задача F