Индийский д. р. капрекар известен своими работами по теории чисел. одна из его работ посвящена так называемому преобразованию капрекара. рассмотрим следующую операцию. пусть задано число xx. пусть mm — наибольшее число, которое можно получить из xx перестановкой его цифр, а mm — наименьшее число (это число может содержать ведущие нули). обозначим как k(x)k(x) разность m-mm−m, дополненную при необходимости ведущими нулями так, чтобы число цифр в ней было равно числу цифр в xx.
например, k(100) = 100 - 001 = 099k(100)=100−001=099, k(2414) = 4421 - 1244 = 3177k(2414)=4421−1244=3177.
капрекар доказал, что если начать с некоторого четырехзначного числа xx, в котором не все цифры равны между собой, и последовательно применять к нему эту операцию (вычислять k(x)k(x), k(k(x))k(k( …), то рано или поздно получится число 6174. для него верно равенство k(6174) = 7641 - 1467 = 6174k(6174)=7641−1467=6174, поэтому на нем процесс зациклится.
ваша состоит в том, чтобы написать программу, вычисляющую k(x)k(x) по числу xx.
введите целое число без ведущих нулей xx (1 \le x \le 10^91≤x≤10
9
).
в выходной файл выведите k(x)k(x).
Далее, для описания манипуляций с видами будем использовать термины:
RT (правый единичный поворот на 90 градусов по часовой стрелке) ,
LT (левый единичный поворот на 90 градусов против часовой стрелки) ,
UT (разворот на 180 градусов)
Наша начальная цель: собрать из пяти видов верхнюю часть куба, т.е. его грани, стоящие над столом. Будем считать, что мы смотрим на стол с кубом сверху. Верхнюю часть куба, состоящую из пяти видов, будем собирать в виде крестовой раскладки.
В центре креста раскладки будет верхняя грань, которая смотрит на нас, когда мы смотрим вниз на стол с кубом. Дальняя от нас (сверху экрана, если смотреть на ноутбук) часть креста раскладки: это задняя сторона куба. Ближняя к нам (снизу экрана, если смотреть на ноутбук) часть креста раскладки: это передняя сторона куба. Левая часть креста раскладки – это левая сторона куба и правая часть раскладки – соответственно правая сторона.
Важно понимать, что на стыках видов (на рёбрах) при составлении раскладки должны совпадать цветные квадратики на краях видов: чёрный к чёрному и белый к белому, поскольку рёбра куба одновременно являются и рёбрами маленьких кубиков, каждый из которых обладает однотонным окрасом со всех сторон.
Перебор возможных вариантов удобно делать на черновике с карандашом и бумагой, либо с ручкой, но тогда нужно зачёркивать неудачные варианты.
Перебор должен быть системным, иначе мы пропустим тот или иной вариант, и можем пропустить и нужный нам вариант. В качестве системы можно предложить, например, такой график просмотра вариантов.
1. Выбираем вид для верхней грани куба, т.е. для центра креста раскладки (сначала первый, потом второй и т.д.)
2. Когда выбран какой-то вид для верхней (центральной) грани, пытаемся подмонтировать в качестве задней грани к нему другие виды. Опять же по порядку видов.
3. Когда выбран какой-то вид для верхней (центральной) и задней граней, пытаемся подмонтировать в качестве правой грани к нему другие виды. Опять же по порядку видов.
4. Когда выбран какой-то вид для верхней (центральной), задней и правой граней, пытаемся подмонтировать в качестве передней грани к нему другие виды. Опять же по порядку видов.
5. Когда выбран какой-то вид для верхней (центральной), задней, правой и передней граней, пытаемся подмонтировать в качестве левой грани к нему оставшийся вид.
При этом нужно следить, чтобы совпадали рёбра не только верхней (центральной) грани с боковыми, но и рёбра между боковыми гранями.
Перед перебором нужно отметить, что грани 3-его и 5-ого видов – несовместимы. Как их не крути, их рёбра никогда не совместятся. Значит, ни один из этих видов не может служить верхней гранью куба, поскольку иначе он бы взаимодействовал по ребру с несовместным видом. Кроме того, эти несовместные виды не могут быть рядом и на соседних боковых гранях. Таким образом, мы понимаем, что при переборе 3-ий и 5-ый виды можно размещать только на противоположных гранях.
Последовательный перебор из, примерно десятка неудачных – приводит к единственному хорошему варианту:
В центре креста раскладки: 2-ой вид.
Слева: 3-ий вид.
Справа: 5ый вид RT.
Сзади: 1-ый вид.
Впереди: 4-ый вид UT.
Эта раскладка показана на первом рисунке. Обратите внимание, что по раскраске совмещены не только рёбра на стыке видов центральных и боковых граней, но и рёбра на стыке соседних боковых граней.
Теперь очень аккуратно в строгом соответствии с буквами-метками (они должны совместиться) переворачиваем раскладку, так чтобы получилась нижняя грань. Это показано на втором рисунке и там уже проявляется по совмещениям на рёбрах вид нижней грани.
Если взглянуть на предлагаемые варианты, то мы можем легко убедиться, что подходит и вариант (А) и вариант (Д) при повороте их на LT.
Выбрать нужный вариант – можно только сосчитав количество белых (их должно быть 12) и чёрных кубиков (их должно быть 15).
Смотрим на первую раскладку. На верхней грани – 3 белых. В среднем видимом слое, в том, что зажат между верхней и нижней гранью (состоящем из 8 кубиков) – 4 белых. В нижней грани (что можно увидеть на второй картинке) – как минимум 3 кубика.
Всего в видимой и известной части кубика мы насчитали 10 белых кубиков. А должно их быть 12. Значит, один белый кубик находится в центре куба (он невидим) и ещё один белый кубик мы можем разместить в положение, отмеченное на втором рисунке знаком вопроса.
А значит, окончательно, нам подходит вариант (Д)
О т в е т :