Problem:


Score : 400 points

Problem Statement

A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:

In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1.

For example, 1234, 1, and 334 are lunlun numbers, while none of 31415, 119, or 13579 is.

You are given a positive integer K. Find the K-th smallest lunlun number.

Constraints

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer.

Sample Input 1

15

Sample Output 1

23

We will list the 15 smallest lunlun numbers in ascending order:

1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
21,
22,
23.

Thus, the answer is 23.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

13

Sample Output 3

21

Sample Input 4

100000

Sample Output 4

3234566667

Note that the answer may not fit into the 32-bit signed integer type.



Sample input:
15


Sample output:
23

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    K = int(stdin.readline().rstrip())

    def check(x):
        s = str(x)
        for i in range(len(s) - 1):
            if 1 < abs(int(s[i]) - int(s[i + 1])):
                return False
        return True

    if K <= 100:
        count = 0
        i = 1
        while True:
            if check(i):
                count += 1
            if count == K:
                print(i)
                return
            i += 1
    else:
        def inner(n):
            s = str(n)
            for idx in range(len(s) - 1, 0, -1):
                c1 = int(s[idx])
                c2 = int(s[idx - 1])
                if c1 != 9 and ((c2 - 1) == c1 or c2 == c1):
                    c1 += 1
                    new_s = s[:idx] + str(c1)
                    for _ in range(len(s) - len(new_s)):
                        new_s += str(max(int(new_s[-1]) - 1, 0))
                    return int(new_s)
            if int(s[0]) != 9:
                new_s = str(int(s[0]) + 1)
                for _ in range(len(s) - len(new_s)):
                    new_s += str(max(int(new_s[-1]) - 1, 0))
                return int(new_s)
            else:
                new_s = '1'
                for _ in range(len(s)):
                    new_s += str(max(int(new_s[-1]) - 1, 0))
                return int(new_s)

        ans = 878
        for i in range(101, K + 1):
            ans = inner(ans)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k = int(input())

chart = [[0 for _ in range(10)] for __ in range(9)]
chart.insert(0,[1 for _ in range(10)])

for i in range(1,10): # 桁
    for j in range(10): # 最初の数
        if j == 0:
            chart[i][j] = chart[i-1][j] + chart[i-1][j+1]
        elif j == 9:
            chart[i][j] = chart[i-1][j-1] + chart[i-1][j]
        else:
            chart[i][j] = chart[i-1][j-1] + chart[i-1][j] + chart[i-1][j+1]

sum_list = [sum(row[1:]) for row in chart]

count = 0
for i,elem in enumerate(sum_list):
    count += elem
    if count > k:
        idx = i
        diff = k-sum(sum_list[:i]) # idx桁目のdiffばんめ
        break

digit = ''
start = 0
end = 10
first = True

while idx >= 0:
    # print(idx,diff,chart[idx][start:end],start,end)
    count = 0
    if first:
        target_row = chart[idx][start:end]
        target_row[0] = 0
        first = False
    else:
        target_row = chart[idx][start:end]
    for i,num in enumerate(target_row):
        count += num
        if count >= diff:
            digit += str(start+i)
            diff = diff - (count - num)
            idx -= 1
            if start + i == 0:
                start = 0
                end = 2
            elif start + i == 9:
                start = 8
                end = 10
            else:
                s = start
                start = s + i - 1
                end = s + i + 2
            break
        
print(digit)

Submission status: Accepted

Solution code:
k = int(input())

te = [[i for i in range(1, 10)]]
a = te[0]
for i in range(11):
    te2 = []
    for j in te[i]:
        c = j%10
        if c == 0:
            te2 += [j*10 + c + k for k in (0, 1)]
        elif c == 9:
            te2 += [j*10 + c + k for k in (-1, 0)]
        else:
            te2 += [j*10 + c + k for k in (-1, 0, 1)]
    te.append(te2)
    a += te2
print(a[k-1])

Submission status: Accepted

Solution code:
import sys
K = int(input())
if K < 10:
    print(K)
    sys.exit()
lst = [[str(i)] for i in range(10)]
i = 9
while True:
    new_lst = [[] for j in range(10)]
    for j in range(10):     #0-9までについて
        for k in range(-1, 2):  #-1, 0, +1の3つについて
            if j == 0 and k == -1:
                continue
            if j == 9 and k == 1:
                break
            for l in lst[j+k]:
                tmp = str(j) + str(l)
                new_lst[j].append(tmp)
                # print(i, K , i == K)
                if j != 0:
                    i += 1
                    if i == K:
                        print(int(tmp))
                        sys.exit()
    # print(i, new_lst)
    lst = new_lst.copy()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
def f(v,i,ans):
    if i == 0:return
    if str(v)[-1] != "0":
        x = int(str(v)+str(int(str(v)[-1])-1))
        ans.add(x)
        f(x,i-1,ans)
    y = int(str(v)+str(v)[-1])
    ans.add(y)
    f(y,i-1,ans)
    if str(v)[-1] != "9":
        z = int(str(v)+str(int(str(v)[-1])+1))
        ans.add(z)
        f(z,i-1,ans)
def main():
    K = int(input())
    ans = set()
    for i in range(1,10):
        ans.add(i)
        f(i,10,ans)
    ans = list(ans)
    ans.sort()
    print(ans[K-1])
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))


#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10000)
def rec(keta,num,val,cache):
    if keta==0:
        #print(val)
        cache.append(val)
        return None

    #"""
    if num!=0:
        tmp=val+(num-1)*10**(keta-1)
        rec(keta-1,num-1,tmp,cache)
    if num!=9:
        tmp=val+(num+1)*10**(keta-1)
        rec(keta-1,num+1,tmp,cache)

    #"""
    tmp=val+(num)*10**(keta-1)
    #print(keta)
    #print(tmp)
    rec(keta-1,num,tmp,cache)
    


ans=[]
#rec(n,1,1*(10**n),ans)
for n in range(10):
    for i in range(10):
        rec(n,i,i*(10**(n)),ans)


ans=set(ans)
ans=list(ans)
ans.sort()
n=int(input())
print(ans[n])

Submission status: Accepted

Solution code:
def main():
    from builtins import int, map, list, print, len
    from collections import deque
    import sys
    sys.setrecursionlimit(10 ** 6)

    input = sys.stdin.readline
    input_list = (lambda: input().rstrip().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    K = input_number()
    cnt = [0]
    queue = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

    def check():
        now = 0
        while len(queue) > 0 and cnt[0] < K:
            now = queue.popleft()
            cnt[0] += 1
            x = now % 10
            num_ls = [x - 1, x, x + 1]
            for num in num_ls:
                if num < 0 or num > 9: continue
                queue.append(now * 10 + num)
        print(now)
    check()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
from collections import deque

def main():
    K = int(input())
    cnt = 0
    dq = deque(['1','2','3','4','5','6','7','8','9'])
    while cnt < K:
        cnt += 1
        d = dq.popleft()
        a = int(d[-1])
        if a == 0:
            dq.append(d+str(0))
            dq.append(d+str(1))
        elif a == 9:
            dq.append(d+str(8))
            dq.append(d+str(9))
        else:
            for i in range(a-1, a+2):
                dq.append(d+str(i))
    print(d)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def check(mae, keta, count, k):
    if keta == 0:
        count += 1
        if count == k:
            ans = mae
        else:
            ans = -1
        return count, ans
    if mae == 0:
        count, ans = check(0, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
        count, ans = check(1, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
    elif mae == 9:
        count, ans = check(8, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
        count, ans = check(9, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
    else:
        for i in [-1, 0, 1]:
            count, ans = check(mae + i, keta - 1, count, k)
            if ans >= 0:
                ans += mae * 10 ** keta
                return count, ans
    return count, ans

k = int(input())
if k < 10:
    print(k)
else:
    count = 9
    flag = 0
    for keta in range(2, 1000):
        for sento in range(1, 10):
            count, ans = check(sento, keta - 1, count, k)
            if ans >= 0:
                print(ans)
                flag = 1
                break
        if flag == 1:
            break

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#dpより愚直に作るか
k = int(input())
lun = [i for i in range(10)]
while len(lun)<k+1:#正の整数
    lun2 = []
    for i in lun:
        lun2.append(i*10+(i%10))
        if i%10:
            lun2.append(i*10+(i%10)-1)
        if (i%10)<9:
            lun2.append(i*10+(i%10)+1)
    lun = list(set(lun+lun2))
lun.sort()
print(lun[k])

Submission status: Accepted

Solution code:
# dfsか？
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
rr = range


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
        # 内包表記はpypyでは若干遅いことに注意
        # #numpy使うだろうからこれを残しておくけど
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from fractions import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a * b // g


K = read_a_int()

# bfsで全探索したほうが良くない？
cnt = 0

candi = set()


def dfs(now: int):  # 上の桁からやってく
    if len(str(now)) >= 11:
        return
    candi.add(now)
    right = now % 10  # 下一桁
    # 探索
    if right == 0:
        tmp = [right, right + 1]
    elif right == 9:
        tmp = [right - 1, right]
    else:
        tmp = [right - 1, right, right + 1]
    for ad in tmp:
        dfs(now * 10 + ad)


# print(sorted(candi))
for i in range(1, 10):
    dfs(i)
print(sorted(candi)[K - 1])

Submission status: Accepted

Solution code:
K = int(input())

if K <= 9:
    print(K)
    exit()

memo = [[1]*10] + [[1]*10 for _ in range(9)]

n = 9
digit = 1
i = -1
ans = []
while True:
    i += 1
    if i == 10:
        i = 0
        digit += 1
    tmp = memo[digit-1][i]
    if i >= 1:
        tmp += memo[digit-1][i-1]
    if i <= 8:
        tmp += memo[digit-1][i+1]
    memo[digit][i] = tmp
    if i != 0:
        if n + tmp >= K:
            while digit >= 0:
                t = memo[digit][i]
                #if n + t == K:
                #    ans.append(i)
                #    for d in range(digit):
                #        ans.append(min(9, i+d))
                #    break
                if n + t >=  K:
                    ans.append(i)
                    digit -= 1
                    i = max(0, i-1)
                else:
                    n += t
                    i += 1
            break
        else:
            n += tmp

print(''.join(map(str, ans)))

Submission status: Accepted

Solution code:
k = int(input())

ll = [1, 2, 3, 4, 5, 6, 7, 8, 9]
lq = [1, 2, 3, 4, 5, 6, 7, 8, 9]


while len(ll) < k:
    nq = []
    for i in range(len(lq)):
        d = lq[i] % 10
        if d > 0:
            nl = lq[i] * 10 + d - 1
            nq.append(nl)
            ll.append(nl)
        nl = lq[i] * 10 + d
        nq.append(nl)
        ll.append(nl)
        if d < 9:
            nl = lq[i] * 10 + d + 1
            nq.append(nl)
            ll.append(nl)

    lq = nq

print(ll[k-1])

Submission status: Accepted

Solution code:
#!python3

# input
K = int(input())


def solve(dp, i, j, s):
    if i == 0:
        return
    for k in range(max(0, j - 1), min(10, j + 2)):
        if s + dp[i][k] >= K:
            print(k, end="")
            return solve(dp, i - 1, k, s)
        else:
            s += dp[i][k]


def main():
    if K < 10:
        print(K)
        return
    dp = [[None], [1] * 10]
    sn = [[0] * 10, [i for i in range(10)]]
    i = 2
    while True:
        l = [0] * 10
        sl = [0] * 10
        l[0] = dp[i-1][0] + dp[i-1][1]
        sl[0] = sn[i-1][9]
        for j in range(1, 10):
            if j == 9:
                l[9] = dp[i-1][8] + dp[i-1][9]
            else:
                l[j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]
            sl[j] = sl[j-1] + l[j]
            if sl[j] >= K:
                print(j, end="")
                solve(dp, i - 1, j, sl[j-1])
                return
        dp.append(l)
        sn.append(sl)
        i += 1


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
#input = sys.stdin.readline

def main():
    k = int(input())

    l = []
    def dfs(i, p, keta):
        l.append(i)
        if keta >= 10:
            return None
        if p != 0 and p != 9:
            for j in range(p-1, p+2):
                temp = j*(10**keta)+i
                l.append(temp)
                dfs(temp, j, keta+1)
        if p == 0:
            for j in range(p, p+2):
                temp = j*(10**keta)+i
                l.append(temp)
                dfs(temp, j, keta+1)
        if p == 9:
            for j in range(8, 10):
                temp = j*(10**keta)+i
                l.append(temp)
                dfs(temp, j, keta+1)

    for i in range(10):
        dfs(i, i, 1)
    #dfs(1, 1, 1)
    l = list(set(l))
    #print(l)
    l.sort()
    #print(l[0:k+1])
    #print(l[0:k])
    print(l[k])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def check(s):
    for i in range(len(s)-1):
        if(abs(int(s[i])-int(s[i+1])) > 1):
            return len(s)-i-2
    return -1


def main():
    k = int(input())

    if k < 10:
        print(k)
        return

    c = 10
    s = '1'
    table = [0] * (10**5+5)
    while c <= k+1:
        d = check(s)
        if d != -1:
            s = str(int(s)+10**d)
            continue
        last = int(s[-1])
        if last != 0:
            table[c] = s+str(last-1)
            c += 1
        table[c] = s+str(last)
        c += 1
        if last != 9:
            table[c] = s+str(last+1)
            c += 1
        s = str(int(s)+1)

    print(table[k])


main()

Submission status: Accepted

Solution code:
k = int(input())
a = [1,2,3,4,5,6,7,8,9] #一桁目を入れる。
kosu = [0,1,1,1,1,1,1,1,1,1]
total = sum(kosu)
i = 0 #これが1桁に相当.
tempk = k*1
while k > total:
  b = a.copy() #aのコピーを作ってbを参照して新しいaを作る。
  tempk = k - total
  i += 1
  a = [] #ここでaをリセット
  kosub = kosu.copy() #各々の数で終わる個数を記録
  kosu = []
  for i in range(10):
    if i == 0:
      kosu.append(kosub[i]+kosub[i+1])
    elif i == 9:
      kosu.append(kosub[i-1]+kosub[i])
    else:
      kosu.append(kosub[i-1]+kosub[i]+kosub[i+1])
  total += sum(kosu)
  for i in range(len(b)):
    if b[i]%10 == 0:
      a.append(b[i]*10)
      a.append(b[i]*10+1)
    elif b[i]%10 == 9:
      a.append(b[i]*10+8)
      a.append(b[i]*10+9)
    else:
      a.append(b[i]*10+b[i]%10-1)
      a.append(b[i]*10+b[i]%10)      
      a.append(b[i]*10+b[i]%10+1)
  #print(a)
  #print(kosu)
  #print(total)
#print(tempk,total,len(a))
print(a[tempk-1])

Submission status: Accepted

Solution code:
import itertools
k = int(input())
def a(b):
    list_ = []
    for i in b:
        ii = str(i)
        z = int(ii[-1])
        if z==0:
            list_.append(int(ii+'0'))
            list_.append(int(ii+'1'))
        elif z==9:
            list_.append(int(ii+'8'))
            list_.append(int(ii+'9'))
        else:
            list_.append(int(ii+str(z-1)))
            list_.append(int(ii+str(z)))
            list_.append(int(ii+str(z+1)))
    return list_

l1 = [[1]]

for _ in range(9):
    l1.append(a(l1[-1]))

c1 = list(itertools.chain.from_iterable(l1))
l2 = [[2]]

for _ in range(9):
    l2.append(a(l2[-1]))
c2 = list(itertools.chain.from_iterable(l2))
l3 = [[3]]

for _ in range(9):
    l3.append(a(l3[-1]))
c3 = list(itertools.chain.from_iterable(l3))

l4 = [[4]]
for _ in range(9):
    l4.append(a(l4[-1]))
c4 = list(itertools.chain.from_iterable(l4))
l5 = [[5]]

for _ in range(9):
    l5.append(a(l5[-1]))
c5 = list(itertools.chain.from_iterable(l5))

l6 = [[6]]

for _ in range(9):
    l6.append(a(l6[-1]))
c6 = list(itertools.chain.from_iterable(l6))
l7 = [[7]]

for _ in range(9):
    l7.append(a(l7[-1]))
c7 = list(itertools.chain.from_iterable(l7))
l8 = [[8]]

for _ in range(9):
    l8.append(a(l8[-1]))
c8 = list(itertools.chain.from_iterable(l8))

l9 = [[9]]

for _ in range(9):
    l9.append(a(l9[-1]))
c9 = list(itertools.chain.from_iterable(l9))

cc = c1+c2+c3+c4+c5+c6+c7+c8+c9


cc.sort()

print(cc[k-1])

Submission status: Accepted

Solution code:
import collections
import math
import operator as op
from functools import reduce
from collections import Counter
import numpy as np
import math
import bisect
import heapq


MOD = 1000000007


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def main():
    K = get_input(int)

    Lun = [None for _ in range(10)]
    for n in range(10):
        Lun[n] = [[] for _ in range(11)]
    for n in range(10):
        Lun[n][1].append(n)
    # print(Lun)

    for d in range(2, 11):
        for n in range(10):
            o = n*10**(d-1) 
            for i in [n-1, n, n+1]:
                if i >= 0 and i <= 9:
                    Lun[n][d].extend([l + o for l in Lun[i][d-1]])

    flag = True
    cnt = K
    for d in range(1, 11):
        for n in range(1, 10):
            if cnt - len(Lun[n][d]) <= 0:
                flag = False
                break
            else:
                cnt -= len(Lun[n][d])
        if not flag:
            break
    # print(n, d, cnt)
    # print(Lun[n][d])
    print(Lun[n][d][cnt-1])


    # Lun = np.zeros((10, 11), dtype=np.int64)
    # Lun[:, 1] = 1
    # for d in range(2, 11):
    #     for n in range(10):
    #         for i in [n-1, n, n+1]:
    #             if i >= 0 and i <= 9:
    #                 Lun[n, d] += Lun[i, d-1]





    # flag = True
    # cnt = K
    # for d in range(1, 11):
    #     for n in range(1, 10):
    #         if cnt - Lun[n, d] <= 0:
    #             flag = False
    #             break
    #         else:
    #             cnt -= Lun[n, d]
    #     if not flag:
    #         break
    # print(n, d, cnt)

    # ans = ""
    # cnt = K
    # flag = True
    # for d in range(1, 11):
    #     for n in range(1, 10):
    #         if cnt - Lun[n, d] <= 0:
    #             flag = False
    #             break
    #         else:
    #             cnt -= Lun[n, d]
    #     if not flag:
    #         break
    
    # ans = [None for _ in range(d)]
    # ans[0] = n

    # for _d in range(d-1, 0, -1):
    #     for n in range(1, 10):
    #         if 
    #         if cnt - Lun[n, d] <= 0:
    #             flag = False
    #             break
    #         else:
    #             cnt -= Lun[n, d]
    #     if not flag:
    #         break
 


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K = int(input())

ans = []
next_list = []
now_list = [""]
cnt = 0
while cnt < K:
    for now in now_list:
        if now == "":
            for i in range(1,10):
                next_list.append(str(i))
                ans.append(str(i))
                cnt += 1
        else:
            end = int(now[-1])
            for i in range(-1,2):
                i += end
                if i < 0 or i > 9:
                    continue
                next_list.append(now+str(i))
                ans.append(now+str(i))
                cnt += 1
    now_list = next_list
    next_list = []

print(ans[K-1])

Submission status: Accepted

Solution code:
import heapq
k = int(input())
l = [1,2,3,4,5,6,7,8,9]
heapq.heapify(l)
count = 0
now = 0
while count < k:
    #print(count,l)
    a = str(heapq.heappop(l))
    count += 1
    now = int(a)
    al = list(a)
    if al[-1] == "0":
        heapq.heappush(l,int(a+"0"))
        heapq.heappush(l,int(a+"1"))
    elif al[-1] == "9":
        heapq.heappush(l,int(a+"8"))
        heapq.heappush(l,int(a+"9"))
    else:
        heapq.heappush(l,int(a+str(int(al[-1])-1)))
        heapq.heappush(l,int(a+str(int(al[-1]))))
        heapq.heappush(l,int(a+str(int(al[-1])+1)))
print(now)

Submission status: Accepted

Solution code:
K = int(input())


cand = [[str(i)] for i in range(10)]


k = 9
end = 0

if K <= 9:
    print(K)
else:
    for j in range(10000000):
        new_cand = [[] for i in range(10)]
        for top in range(10):
            if top == 0:
                new = []
                new += [str(top) + rest for rest in cand[0]]
                new += [str(top) + rest for rest in cand[1]]
                new_cand[top] = new
            elif top != 0 and top != 9:
                new = []
                new += [str(top) + rest for rest in cand[top-1]]
                new += [str(top) + rest for rest in cand[top]]
                new += [str(top) + rest for rest in cand[top+1]]
                new_cand[top] = new
                if k + len(new) >= K:
                    print(new[K-k-1])
                    end = 1
                    break
                k += len(new)
            elif top == 9:
                new = []
                new += [str(top) + rest for rest in cand[8]]
                new += [str(top) + rest for rest in cand[9]]
                new_cand[top] = new
                if k + len(new) >= K:
                    print(new[K-k-1])
                    end = 1
                    break
                k += len(new)
        cand = new_cand
        if end == 1:
            break

Submission status: Accepted

Solution code:
import heapq
K = int(input())


def fun(h, n):
    tmp = str(n)
    if tmp[-1] == '0':
        heapq.heappush(h, int(tmp + '0'))
        heapq.heappush(h, int(tmp + '1'))
    elif tmp[-1] == '9':
        heapq.heappush(h, int(tmp + '8'))
        heapq.heappush(h, int(tmp + '9'))
    else:
        heapq.heappush(h, int(tmp + str(int(tmp[-1]) - 1)))
        heapq.heappush(h, int(tmp + tmp[-1]))
        heapq.heappush(h, int(tmp + str(int(tmp[-1]) + 1)))


h = list(range(1, 10))
while K > 0:
    tmp = heapq.heappop(h)
    fun(h, tmp)
    K -= 1
else:
    print(tmp)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    k = int(input())
    dp = [[[] for _ in range(10)] for _ in range(11)]
    
    num = ['0','1','2','3','4','5','6','7','8','9']
    for i in range(10):
        dp[1][i] = [num[i]]

    if k <= 9:
        print(*dp[1][k])
        return 
    
    cnt = 9
    for i in range(2,11):
        for l in range(len(dp[i - 1][0])):
            dp[i][0].append('0' + dp[i - 1][0][l])
        for l in range(len(dp[i - 1][1])):
            dp[i][0].append('0' + dp[i - 1][1][l])   

        for j in range(1,10):
            for l in range(len(dp[i - 1][j - 1])):
                dp[i][j].append(num[j] + dp[i - 1][j - 1][l])
                cnt += 1
                if cnt == k:
                    print(dp[i][j][-1])
                    #print(dp)
                    #print(num)
                    return

            for l in range(len(dp[i - 1][j])):
                dp[i][j].append(num[j] + dp[i - 1][j][l])
                cnt += 1
                if cnt == k:
                    print(dp[i][j][-1])
                    #print(dp)
                    #print(num)
                    return

            if j < 9:
                for l in range(len(dp[i - 1][j + 1])):
                    dp[i][j].append(num[j] + dp[i - 1][j + 1][l])
                    cnt += 1
                    if cnt == k:
                        print(dp[i][j][-1])
                        #print(dp)
                        #print(num)
                        #print(dp[2][1])
                        return
        

 
if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
k=int(input())
ans=[[i for i in range(1,10)]]
d=9
while d<k:
    ans.append([])
    for i in ans[-2]:
        x=str(i)
        y=int(x[0])
        if y==1:
            ans[-1].append(str(y)+x)
            ans[-1].append(str(y+1)+x)
        elif 2<=y<=8:
            ans[-1].append(str(y-1)+x)
            ans[-1].append(str(y)+x)
            ans[-1].append(str(y+1)+x)
        else:
            ans[-1].append(str(y-1)+x)
            ans[-1].append(str(y)+x)
        z=int(x[-1])
        if z==0:
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        elif 1<=z<=8:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        else:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
    ans[-1]=list(set(ans[-1]))
    d+=len(ans[-1])
l=len(ans[-1])
v=sorted([int(i) for i in ans[-1]])

print(v[k-(d-l)-1])

Submission status: Accepted

Solution code:
k=int(input())
count=0
def rec(l,keta,countive,s):
    global count
    global k
    #count
    if keta==1:
        if countive:
            count+=1
            if count==k:
                while s[0]=="0":
                    s=s[1:]
                print(s)
                return True #end flag
    #create next
    else:
        if l==0:
            if countive==False:#all l
                if rec(0,keta-1,False,s+str(0)):return True
                for i in range(1,10):
                    if rec(i,keta-1,True,s+str(i)):return True
            else:
                if rec(l,keta-1,True,s+str(l)):return True
                if rec(l+1,keta-1,True,s+str(l+1)):return True
        elif l==9:
            if rec(l-1,keta-1,True,s+str(l-1)):return True
            if rec(l,keta-1,True,s+str(l)):return True
        else:
            if rec(l-1,keta-1,True,s+str(l-1)):return True
            if rec(l,keta-1,True,s+str(l)):return True
            if rec(l+1,keta-1,True,s+str(l+1)):return True
rec(0,11,False,"0")

Submission status: Accepted

Solution code:
X = [i for i in range(1, 10)]
prev = X[:]
for i in range(9):
    ne = []
    for x in prev:
        s = x % 10
        ne.append(x * 10 + s)
        if s: ne.append(x * 10 + s - 1)
        if s < 9: ne.append(x * 10 + s + 1)
    X += ne
    prev = ne
X = sorted(X)
print(X[int(input()) - 1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10, 6))
N = 12
rs = []
def f(s, bb):
    if len(s) == N:
        rs.append(int(s))
        return
    b = int(s[-1])
    r = []
    if bb == 0:
        for i in range(10):
            if i == 0:
                f(s+str(i), bb)
            else:
                f(s+str(i), 1)
        return
    if b > 0:
        f(s+str(b-1), 1)
    f(s+str(b), 1)
    if b < 9:
        f(s+str(b+1), 1)

f(str(0), 0)
print(rs[int(input())])

Submission status: Accepted

Solution code:
def next(n):
    s = [int(i) for i in str(n)]
    l = len(s)
    if l == 1:
        return n + 1
    ans = s
    for i in range(l - 1):
        if s[-i - 1] <= s[-i - 2] and s[-i - 1] != 9:
            ans = s[:-i - 1]
            ans.append(s[-i - 1] + 1)
            for j in range(i):
                if ans[-1] == 0:
                    ans.append(0)
                else:
                    ans.append(ans[-1] - 1)
            return int(''.join([str(i) for i in ans]))
    if s[0] == 9:
        return n + 1
    ans = [s[0] + 1]
    for j in range(l - 1):
        if ans[-1] == 0:
            ans.append(0)
        else:
            ans.append(ans[-1] - 1)
    return int(''.join([str(i) for i in ans]))


K = int(input())
ans = 1
for i in range(K - 1):
    ans = next(ans)
print(ans)