алгоритмы - Алгоритм восстановления числа

Выразить Y через X достаточно легко при помощи операторов div и mod. Оказывается, что значениями Y не могут быть девять трёхзначных чисел: 100, 210, 320, 430, 540, 650, 760, 870, 980. При этом может получиться одно из девяти четырёхзначных чисел: 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008. У всех чисел, которые могут получиться, прообраз только один, что следует из совпадения количества.

Проверить надо два факта. Первый -- что из указанных девяти исключений ни одно получиться не могло. Это делается просто: если до перестановки цифр было 100, 201, 302, ... , 908, то такой результат не мог возникнуть в результате прибавления к трёхзначному числу его первой цифры -- как при смене старшего разряда, так и при его сохранении. Оба варианта ведут к противоречию. Например, число 403 теоретически могло получиться из числа, начинающегося с 3 или 4, но тогда в первом варианте до прибавления было 400, а во втором 399.

Второй факт состоит в том, что все остальные числа имеют хотя бы один прообраз. Опишем способ его получения. Пусть $%Y=\overline{pqr}=100p+10q+r$%, где значение $%p$% условно может принимать значение $%10$% для указанных выше вариантов.

Допустим, что $%p\le q$%. Рассмотрим трёхзначное число $%X=100p+10r+(q-p)$%. Ясно, что после прибавления цифры $%p$% и перестановки двух последних цифр получится в точности $%Y$%.

Пусть теперь $%p > q$%. Разберём два подслучая. Если $%r\ge1$%, то положим $%X=100a+10b+c$%, где $%a=p$%, $%b=r-1$%, $%c=10+q-p$%. Из условия ясно, что это десятичные цифры. После прибавления цифры $%p$% в младшем разряде оказывается цифра $%q$%, а единица переходит в следующий разряд, который становится равен $%r$%. После перестановки цифр имеет место то, что нужно.

Пусть теперь $%p > q$%, $%r=0$% (включая случай $%p=10$%). Для начала пусть $%p\le9$%. Равенство $%p=q+1$% соответствует тем вариантам, которые были выше рассмотрены как невозможные, поэтому $%p\ge q+2$%. Полагаем $%X=100a+10b+c$%, где $%a=p-1\ge1$%, $%b=9$%, $%c=11+q-p$%. Из условия вытекает, что $%1\le c\le9$% будет десятичной цифрой. После прибавления первой цифры, равной $%p-1$%, на конце получится $%q$%, а единица перейдёт в разряд десятков, прибавляясь к цифре $%9$%. Поэтому в разряде десятков окажется $%0=r$%, а к разряду сотен прибавится единица, и там получится $%p$%. Переставляем две поcледние цифры, получая $%Y$%.

Если $%p=10$%, то рассмотрению подлежат числа $%Y$% от $%1000$% до $%1008$%. Для них $%X=Y-9$%.