Задача: годовой баланс

В конторе «Рога и Копыта» подходит время подведения годового баланса. В бухгалтерию поступили сведения о том, что, согласно документам, суммарный расход составил а рублей, a суммарный приход – b рублей. Поскольку с реальным положением дел эти цифры все равно не имеют ничего общего, бухгалтер решил реализовать следующую свою идею. Как известно, при наборе чисел на компьютере люди часто ошибаются и вводят цифры в неправильном порядке (например, если надо ввести 150, могут ввести 105). Поэтому бухгалтер хочет найти такой способ переставить цифры в числах a и b, чтобы в результате разность a−b (и, соответственно, количество денег, которые он положит к себе в карман), была максимальна, а в случае чего можно будет сослаться на ошибку секретаря. При этом нельзя забывать о знаке чисел и о том, что ноль не может быть первой цифрой числа, отличного от ноля. Напишите программу, которая поможет бухгалтеру.

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

Входной файл INPUT.TXT содержит два целых числа a и b (-109 < a,b < 109).

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

В выходной файл OUTPUT.TXT выведите одно целое число – наибольшую разность чисел, первое из которых может быть получено перестановкой цифр a, а второе – перестановкой цифр b.

Примеры:

1. Входные данные: 18 и 10; выходные: 71;
2. Входные данные: 1 и -23; выходные: 33.

 Решение

Для того, чтобы значение a−b было максимально, необходимо из a получить максимально возможное число, а из b, наоборот, определить наименьшее. Если число неотрицательно, то для получения минимума цифры сортируются в порядке возрастания, а при вычислении максимума, соответственно, в порядке убывания. Для отрицательных чисел ситуация с сортировкой цифр меняется с точностью до наоборот. Причем, нужно заметить, что при сортировке цифр по возрастанию нужно избежать момента, где пришлось бы поставить 0 на первое место (этого можно достичь, например, при сортировке пузырьком, если при сравнении первых двух соседних элементов не менять их в том случае, когда второй — это ноль).

Сортировку цифр в числе проще проводить, если преобразовать само число в строку, и работать с обычным массивом символов. Причем, знак  - не обязательно включать в этот массив. Отсортировав его, например пузырьком, можно сделать обратное преобразование строки в число. После нахождения максимального a и минимального b останется просто вывести значение a−b.

Для хранения чисел можно использовать обычный 4-байтовый целый тип (long или longint например), т.к. результат вычислений не может превзойти значения 1999999998 по абсолютной величине. Если бы ограничения на a и b были не до миллиарда, а до двух миллиардов, то итоговая разница могла бы достигать значения, большего 19 миллиардов, где пришлось бы использовать такие 8-байтовые целые типы как int64 или __int64.

Другие интересные задачи для программистов (и не только) вы можете посмотреть у нас на сайте.