上から作ったり、下から作ろうとしたり、dpを考えてみたが、 0の扱いが難しくて、下からは作れなかったし、上から作ると、何番目、の扱いが非常に面倒。
しばらく考えて苦肉の策として、Nがそこまで大きくないこととサンプルテストに最大値が出ていることに甘えて、 ルンルン数を100000番目を超える範囲ですべて作った。
コードテストで1000ms以下で実行できることを確認してからsubmit。
def create_lun(K): if K == 1: return ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"] else: r = [] d = create_lun(K - 1) for n in d: c = int(n[-1]) if K == 10 and int(n[0]) > 3: continue if c - 1 >= 0: r.append(n + str(c - 1)) r.append(n + n[-1]) if c + 1 <= 9: r.append(n + str(c + 1)) r.extend(d) return r def solve(K): A = create_lun(10) S = set([int(l) for l in A]) S.remove(0) A = sorted(list(S)) return A[K - 1] if __name__ == "__main__": K = int(input()) print(solve(K))
