C - Kaprekar Number Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

0 以上の整数 x に対して、g_1(x), g_2(x), f(x) を次のように定めます。

  • g_1(x)= x を十進法で表したときの各桁の数字を大きい順に並び替えてできる整数
  • g_2(x)= x を十進法で表したときの各桁の数字を小さい順に並び替えてできる整数
  • f(x)=g_1(x)-g_2(x)

例えば g_1(314)=431, g_2(3021)=123, f(271)=721-127=594 です。先頭の余分な 0 は無視されることに注意してください。

整数 N,K が与えられるので、a_0=N, a_{i+1}=f(a_i)\ (i\geq 0) で定まる数列の a_K を求めてください。

制約

  • 0 \leq N \leq 10^9
  • 0 \leq K \leq 10^5
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

a_K を出力せよ。

入力例 1

314 2

出力例 1

693
  • a_0=314
  • a_1=f(314)=431-134=297
  • a_2=f(297)=972-279=693

です。

入力例 2

1000000000 100

出力例 2

0
  • a_0=1000000000
  • a_1=f(1000000000)=1000000000-1=999999999
  • a_2=f(999999999)=999999999-999999999=0
  • a_3=f(0)=0-0=0
  • \vdots

となります。

入力例 3

6174 100000

出力例 3

6174

Score : 300 points

Problem Statement

For an integer x not less than 0, we define g_1(x), g_2(x), f(x) as follows:

  • g_1(x)= the integer obtained by rearranging the digits in the decimal notation of x in descending order
  • g_2(x)= the integer obtained by rearranging the digits in the decimal notation of x in ascending order
  • f(x)=g_1(x)-g_2(x)

For example, we have g_1(314)=431, g_2(3021)=123, f(271)=721-127=594. Note that the leading zeros are ignored.

Given integers N, K, find a_K in the sequence defined by a_0=N, a_{i+1}=f(a_i)\ (i\geq 0).

Constraints

  • 0 \leq N \leq 10^9
  • 0 \leq K \leq 10^5
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print a_K.

Sample Input 1

314 2

Sample Output 1

693

We have:

  • a_0=314
  • a_1=f(314)=431-134=297
  • a_2=f(297)=972-279=693

Sample Input 2

1000000000 100

Sample Output 2

0

We have:

  • a_0=1000000000
  • a_1=f(1000000000)=1000000000-1=999999999
  • a_2=f(999999999)=999999999-999999999=0
  • a_3=f(0)=0-0=0
  • \vdots

Sample Input 3

6174 100000

Sample Output 3

6174