ある自然数に対するカプレカ―変換は,以下の手順で定義される.

  1. 自然数の桁の数字を大きい順に並び替え,その桁数字を用いてできる最大の自然数を作る
  2. 自然数の桁の数字を小さい順に並び替え,その桁数字を用いてできる最小の自然数を作る
  3. 最大の自然数(手順1)から最小の自然数(手順2)を引き,自然数を更新する

3桁の自然数(ただし全ての桁の数字が同じものは除く)に対して,カプレカ―変換を繰り返し適用すると,必ず495に到達することが知られている.例えば,$246$を出発点とすると,以下のように$495$に到達する.

ここで,3桁に満たない数字については上位の桁が$0$で埋められているものと考えよ. たとえば$909$に対するカプレカー変換は$909 \mapsto 990 - 99 = 891$であり,$9$に対するカプレカー変換は$9 \mapsto 900 - 9 = 891$である.

問題

標準入力より3桁までの自然数を読み込み,$495$に到達するまでカプレカ―変換を繰り返すプログラムを作成せよ.

ただし,$0$および全桁の数字が同じもの($111,222,\dots,999$)は入力されない. また,3桁に満たない数字が入力された場合は上位の桁が$0$で埋められていると考えよ.たとえば$12$が入力された場合は$012$のカプレカー変換から処理をはじめよ. プログラムは以下の仕様を満たすこと.

  1. 各行に1回のカプレカー変換の様子を「最大の自然数 - 最小の自然数 = 新しい自然数」という形式で出力すること.実行例を参考にせよ.
  2. 各自然数は右詰めで3桁になるように適宜空白を挿入せよ.
  3. カプレカ―変換後の自然数が495になった段階で,プログラムを終了せよ.
  4. 各表示は標準出力に書き出し,末尾には改行文字\nを付けること.

実行例

#は標準入力,>は標準出力を表す.

# 123
> 321 - 123 = 198
> 981 - 189 = 792
> 972 - 279 = 693
> 963 - 369 = 594
> 954 - 459 = 495
# 121
> 211 - 112 =  99
> 990 -  99 = 891
> 981 - 189 = 792
> 972 - 279 = 693
> 963 - 369 = 594
> 954 - 459 = 495
# 9
> 900 -   9 = 891
> 981 - 189 = 792
> 972 - 279 = 693
> 963 - 369 = 594
> 954 - 459 = 495

ヒント

少しずつ作り,少しずつテストする

参考文献