数の10進表現は数字を並べ替えることで別の数になる.
このことを使って数列を作ってみよう.
最初に,非負の整数a0と桁数Lを与える.
以下の規則を適用してaiからai+1を得る.
- 整数aiを,L桁の10進数で表記する.
必要であれば上位の桁に 0 を付け加える.
たとえば 2012 という数は 6 桁の10進数で表記する場合は 002012 となる.
- 各桁の数字を並べ替えて,最も大きい整数と最も小さい整数を作る.
上の例では,最も大きい整数は 221000 であり,
最も小さい整数は 000122 = 122となる.
- 最も大きい整数から最も小さな整数を引いて,整数ai+1を得る.
上の例では 221000 − 122 を計算して 220878 を得る.
この計算を繰り返すと,数列
a0 ,
a1 ,
a2 , ...
が得られる.
例えば 83268 という整数と桁数6が与えられた時,この計算を繰り返すと次のような数列
a0 ,
a1 ,
a2 , ...
が得られる.
a0 = 083268
a1 = 886320 − 023688 = 862632
a2 = 866322 − 223668 = 642654
a3 = 665442 − 244566 = 420876
a4 = 876420 − 024678 = 851742
a5 = 875421 − 124578 = 750843
a6 = 875430 − 034578 = 840852
a7 = 885420 − 024588 = 860832
a8 = 886320 − 023688 = 862632
…
整数を表すための桁数が指定されているので,
a0 ,
a1 ,
a2 , ...
と順に計算していくといずれ同じ数が現れる.
すなわち,条件
ai = aj
を満たすような i と j
(ただし i > j )
の組が必ず存在する.
上の例では,a8 = a1 = 862632 なので
(i = 8, j = 1) の組が条件を満たす.
最初の整数 a0 と桁数 L が与えられた場合に,条件
ai = aj (ただしi > j )
を満たす最小の i を求めるプログラムを作成せよ.
入力は複数のデータセットからなる.
各データセットは2つの整数
a0
と
L
が1個のスペースで区切られた1行であり,
a0 が最初の整数を,
L が桁数を表す.
ただし,
1 ≤ L ≤ 6 かつ
0 ≤ a0 < 10L
である.
入力の終わりは2個の0を含む行で示される.この行はデータセットではない.