101922: [AtCoder]ABC192 C - Kaprekar Number

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

定义如下函数: - $g_1(x)$ 为 $x$ 在十进制下的数位按照降序排列形成的数; - $g_2(x)$ 为 $x$ 在十进制下的数位按照升序排列形成的数; - $f(x)=g_1(x)-g_2(x)$。 给定 $N,K$,对于序列 $a_0=N$,$a_i=f(a_{i-1})$。求出 $a_K$。

加入题单

上一题 下一题 算法标签: