【pythonでABC161を解説】D - Lunlun Number

問題概要

問題ページ

D - Lunlun Number

問題ページへ移動する

問題文

正の整数 $X$ が以下の条件を満たすとき、 $X$ はルンルン数であると言います。

• $X$ を(leading zeroなしで)十進数表記した際に、隣り合うどの $2$ つの桁の値についても、差の絶対値が $1$ 以下

例えば、 $1234$ , $1$ , $334$ などはルンルン数ですが、 $31415$ , $119$ , $13579$ などはルンルン数ではありません。

正の整数 $K$ が与えられます。小さい方から $K$ 番目のルンルン数を求めてください。

制約

• $1 \leq K \leq 10^5$
• 入力はすべて整数である。

問題の考察

ACコード

import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    k = int(readline())
    if k < 10:
        print(k)
    else:
        ls_r = [str(i) for i in range(1, 10)]
        ls_z = ["0"]
        t = 9
        while True:
            t_ls_r = []
            t_ls_z = []
            for v in ls_r + ls_z:
                top = int(v[0])
                for i in range(max(0, top - 1), min(10, top + 2)):
                    if i == 0:
                        t_ls_z.append("".join([str(i)] + list(str(v))))
                    else:
                        t_ls_r.append("".join([str(i)] + list(str(v))))
            if len(t_ls_r) + t >= k:
                t_ls_r.sort()
                print(t_ls_r[k - t - 1])
                exit()
            else:
                ls_r = t_ls_r
                ls_z = t_ls_z
                t += len(t_ls_r)


if __name__ == '__main__':
    solve()