Edit

【pythonでABC192を解説】C - Kaprekar Number

問題概要

問題ページ

C - Kaprekar Number
C - Kaprekar Number

問題ページへ移動する

問題文

\(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\)
  • 入力は全て整数

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(str, str(input().rstrip('\n')).split()))
    for i in range(int(k)):
        a = []
        b = []
        n = sorted(n)
        for j in range(len(n)):
            a += [n[-j-1]]
            b += [n[j]]
        n = str(int("".join(a)) - int("".join(b)))
    print(n)


if __name__ == '__main__':
    solve()

-Edit
-