Edit

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

問題概要

問題ページ

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()

-Edit