013. Постоянная Капрекара

(Время - 1 сек., память - 16 Мб)

Возьмем четырехзначное число, в котором не все цифры одинаковы, например 6264. Расположим цифры сначала в порядке убывания - 6642; затем, переставив их в обратном порядке, получим 2466. Вычтем последнее число из 6642. На следующем шаге с полученной разностью проделаем тоже самое. Через несколько таких действий получится число, переходящее само в себя и называемое постоянной Капрекара.

Требуется написать программу, которая находит эту постоянную и количество шагов для ее получения из заданного четырехзначного числа.

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

В единственной строке входного файла input.txt записано четырехзначное число.

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

В первую строку выходного файла output.txt нужно вывести постоянную Капрекара, во вторую – количество шагов для ее получения из заданного числа.

Пример

input.txt

output.txt

1

1234

6174
3

Разбор

Вначале опишем функцию нахождения следующего числа: для этого находим цифры числа n=a1+a2*10+a3*100+a4*1000, упорядочиваем их по возрастанию a1  a2  a3  a4, считаем следующее число по формуле a4*1000+a3*100+a2*10+a1-a1*1000-a2*100-a3*10-a4=(a4-a1)*1000+(a3-a2)*100+(a2-a3)*10+a1-a4=(a4-a1)*999+(a3-a2)*90. Далее в цикле пока следующее число не равно рассматриваемому увеличиваем счётчик на единицу и, используя описанную функцию, находим следующее число.

Программа на Паскале

var

  n, n1, c : integer;

function sled(n:integer): integer;

  var a : array [1..4] of integer;

      i, j, x : integer;

begin

  for i:=1 to 4 do

  begin

    a[i]:=n mod 10;

    n:=n div 10

  end;

  for i:=1 to 3 do

    for j:=1 to 4-i do

      if a[j]>a[j+1] then begin x:=a[j]; a[j]:=a[j+1]; a[j+1]:=x end;

  sled:=(a[4]-a[1])*999+(a[3]-a[2])*90

end;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  read(n);

  c:=0; n1:=sled(n);

  while n<>n1 do

  begin

    c:=c+1;

    n:=n1;

    n1:=sled(n)

  end;

  writeln(n);

  write(c)

end.

Программа на С

 

Информация о задаче

Автор, источник

 

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2008-2009 уч. год, 2-й тур

Тематика

Целочисленная арифметика

Примерная сложность

22%

Ссылки в Интернете

Условие, сдача решения – http://acmu.ru/index.asp?main=task&id_task=457

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор, дата –  Алексеев А.В., 22.05.2012