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.

Solution (Python):
from collections import deque
k = int(input())

q = deque([i for i in range(1,10)])

for i in range(1,k+1):
  x = q.popleft()
  
  if i == k:
    print(x)
    exit()
    
  if x%10 != 0:
    q.append(10*x+(x%10)-1)
    
  q.append(10*x+(x%10))
  
  if x%10 != 9:
    q.append(10*x+(x%10)+1)

Solution (Python):
def dfs(x):
    ans.append(x)
    if len(str(x))==10:
        return
    
    last=x%10
    
    for i in [last-1,last,last+1]:
        if 0<=i<=9:
            dfs(10*x+i)

k=int(input())
ans=[]
for i in range(1,10):
    dfs(i)
    
ans=sorted(ans)
print(ans[k-1])

Solution (Python):
k=int(input())  
l=[1,2,3,4,5,6,7,8,9]  
for i in range(k):  
  x=l[i]  
  if x%10!=0:  
    l.append(10*x+x%10-1)  
  l.append(10*x+x%10)  
  if x%10!=9:  
    l.append(10*x+x%10+1)  
print(x)

Solution (Python):
k = int(input())

ls = []
for i in range(1,10):
  ls.append(i)
idx_next = 0
for i in range(1,10):
  idx = idx_next
  idx_next = len(ls)
  for v in ls[idx:]:
    r = v%10
    if r-1 >= 0:
      ls.append(v*10+r-1)
    ls.append(v*10+r)
    if r+1 <= 9:
      ls.append(v*10+r+1)
print(ls[k-1])

Solution (Python):
k = int(input())
L = [1,2,3,4,5,6,7,8,9]
i = 0
while i < k:
    if int(str(L[i])[-1]) == 0:
        n2 = L[i]*10 + L[i]%10
        n3 = L[i]*10 + L[i]%10 +1
        L.append(n2)
        L.append(n3)
    elif 1 <= int(str(L[i])[-1]) <= 8:
        n1 = L[i]*10 + L[i]%10 -1
        n2 = L[i]*10 + L[i]%10
        n3 = L[i]*10 + L[i]%10 +1
        L.append(n1)
        L.append(n2)
        L.append(n3)
    elif int(str(L[i])[-1]) == 9:
        n1 = L[i]*10 + L[i]%10 -1
        n2 = L[i]*10 + L[i]%10
        L.append(n1)
        L.append(n2)
    i +=1

print(L[k-1])

Solution (Python):
K = int(input())
lunlun = []

def dfs(x):
    lunlun.append(x)
    if len(str(x))==10:
        return
    d = x % 10
    for v in [d-1,d,d+1]:
        if 0<= v <= 9:
            dfs(x*10+v)

for i in range(1, 10):
    dfs(i)

lunlun.sort()
print(lunlun[K-1])

Solution (Python):
def solve():
    K = int(input())
    all = []
    for i in range(1,10):
        dfs(1,i,all)
    
    all.sort()
    print(all[K-1])
    
def dfs(d, val, all):
    all.append(val)

    if d == 10:
        return
    
    for j in [-1,0,1]:
        add = val % 10 + j
        if 0 <= add <= 9:
            dfs(d+1, val*10+add, all)

if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque

K = int(input())
q = deque()
for i in range(1, 10):
    q.append(i)
for _ in range(K - 1):
    x = q.popleft()
    if x % 10:
        q.append(10 * x + x % 10 - 1)
    q.append(10 * x + x % 10)
    if x % 10 != 9:
        q.append(10 * x + x % 10 + 1)
print(q.popleft())

Solution (Python):
from collections import deque
import sys

k = int(input())
d = deque()
c = 1

while True:
    if c < 10:
        d.append(c)
        c += 1
        if c > k:
            print(d.pop())
            sys.exit()
    else:
        n = d.popleft()
        m = n % 10
        for i in range(-1, 2):
            if 0 <= m + i <= 9:
                d.append(n * 10 + m + i)
                c += 1
                if c > k:
                    print(d.pop())
                    sys.exit()

Solution (Python):
k = int(input())
RUNRUN_numbers = []

def RN(x,y):

    RUNRUN_numbers.append(y)

    if y > 10**9:
        return
    if x == 0:
        for i in range(0,2):
            
            yy = 10*y + i
            RN(i,yy)
    elif x == 9:
        for i in range(8,10):
            
            yy = 10*y + i
            RN(i,yy)
    else:
        for i in range(x-1,x+2,1):
            
            yy = 10*y + i
            RN(i,yy)


for i in range(1,10):
    RN(i,i)

RUNRUN_numbers.sort()
print(RUNRUN_numbers[k-1])

Solution (Python):
k=int(input())
li=[str(i) for i in range(1,10)]

for j in range(k):
    t=li[j]
    if t[-1]!="0":
        li.append(t+str(int(t[-1])-1))
    
    li.append(t+str(int(t[-1])))
        
    if t[-1]!="9":
        li.append(t+str(int(t[-1])+1))

print(li[k-1])

Solution (Python):
from collections import deque

K = int(input())

dq = deque(list(range(1,10)))

for i in range(K):
    now = dq.popleft()
    for i in (-1,0,1):
        add = (now%10)+i
        if 0 <= add<10:
            dq.append(now*10+add)

print(now)

Solution (Python):
import math

k = int(input())

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

c = 0
while k > len(l):
    f = l[c] - (l[c] // 10 * 10)

    if f != 0:
        l.append(l[c] * 10 + f - 1)

    l.append(l[c] * 10 + f)

    if f != 9:
        l.append(l[c] * 10 + f + 1)

    c += 1

print(l[k - 1])

Solution (Python):
def main():
    k = int(input())
    a = [i for i in range(1,10)]
    x = 0
    while(1):
        if k <= len(a):
            print(a[k-1])
            return
        for i in range(-1,2):
            d = a[x]%10 +i
            if 0 <= d and d < 10:
                a.append(a[x]*10 + d)
        x+=1

if __name__ == "__main__":
    main()

Solution (Python):
def dfs(A,B):
    if len("".join(A))>10:
        return
    if int(A[-1]) == 0:
        for i in [0,1]:
            A.append(str(i))
            B.append("".join(A))
            dfs(A, B)
            A.pop()
    elif int(A[-1]) == 9:
        for i in [8,9]:
            A.append(str(i))
            B.append("".join(A))
            dfs(A, B)
            A.pop()
    else:
        for i in range(int(A[-1])-1,int(A[-1])+2):
            A.append(str(i))
            B.append("".join(A))
            dfs(A,B)
            A.pop()

if __name__ == "__main__":
    k=int(input())
    ans_list=[]
    num_list=[]
    for i in range(1,10):
        ans_list.append(str(i))
        num_list.append(str(i))
        dfs(num_list,ans_list)
        num_list.clear()
    ans_list=sorted(ans_list,key=int)
    print(ans_list[k-1])

Solution (Python):

from collections import deque
k = int(input())

dq = deque(list(range(1, 10)))
rep = 0
while rep < k:
    now = dq.popleft()
    rep+=1
    for i in (-1, 0, 1):
        if 0<=now%10+i<10:
            dq.append(now*10+now%10+i)
print(now)

Solution (Python):
K = int(input())

LLs = []

def dfs(d, num):
    LLs.append(num)
    
    if d == 10: return

    a = num % 10
    for i in [-1, 0, 1]:
        b = a + i
        if  0 <= b < 10:
            dfs(d+1, num * 10 + b)

d = 1
for i in range(1, 10):
    dfs(d, i)

print(sorted(LLs)[K-1])

Solution (Python):
import math
import copy
from queue import Queue

n = int(input())














queue = Queue()
temp = 0

if (n < 10):
    print(n)
else:
    for i in range(1,10):
        queue.put(i)
    for i in range(1,n):
        temp = queue.get()
        if (temp % 10 != 0) :
            queue.put(10 * temp + (temp % 10) - 1)
        queue.put(10 * temp + (temp % 10))
        if (temp % 10 != 9) :
            queue.put(10 * temp + (temp % 10) + 1)
    print(queue.get())

Solution (Python):
K = int(input())

runrun_pool = [list(range(1,10))]
runrun_num = len(runrun_pool[0])
digit = 1

while runrun_num < K:
    tmp = list()
    for i in runrun_pool[digit-1]:
        if i % 10 == 0:
            tmp.append(i * 10 + i % 10)
            tmp.append(i * 10 + i % 10 + 1)
        elif i % 10 == 9:
            tmp.append(i * 10 + i % 10 - 1)
            tmp.append(i * 10 + i % 10)
        else:
            tmp.append(i * 10 + i % 10 - 1)
            tmp.append(i * 10 + i % 10)
            tmp.append(i * 10 + i % 10 + 1)
    runrun_pool.append(tmp)         
    runrun_num += len(runrun_pool[digit])
    digit += 1

num = K
for i in range(digit-1):
    num -= len(runrun_pool[i])
    
print(runrun_pool[digit-1][num-1])

Solution (Python):
from collections import deque
k = int(input())

dq = deque(list(range(1, 10)))
rep = 0
while rep < k:
    now = dq.popleft()
    rep+=1
    for i in (-1, 0, 1):
        if 0<=now%10+i<10: dq.append(now*10+now%10+i)
print(now)

Solution (Python):
K = int(input())

def dfs(A, li):
    if len(A)==10:
        return
    
    for i in right(A):
        A.append(i)
        A_int = int(''.join(map(str, A)))
        li.append(A_int)
        dfs(A, li)
        A.pop()
    return
        
def right(A):
    if A==[]:
        return [x for x in range(1, 10)]
    
    ret = A[-1]
    if ret==9:
        return [8, 9]
    elif ret==0:
        return [0, 1]
    else:
        return [ret-1, ret, ret+1]

li = []    
dfs([], li)
li.sort()

print(li[K-1])

Solution (Python):
k = int(input())

all_lun = []
def dfs(d):
    all_lun.append(d)
    if len(str(d))==10:
        return
    for i in [-1, 0, 1]:
        if 0<=d%10+i<10: dfs(d*10+d%10+i)
for i in range(1, 10):
    dfs(i)
all_lun.sort()
print(all_lun[k-1])

Solution (Python):
from collections import deque

def main():
    K = int(input())
    if K <= 9:
        print(K)
        return

    que = deque(range(1,10))
    
    cnt = 9
    while True:
        x = que.popleft()
        mod = x % 10

        if mod != 0:
            que.append(10 * x + mod - 1)
            
            cnt += 1
            if cnt == K:
                print(que[-1])
                return

        que.append(10 * x + mod)
        
        cnt += 1
        if cnt == K:
            print(que[-1])
            return

        if mod != 9:
            que.append(10 * x + mod + 1)
            
            cnt += 1
            if cnt == K:
                print(que[-1])
                return

main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    k = I()

    m = {}
    def f(i,t):
        k = (i,t)
        if k in m:
            return m[k]

        r = 0
        if i == 1:
            if t == -1:
                r = 9
            elif t == 0 or t == 9:
                r = 2
            else:
                r = 3
        else:
            if t == -1:
                r += f(i-1, -1)
                for nt in range(1, 10):
                    r += f(i-1, nt)
            else:
                for nt in range(max(0,t-1), min(10, t+2)):
                    r += f(i-1, nt)
        m[k] = r
        return r

    def g(i, t, k):
        if i == 1:
            if t == -1:
                return k
            if t == 0:
                return k - 1
            return t + k - 2

        if t == -1:
            f1 = f(i-1, -1)
            if f1 >= k:
                return g(i-1, -1, k)
            k -= f1
            for j in range(1, 10):
                fj = f(i-1, j)
                if fj >= k:
                    r = g(i-1, j, k)
                    return r + j * 10**(i-1)
                k -= fj
        else:
            for j in range(max(0, t-1), min(10, t+2)):
                fj = f(i-1, j)
                if fj >= k:
                    r = g(i-1, j, k)
                    return r + j * 10**(i-1)
                k -= fj

    r = g(11, -1, k)
    return r

print(main())

Solution (Python):

def abc161_d():
  k = int(input())
  lunlun = []

  def rec(d, val):
    
    lunlun.append(val)
    
    if d == 10: return
    
    for j in range(-1, 2):
      add = val % 10 + j
      if 0 <= add and add <= 9:
        rec(d+1, val*10 + add)

  
  for i in range(1, 10):
    rec(1, i)
  lunlun.sort()
  ans = lunlun[k-1]
  print(ans)

abc161_d()

Solution (Python):
from collections import deque

k = int(input())

a = deque([9,8,7,6,5,4,3,2,1])
current_num = 0

for i in range(k):
  current_num = a.pop()
  current_str = str(current_num)
  current_last = int(current_str[-1])

  up = ""  
  mid = current_str + str(current_last)
  down = ""

  if current_last >= 0 and current_last <= 8:
    up = current_str + str(current_last + 1)

  if current_last >= 1 and current_last <= 9:
    down = current_str + str(current_last - 1)
  
  if len(down) != 0:
    a.appendleft(down)

  a.appendleft(mid)

  if len(up) != 0:
    a.appendleft(up)

print(current_num)

Solution (Python):
def plus(x):
    X = str(x)
    p = int(X[len(X)-1])
    if p == 0:
        return(int(X+str(p)), int(X+str(p+1)))
    elif p == 9:
        return(int(X+str(p-1)), int(X+str(p)))
    else:
        return(int(X+str(p-1)), int(X+str(p)), int(X+str(p+1)))
    
A = [[] for _ in range(10)]
for i in range(1,10):
    A[0].append(i)
    
for i in range(1,10):
    for j in A[i-1]:
        A[i].extend(plus(j))
ans = sum(A,[])
print(ans[int(input())-1])

Solution (Python):
from collections import deque

K = int(input())
que = deque(list(range(1, 10)))

c = 0
while que:
    n = que.popleft()
    s = str(n)

    flg = True

    for i in range(1, len(s)):
        if abs(int(s[i])-int(s[i-1])) >= 2:
            flg = False

    if flg:
        c += 1

    if c == K:
        print(s)
        exit()

    if n % 10 != 0:
        que.append(n*10+n % 10-1)

    que.append(n*10+n % 10)

    if n % 10 != 9:
        que.append(n*10+n % 10+1)

Solution (Python):

import sys
from collections import deque

def solve(K: int):

    ct = 0
    q = deque([1,2,3,4,5,6,7,8,9])
    while(len(q)>0):
        a = q.popleft()
        al = a % 10
        ct += 1 
        if ct == K:
            print(a)
            break

        if al != 0:
            q.append(a*10+al - 1)
        q.append(a*10+al)
        if al != 9:
            q.append(a*10+al + 1)

        


    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  
    solve(K)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
k = int(input())
from collections import deque
d = deque()
for i in range(9):
    d.append(str(i+1)) 

def dfs():
    global cnt
    a = d.popleft()
    
    
    for i in range(-1,2,1):
        nya = a
        last_string = int(a[-1]) + i
        if last_string < 0 or last_string > 9:
            pass
        else:
            nya += str(last_string)
            cnt += 1
            if k == cnt:
                print(nya)
                exit()
            d.append(nya)
    dfs()

cnt = 9
if k <= cnt:
    print(k)
    exit()
dfs()

Solution (Python):
import sys
K = int(input())

listup = []
listup.append(list(range(1, 10)))
list_length = 9
if K <= 9:
    print(listup[0][K - 1])
    sys.exit(0)
for i in range(10000000):
    new_list_floor = []
    for value in listup[i]:
        newlist = []
        mod_value = value % 10
        if mod_value == 0:
            newlist.append(value * 10 + mod_value)
            newlist.append(value * 10 + mod_value + 1)
        elif mod_value == 9:
            newlist.append(value * 10 + mod_value - 1)
            newlist.append(value * 10 + mod_value)
        else:
            newlist.append(value * 10 + mod_value - 1)
            newlist.append(value * 10 + mod_value)
            newlist.append(value * 10 + mod_value + 1)
        list_length_before = list_length
        list_length += len(newlist)
        new_list_floor.extend(newlist)
        if list_length >= K:
            diff = K - list_length_before
            print(newlist[diff - 1])
            sys.exit(0)
    listup.append(new_list_floor)
print(listup)

Solution (Python):
def dfs(l, r):
    if len(r) == 11:
        return
    l.append(int(r))
    for i in range(-1, 2):
        tmp = int(r[-1]) + i
        if 0 <= tmp <= 9:
            dfs(l, r + str(tmp))


k = int(input())
l = []
for i in range(1, 10):
    dfs(l, str(i))
print(sorted(l)[k - 1])

Solution (Python):
import heapq
K=int(input())
queue=[i for i in range(1,10)]
heapq.heapify(queue)
for i in range(K-1):
    n=heapq.heappop(queue)
    if n%10==0:
        heapq.heappush(queue,n*10+0)
        heapq.heappush(queue,n*10+1)
    elif n%10==9:
        heapq.heappush(queue,n*10+8)
        heapq.heappush(queue,n*10+9) 
    else:
        heapq.heappush(queue,n*10+(n%10))
        heapq.heappush(queue,n*10+(n%10)+1)
        heapq.heappush(queue,n*10+(n%10)-1)
print(queue[0])

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

def dfs(n, before):
    global cnt, K, ans, flag
    ints = int(before[-1])
    int1s = ints - 1; ints1 = ints + 1

    if int1s >= 0:
        after1s = before + str(int1s)
        if n == 1: 
            cnt += 1
        if cnt == K and flag == 0:
            ans = after1s; flag = 1
            return
        if n >= 2:
            dfs(n-1, after1s)
    
    afters = before + str(ints)
    if n == 1:
        cnt += 1
    if cnt == K and flag == 0:
        ans = afters; flag = 1
        return
    if n >= 2:
        dfs(n-1, afters)

    if ints1 <= 9:
        afters1 = before + str(ints1)
        if n == 1:
            cnt += 1
        if cnt == K and flag == 0:
            ans = afters1; flag = 1
        if n >= 2:
            dfs(n-1, afters1)


def main():
    global cnt, K, ans, flag
    K = int(input())
    if K <= 9:
        print(K)
        return
    cnt = 9
    flag = 0
    for n in range(1, 13):
        for s in range(1, 10):
            dfs(n, str(s))
            if flag == 1:
                break
        if flag == 1:
            break
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def dfs(r):
    global l
    if len(r) == 11:
        return
    l.append(int(r))
    for i in range(-1, 2):
        tmp = int(r[-1]) + i
        if 0 <= tmp <= 9:
            dfs(r + str(tmp))


k = int(input())
l = []
for i in range(1, 10):
    dfs(str(i))
print(sorted(l)[k - 1])

Solution (Python):
c = int(input())

l = list(range(1, 10))

j = 0

if c < 10:
    print(l[c-1])

else:
    c -= 9

    while True:
        new_l = []
        for i in l:
            d = i % 10
            if d != 0:
                new_l.append(10*i+d-1)
            
            new_l.append(10*i+d)

            if d != 9:
                new_l.append(10*i+d+1)

        if c <= len(new_l):
            new_l.sort()
            print(new_l[c-1])
            break
        else:
            c -= len(new_l)
            l = new_l

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')
from collections import deque


def solve():
    k = II()
    q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

    if k <= 9:
        print(q[k-1])
        return

    cnt = len(q)
    while 1:
    
        a = q.popleft()
        
        one = int(str(a)[-1])
        for i in range(one-1, one+2):
            
            if i < 0 or i > 9:
                continue
            num = int(str(a) + str(i))
            cnt += 1
            
            if cnt == k:
                print(num)
                return

            q.append(num)
        


if __name__ == '__main__':
    solve()

Solution (Python):
N = int(input())
num = [str(i) for i in range(1, 10)]
lunlun = num
for i in range(10):
    temp_list = []
    for j in num:
        temp = int(j[-1])
        if 0 < temp < 9:
            temp_list.append(j + str(temp - 1))
            temp_list.append(j + str(temp))
            temp_list.append(j + str(temp + 1))
        elif temp == 0:
            temp_list.append(j + str(temp))
            temp_list.append(j + str(temp + 1))
        else:
            temp_list.append(j + str(temp - 1))
            temp_list.append(j + str(temp))
    num = temp_list
    lunlun = lunlun + num
lunlun = [int(l) for l in lunlun]
lunlun = list(set(lunlun))
lunlun.sort()
print(lunlun[N - 1])

Solution (Python):
from collections import deque
k = int(input())
if k <= 9: print(k)
que = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
count = 9
while count <= k:
    X = que.popleft()
    if X%10==0: check=[0, 1]
    elif X%10==9: check=[8, 9]
    else: check = [X%10-1, X%10, X%10+1]
    for i in check:
        que.append(X*10+i)
        count += 1
        if count == k:
            print(que[-1])
            exit()

Solution (Python):

from collections import deque
d = deque(range(1, 10))
Dequeue = lambda: d.popleft()
Enqueue = lambda x: d.append(x)

for _ in range(int(input())):
    x = Dequeue()
    m = x%10
    if m != 0: Enqueue(10*x + m-1)
    if True  : Enqueue(10*x + m)
    if m != 9: Enqueue(10*x + m+1)
print(x)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    k = int(input())
    res = []

    def dfs(x):
        res.append(x)
        if len(str(x)) == 10:
            return

        for i in range(10):
            if abs(x % 10 - i) <= 1:
                dfs(x * 10 + i)

        return

    for i in range(1, 10):
        dfs(i)
    res.sort()
    print(res[k - 1])


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque
k = int(input())

def dfs(k):
  cnt = 0
  stack = deque()
  for i in range(1, 10):
    stack.append(i)
  while cnt <= k:
    q = stack.popleft()
    ans.append(q)
    cnt += 1
    l = q % 10
    for x in range(max(0, l - 1), min(10, l + 2)):
      stack.append(q * 10 + x)
          
ans = []
dfs(k)
print(ans[k-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
k = int(readline())

X = [[i for i in range(1, 10)]]
for i in range(9):
    Y = []
    for x in X[-1]:
        s = x % 10
        if s == 0:
            Y.append(x*10+s)
            Y.append(x*10+s+1)
        elif s == 9:
            Y.append(x*10+s-1)
            Y.append(x*10+s)
        else:
            Y.append(x*10+s-1)
            Y.append(x*10+s)
            Y.append(x*10+s+1)
    X.append(Y)

XX = []
for x in X:
    XX += x[:]


print(XX[k-1])

Solution (Python):
k = int(input())
l = []
for i in range(1, 10):
    l.append(i)
judge = l
for d in range(1, 10):
    tmp = []
    for i in range(len(judge)):
        val = judge[i]
        for j in range(-1, 2):
            add = val%10 + j
            if add >= 0 and add <= 9:
                tmp.append(val*10 + add)
    for i in range(len(tmp)):
        l.append(tmp[i])
    judge = tmp
print(l[k-1])

Solution (Python):
import queue
K = int(input())

lunlun_queue = queue.Queue()

for i in range(1, 10):
    lunlun_queue.put(i)

for i in range(K):
    ans = lunlun_queue.get()

    if(ans % 10 != 0):
        lunlun_queue.put(ans * 10 + ans % 10 - 1)
    
    lunlun_queue.put(ans * 10 + ans % 10)

    if(ans % 10 != 9):
        lunlun_queue.put(ans * 10 + ans % 10 + 1)
'''
while not lunlun_queue.empty():
    print(lunlun_queue.get())
'''
print(ans)

Solution (Python):
import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=q
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)


K = readInt()

q = queue.Queue()

for i in range(1,10):
	q.put(i)

ans = 0
for i in range(K):
	ans = q.get()
	if str(ans)[-1]=="0":
		q.put(int(str(ans)+"0"))
		q.put(int(str(ans)+"1"))
	elif str(ans)[-1]=="9":
		q.put(int(str(ans)+"8"))
		q.put(int(str(ans)+"9"))
	else:
		q.put(int(str(ans)+str(int(str(ans)[-1])-1)))
		q.put(int(str(ans)+str(int(str(ans)[-1]))))
		q.put(int(str(ans)+str(int(str(ans)[-1])+1)))

print(ans)

Solution (Python):
k = int(input())
A = [1,2,3,4,5,6,7,8,9]
for i in A:
    if len(A) > k:
        break
    x = i%10
    for j in range(max(x-1, 0), min(x+2, 10)):
        A.append(10*i+j)
print(A[k-1])

Solution (Python):
K = int(input())
table = [1,2,3,4,5,6,7,8,9]
for i in table:
  if len(table) > K:
    break
  x = i % 10
  for j in range(max(0, x - 1), min(x + 2, 10)):
    table.append(i * 10 + j)
print(table[K-1])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

runrun = [None for _ in range(100)]
runrun[1] = (1, 2, 3, 4, 5, 6, 7, 8, 9)


def gen_runrun_keta(k):
    for x in runrun[k - 1]:
        r = x % 10
        if r > 0:
            yield 10 * x + (r - 1)
        yield 10 * x + r
        if r < 9:
            yield 10 * x + (r + 1)


for keta in range(2, 11):
    runrun[keta] = tuple(gen_runrun_keta(keta))


rest = int(read())

answer = 0
for n in range(1, 11):
    if rest <= len(runrun[n]):
        answer = runrun[n][rest - 1]
        break
    rest -= len(runrun[n])
print(answer)

Solution (Python):
from collections import deque
k=int(input())
cand=["1","2","3","4","5","6","7","8","9"]
cand=deque(cand)
lunlun=['0']
while len(lunlun)<10**5+5:
    l=cand.popleft()
    lunlun.append(l)
    if l[-1]!='0':
        cand.append(l+str(int(l[-1])-1))
    cand.append(l+str(int(l[-1])))
    if l[-1]!='9':
        cand.append(l+str(int(l[-1])+1))
print(lunlun[k])

Solution (Python):
import queue

q = queue.Queue()

k = int(input())

for i in range(1,10):
    q.put(i)
    
while(k > 0):
    x = q.get()
    if x % 10 != 0:
        q.put(x*10 + (x%10 - 1))
    q.put(x*10 + x%10)
    if x % 10 != 9:
        q.put(x*10 + (x%10 + 1))
    k -= 1
    
print(x)

Solution (Python):
import queue

q = queue.Queue()

k = int(input())

for i in range(1,10):
    q.put(i)
    
while(k > 0):
    x = q.get()
    if x % 10 != 0:
        q.put(x*10 + (x%10 - 1))
    q.put(x*10 + x%10)
    if x % 10 != 9:
        q.put(x*10 + (x%10 + 1))
    k -= 1
    
print(x)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
cnt = 0
def main():
    K = int(readline())
    cnd = [i for i in range(1, 10)]

    dq = deque()
    for i in range(1, 10):
        dq.append(i)

    cnt = 0 
    while len(dq)>0:
        cnt += 1
        x = dq.popleft()
        v = x%10
        if v==0:
            for i in (0, 1):
                nx = 10*x+i
                cnd.append(nx)
                dq.append(nx)
        elif v == 9:
            for i in (-1, 0):
                nx = 10*x+9+i
                cnd.append(nx)
                dq.append(nx)
        else:
            for i in (-1, 0, 1):
                nx = 10*x+v+i
                cnd.append(nx)
                dq.append(nx)
        if cnt == K:
            break 
    cnd.sort()
    print(cnd[K-1])
if __name__ == '__main__':
    main()

Solution (Python):


import queue

K = int(input())

Q = queue.Queue()
for i in range(1, 10):
    Q.put(i)
ans = 0
for _ in range(K):
    ans = Q.get()
    if ans % 10 != 0:
        Q.put((10 * ans) + (ans % 10) - 1)
    Q.put((10 * ans) + (ans % 10))
    if ans % 10 != 9:
        Q.put((10 * ans) + (ans % 10) + 1)

print(ans)

Solution (Python):
from collections import deque
K=int(input())
res = 0
deq = deque(['1','2','3','4','5','6','7','8','9'])
for i in range(K):
    now = deq.popleft()
    if i==K-1:
       res = int(now)
       break

    if now[-1] != '0':
        tmp = str(int(now[-1])-1)
        deq.append(now+tmp)
    tmp = now + now[-1]
    deq.append(tmp)
    if now[-1] != '9':
        tmp = str(int(now[-1])+1)
        deq.append(now+tmp)

print(res)

Solution (Python):
import sys

k = int(input())
q = []

for i in range(1, 10):
  q.append(i)

for i in range(k):
  
  n = q[i]
  
  if i == k - 1:
    print(n)
    sys.exit()
    
  if n % 10 != 0:
    q.append(10*n + (n % 10) - 1)
    
  q.append(10*n + (n % 10))
  
  if n % 10 != 9:
    q.append(10*n + (n % 10) + 1)

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

K = int(input())

lunlun = []
def dfs(i,before):
    if i == 11:
        return
    lunlun.append(before)
    back = before%10
    for j in range(-1,2):
        t = back + j
        if 0 <= t < 10:
            dfs(i + 1,before*10 + t)

for i in range(1,10):
    dfs(1,i)
lunlun.sort()
print(lunlun[K - 1])

Solution (Python):
K = int(input())
r = [[] for _ in range(10)]
r[0] = list(range(1,10))

for i in range(9):
  for a in r[i]:
    s = str(a)
    d = a%10
    for j in range(d-1, d+2):
      if not 0 <= j <= 9: continue
      r[i+1].append(int(s+str(j)))

for i in range(10):
  if K >= len(r[i]):
    K -= len(r[i])
  else:
    print(r[i][K-1])
    break

Solution (Python):
from collections import deque
K = int(input())

d = deque()

for i in range(1,10):
	d.append(i)

for i in range(K):
	x = d.popleft()
	if x % 10 != 0:
		d.append(10*x+(x%10)-1)
	d.append(10*x+(x%10))
	if x % 10 != 9:
		d.append(10*x+(x%10)+1)

print(x)

Solution (Python):
def main():
    from collections import deque

    K = int(input())

    dq = deque([i for i in range(1, 10)])

    cnt = 0

    while dq:
        x = dq.popleft()
        cnt += 1
        if cnt == K:
            print(x)
            return

        r = x % 10

        s = max(0, r - 1)
        t = min(9, r + 1)

        for k in range(s, t + 1):
            dq.append(x * 10 + k)


if __name__ == '__main__':
    main()

Solution (Python):
lunlun = []


def dfs(x):
    lunlun.append(x)
    if x > 3234566667:
        return 0
    d = x % 10
    if d != 0:
        dfs(10*x+d-1)
    dfs(10*x+d)
    if d != 9:
        dfs(10*x+d+1)


for i in range(1, 10):
    dfs(i)

lunlun.sort()
k = int(input())
print(lunlun[k-1])

Solution (Python):
from collections import deque
k = int(input())


def generate_lunlun(x):
    d = int(x) % 10
    if d != 0:
        yield x+str(d-1)
    yield x+str(d)
    if d != 9:
        yield x+str(d+1)


d = deque([str(i) for i in range(1, 10)])
for _ in range(k):
    x = d.popleft()
    for y in generate_lunlun(x):
        d.append(y)
print(x)