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

import sys
sys.setrecursionlimit(10**6+1)
K = int(input())

ans = []
def dfs(A):
    if len(A)>=2:
        A_str = [str(i) for i in A] 
        A_str = ''.join(A_str)
        ans.append(int(A_str))
    if len(A) == 10:
        return
    if len(A) >= 1:
        
        if A[-1] == 9:
            sta = 8
            fin = 9+1
        elif A[-1] == 0:
            sta = 0
            fin = 1+1
        else:
            sta = A[-1] - 1
            fin = A[-1] + 1 + 1
        for v in range(sta,fin):
            A.append(v)
            dfs(A)
            A.pop()
    else:
        for v in range(1,9+1):
            A.append(v)
            dfs(A)
            A.pop()
dfs([])
ans = sorted(ans,reverse = False)
if K<=9:
    print(K)
else:
    print(ans[K-10])

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

def rec(d, n, array):
    array.append(n)

    if d == 10:
        return
    
    for i in [-1, 0, 1]:
        add = n % 10 + i
        if 0 <= add <= 9:
            rec(d + 1, 10 * n + add, array)


array = []
for i in range(1, 10):
    rec(1, i, array)

s_array = sorted(array)
ans = s_array[k - 1]
print(ans)

Solution (Python):
K = int(input())
ls = []
def rec(digit, ini):
    ls.append(ini)
    if digit == 10: 
        return
    deltas = []
    if ini % 10 == 0:
        deltas = [0, 1]
    elif ini % 10 == 9:
        deltas = [-1, 0]
    else:
        deltas = [-1, 0, 1]
    for delta in deltas:
        new = ini * 10 + ini % 10 + delta
        rec(digit+1, new)

for ini in range(1, 10):
    rec(1, ini)
print(sorted(ls)[K-1])

Solution (Python):
from collections import deque
K = int(input())
que = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
for i in range(K):
    num = que.popleft()
    if i == K-1:
        print(num)
        break
    if num%10 == 0:
        que.append(num*10 + num%10)
        que.append(num*10 + num%10 + 1)
    elif num%10 == 9:
        que.append(num*10 + num%10 - 1)
        que.append(num*10 + num%10)
    else:
        que.append(num*10 + num%10 - 1)
        que.append(num*10 + num%10)
        que.append(num*10 + num%10 + 1)

Solution (Python):
from collections import deque
k=int(input())
d=deque([1,2,3,4,5,6,7,8,9])
num=[1,2,3,4,5,6,7,8,9]
while d:
  now=d.popleft()
  hitoketa=now%10
  for i in [-1,0,1]:
    if 0<=hitoketa+i<=9:
      nxt=now*10+hitoketa+i
      if nxt<=3234566667:
        
        num.append(nxt)
        d.append(nxt)
num.sort()
print(num[k-1])

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

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

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

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

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

import queue

que = queue.Queue()

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

for i in range(1, k + 1):
    ans = que.get()
    keta1 = ans % 10
    if keta1 == 0:
        append_list = [ans * 10, ans * 10 + 1]
    elif keta1 == 9:
        append_list = [ans * 10 + 8, ans * 10 + 9]
    else:
        append_list = [ans * 10 + keta1 - 1, ans * 10 + keta1, ans * 10 + keta1 + 1]
    for item in append_list:
        que.put(item)
print(ans)

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

import queue

que = queue.Queue()

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

for i in range(1, k + 1):
    ans = que.get()
    keta1 = ans % 10
    if keta1 == 0:
        append_list = [ans * 10, ans * 10 + 1]
    elif keta1 == 9:
        append_list = [ans * 10 + 8, ans * 10 + 9]
    else:
        append_list = [ans * 10 + keta1 - 1, ans * 10 + keta1, ans * 10 + keta1 + 1]
    for ite in append_list:
        que.put(ite)
print(ans)

Solution (Python):
from collections import deque

N = int(input())

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

for i in range(N - 1):
    x = Q.popleft()
    if x % 10 != 0:
        y = 10 * x + x % 10 - 1
        Q.append(y)
    
    y = 10 * x + x % 10
    Q.append(y)

    if x % 10 != 9:
        y = 10 * x + x % 10 + 1
        Q.append(y)

ans = Q.popleft()

print(ans)

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-1):
    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(d.popleft())

Solution (Python):
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())
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    runrun_lst = []
    def rec(num_of_digit, runrun_val):
        runrun_lst.append(runrun_val)
        if num_of_digit == 10: return
        for i in range(-1, 2):
            add = (runrun_val%10) + i
            if 0 <= add <= 9: rec(num_of_digit+1, runrun_val*10+add)

    for v in range(1, 10):
        rec(1, v)
    runrun_lst.sort()
    print(runrun_lst[K-1])

if __name__ == '__main__':
    main()

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

def dfs(lun):
  
  num.append(lun)
  if lun>3234566667:
    return
  now=lun%10
  for i in [-1,0,1]:
    if 0<=now+i<=9:
      dfs(lun*10+now+i)

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

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

Solution (Python):


def solver(d, v, a):
  a.append(v)
  if d == 10:
    return

  for i in range(-1, 2):
    add = (v % 10) + i;
    if add < 0 or 9 < add:
      continue
    solver(d + 1, v * 10 + add, a)

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

  a = []
  for i in range(1, 10):
    solver(1, i, a)
  a.sort();

  print(a[k - 1])

if __name__ == "__main__":
  main()

Solution (Python):
K = int(input())
A = [i for i in range(1, 10)]
if K <= 9:
  print(A[K-1])
else:
  K -= 9
  f = 1
  while f:
    B = []
    for a in A:
      k = a % 10
      if k != 0:
        B.append(a * 10 + k - 1)
        K -= 1
      if K == 0:
        print(B[-1])
        f = 0
        break
      B.append(a * 10 + k)
      K -= 1
      if K == 0:
        print(B[-1])
        f = 0
        break
      if k != 9:
        B.append(a * 10 + k + 1)
        K -= 1
      if K == 0:
        print(B[-1])
        f = 0
        break
    A = B

Solution (Python):
from collections import deque

def main():
    K = int(input())
    q = deque()
    for i in range(1,10,1):
        q.append(i)
    list = []
    while (len(list) <= 100002):
        v = q.popleft()
        list.append(v)
        amari = v%10
        if amari != 0 and amari != 9:
            q.append((v*10)+amari-1)
            q.append((v*10)+amari)
            q.append((v*10)+amari+1)
        elif amari == 0:
            q.append((v*10)+amari)
            q.append((v*10)+amari+1)
        else:
            q.append((v*10)+amari-1)
            q.append((v*10)+amari)

    return list[K-1]

print(main())

Solution (Python):
from collections import deque
K = int(input())
q = deque([i for i in range(1, 10)])
for _ in range(K - 1):
    
    num = q.popleft()
    for i in range(-1,2):
        if 0 <= int(str(num)[-1]) + i <= 9:
            q.append(num * 10 + int(str(num)[-1]) + i)
print(q[0])

Solution (Python):
from collections import deque
d = deque(range(1,10))
k = int(input())

for _ in range(k):
    ans = d.popleft()
    mod = ans % 10
    if mod != 0:
        d.append(ans * 10 + mod - 1)
    d.append(ans * 10 + mod)
    if mod != 9:
        d.append(ans * 10 + mod + 1)

print(ans)

Solution (Python):
def resolve():
    K = int(input())
    lunluns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    count = 9
    pointer = 0
    while K > count:
        lunnum = lunluns[pointer]
        lunlast = int(str(lunnum)[-1])
        if lunlast == 0:
            for i in [0, 1]:
                lunluns.append(int(str(lunnum)+str(lunlast+i)))
                count += 1
        elif lunlast == 9:
            for i in [-1, 0]:
                lunluns.append(int(str(lunnum)+str(lunlast+i)))
                count += 1
        else:
            for i in [-1, 0, 1]:
                lunluns.append(int(str(lunnum)+str(lunlast+i)))
                count += 1
        pointer += 1
    print(lunluns[K-1])

if '__main__' == __name__:
    resolve()

Solution (Python):
from collections import deque

k=int(input())
d=deque()
for i in range(1,10):
    d.append(i)

for i in range(1,k):
    v=d.popleft()
    s=v%10
    if s>0:
        d.append(10*v+s-1)
    d.append(10*v+s)
    if s<9:
        d.append(10*v+s+1)
    
print(d[0])

Solution (Python):
from collections import deque

def main():
  N=int(input())
  for n in range(N):
    x=ans.popleft()
    if x%10!=0:
      ans.append(10*x+(x%10)-1) 
    ans.append(10*x+(x%10)) 
    if x%10!=9:
      ans.append(10*x+(x%10)+1) 
  print(x)
  
if __name__=='__main__':
  ans=deque([1,2,3,4,5,6,7,8,9])
  main()

Solution (Python):
from collections import deque

k=int(input())

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

b=deque(a)

while b:
  v=b.popleft()
  if v%10==0:
    f=v*10+1
    if f<=3234566667:
      
      b.append(f)
      a.append(f)
    g=v*10
    if g<=3234566667:
      b.append(g)
      a.append(g)
    
  elif v%10==9:
    f=v*10+8
    g=v*10+9
    if f<=3234566667:
      
      b.append(f)
      a.append(f)
    if g<=3234566667:
      b.append(g)
      a.append(g)
    
  else:
    f=v*10+(v%10)-1
    g=v*10+(v%10)
    h=v*10+(v%10)+1
    if f<=3234566667:
      b.append(f)
      a.append(f)
    if g<=3234566667:
      b.append(g)
      a.append(g)
    if h<=3234566667:
      b.append(h)
      a.append(h)
      
a.sort()

print(a[k-1])

Solution (Python):
from collections import deque

K=int(input())
q=deque([i for i in range(1,10)])
for _ in range(K-1):
  x=deque.popleft(q)
  a=x%10
  if a!=0 and a!=9:
    deque.append(q,x*10+a-1)
    deque.append(q,x*10+a)
    deque.append(q,x*10+a+1)
  elif a==0:
    deque.append(q,x*10)
    deque.append(q,x*10+1)
  else:
    deque.append(q,x*10+8)
    deque.append(q,x*10+9)
print(deque.popleft(q))

Solution (Python):
from collections import deque

K=int(input())
if K<=9:
  print(K)
  exit()
q=deque([i for i in range(1,10)])
for _ in range(K-1):
  x=deque.popleft(q)
  a=x%10
  if a!=0 and a!=9:
    deque.append(q,x*10+a-1)
    deque.append(q,x*10+a)
    deque.append(q,x*10+a+1)
  elif a==0:
    deque.append(q,x*10)
    deque.append(q,x*10+1)
  else:
    deque.append(q,x*10+8)
    deque.append(q,x*10+9)
print(deque.popleft(q))

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

if K<=9:
  print(K)
else:
  p=1
  dp,old=[[1]*10],[0,1]
  n=9
  while K>n:
    old=dp[p-1]
    tmp=[0]*10
    for i in range(1,9):
      tmp[i]=old[i-1]+old[i]+old[i+1]
    tmp[9]=old[8]+old[9]
    tmp[0]=old[0]+old[1]
    dp.append(tmp)
    p+=1
    n+=sum(tmp[1:])

  ans=0
  n-=sum(tmp[1:])
  K-=n
  c=2
  for i in range(p-1,-1,-1):
    if c!=0:
      c-=1
    while K>dp[i][c]:
      K-=dp[i][c]
      c+=1
    ans+=c*10**i
  print(ans)

Solution (Python):
from collections import deque

K = int(input())

q = deque()
for i in range(1,10):
    q.append(i)
ans=0
cnt=0
while cnt<K:
    cnt+=1
    current = q.popleft()

    dn = [-1,0,1]
    for i in dn:
        if current%10+i<0 or current%10+i>9:
            continue
        q.append(current*10+current%10+i)
else:
    ans=current
    
print(ans)

Solution (Python):
from collections import deque

K = int(input())

q = deque()
for i in range(1,10):
    q.append(i)
ans=0
if K>=10:
    cnt = 9
    while len(q)>0:
        current = q.popleft()

        dn = [-1,0,1]
        for i in dn:
            if current%10+i<0 or current%10+i>9 or cnt>=K:
                continue
            q.append(current*10+current%10+i)
            cnt+=1
    else:
        ans=current

else:
    ans = K
    
print(ans)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    k = int(input())
    queue = list(range(1, 10))
    cnt = 0
    for v in queue:
        cnt += 1
        if k == cnt:
            print(v)
            return
        r = v % 10
        for d in range(r - 1, r + 2):
            if 0 <= d <= 9:
                queue.append(v * 10 + d)
resolve()

Solution (Python):


from collections import deque

K=int(input())
d = deque()

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

for i in range(1,K):
    s = d.popleft()
    v = s%10
    if v>0:
        d.append(10*s+v-1)
    d.append(10*s+v)
    if v<9:
        d.append(10*s+v+1)
print(d.popleft())

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

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

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

Solution (Python):
K=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
  q.put(i)
for j in range(1,K+1):
  x=q.get(j)
  if x%10!=0:
    q.put(10*x+x%10-1)
  q.put(10*x+x%10)
  if x%10!=9:
    q.put(10*x+x%10+1)
print(x)

Solution (Python):
def dfs(d:int, v:int, all:list):
    if d==11:
        return
    all.append(v)
    if list(str(v))[-1]=="0":
        dfs(d+1,10*v+int(list(str(v))[-1])+1,all)
        dfs(d+1,10*v+int(list(str(v))[-1]),all)
    elif list(str(v))[-1]=="9":
        dfs(d+1,10*v+int(list(str(v))[-1])-1,all)
        dfs(d+1,10*v+int(list(str(v))[-1]),all)
    else:
        dfs(d+1,10*v+int(list(str(v))[-1])+1,all)
        dfs(d+1,10*v+int(list(str(v))[-1]),all)
        dfs(d+1,10*v+int(list(str(v))[-1])-1,all)
k=int(input())
all=[]
for i in range(1,10):
    dfs(1,i,all)
all.sort()
print(all[k-1])

Solution (Python):
from collections import deque
k=int(input())
que=deque()
for i in range(1,10):
    que.append(i)

for i in range(k):
    x=que.popleft()
    if list(str(x))[-1]=="0":
        que.append(x*10+int(list(str(x))[-1]))
        que.append(x*10+int(list(str(x))[-1])+1)
    elif list(str(x))[-1]=="9":
        que.append(x*10+(int(list(str(x))[-1])-1))
        que.append(x*10+int(list(str(x))[-1]))
    else:
        que.append(x*10+int(list(str(x))[-1])-1)
        que.append(x*10+int(list(str(x))[-1]))
        que.append(x*10+int(list(str(x))[-1])+1)

print(x)

Solution (Python):
x=int(input())
next=[]
now=[1,2,3,4,5,6,7,8,9]

for _ in range(11):
  if x<=len(now):
    print(now[x-1])
    exit()
  else:
    x-=len(now)
    next=now
    now=[]
    for i in next:
      i=str(i)
      if i[-1]=='0':
        j=i+'0'
        k=i+'1'
        now+=[j]
        now+=[k]
      elif i[-1]=='9':
        j=i+'8'
        k=i+'9'
        now+=[j]
        now+=[k]
      else:
        j=i+str(int(i[-1])-1)
        k=i+str(int(i[-1]))
        l=i+str(int(i[-1])+1)
        now+=[j]
        now+=[k]
        now+=[l]

Solution (Python):
from queue import deque

k=int(input())
que=deque()
for i in range(1,10):
  que.append(i)
for i in range(k):
  now=que.popleft()
  too=now%10

  if too!=0:
    que.append(now*10+too-1)

  que.append(now*10+too)

  if too!=9:
    que.append(now*10+too+1)

print(now)

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

for i in range(k):
  now=que.pop(0)
  too=now%10

  if too!=0:
    que.append(now*10+too-1)

  que.append(now*10+too)

  if too!=9:
    que.append(now*10+too+1)

print(now)

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

def make_lunlun(lunlun_lst):
    ret_lunlun = []
    for num in lunlun_lst:
        num_str = str(num)
        if num_str[-1] != "0":
            num_tmp = num_str + str(int(num_str[-1]) - 1)
            ret_lunlun.append(int(num_tmp))
        if num_str[-1] != "9":
            num_tmp = num_str + str(int(num_str[-1]) + 1)
            ret_lunlun.append(int(num_tmp))
        num_tmp = num_str + num_str[-1]
        ret_lunlun.append(int(num_tmp))
    return ret_lunlun

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

while 1:
    if len(lunlun_lst) < k:
        k -= len(lunlun_lst)
        lunlun_lst = make_lunlun(lunlun_lst)
    else:
        lunlun_lst.sort()
        print(lunlun_lst[k - 1])
        break

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
K = I()
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
queue = deque(A)
cnt = 0
while cnt != (K - 1):
    x = queue.popleft()
    mod = x % 10
    if mod != 0:
        queue.append(10 * x + mod - 1)
    queue.append(10 * x + mod)
    if mod != 9:
        queue.append(10 * x + mod + 1)
    cnt += 1
print(queue.popleft())

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


K = I()

B = []


lun = {(0, 1): 1, (1, 1): 1, (2, 1): 1, (3, 1): 1, (4, 1): 1, (5, 1): 1, (6, 1): 1, (7, 1): 1, (8, 1): 1, (9, 1): 1}
for j in range(2, 11):
    for i in range(10):
        if i == 0:
            lun[(i, j)] = lun[(i, j - 1)] + lun[(i + 1, j - 1)]
        elif i == 9 :
            lun[(i, j)] = lun[(i - 1, j - 1)] + lun[(i, j - 1)]
        else:
            lun[(i, j)] = lun[(i - 1, j - 1)] + lun[(i, j - 1)] + lun[(i + 1, j - 1)]

cnt = 0
for j in range(1, 10):
    for i in range(1, 10):
        cnt += lun[(i, j)]
    B.append(cnt)

b = bisect.bisect_right(B, K)

ans = []
if b == 0:
    print(K)
    exit()
if K == B[b - 1]:
    print(pow(10, b) - 1)
    exit()
else:
    K -= B[b - 1]
    i = 1
    while K > 0:
        K -= lun[(i, b + 1)]
        i += 1
    if K == 0:
        for j in range(b + 1):
            c = i - 1 + j
            if c <= 9:
                ans.append(c)
            else:
                ans.append(9)
    else:
        K += lun[(i - 1, b + 1)]
        ans.append(i - 1)
        for l in range(b):
            if ans[-1] == 0:
                k = 0
            else:
                k = ans[-1] - 1
            while K > 0:
                K -= lun[(k, b - l)]
                k += 1
            if K == 0:
                for j in range(b - l):
                    c = k - 1 + j
                    if c <= 9:
                        ans.append(c)
                    else:
                        ans.append(9)
                break
            else:
                K += lun[(k - 1, b - l)]
                ans.append(k - 1)
print(''.join(map(str, ans)))

Solution (Python):
from collections import deque

k=int(input())

lunlun=deque(i for i in range(1,10))
for _ in range(k-1):
  p=lunlun.popleft()
  if p%10!=0:
    lunlun.append(10*p+p%10-1)
  lunlun.append(10*p+p%10)
  if p%10!=9:
    lunlun.append(10*p+p%10+1)
print(lunlun.popleft())

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

l = [str(i) for i in range(1,10)]
que = deque(l)


while len(l) < k:
    seq = que.popleft()

    a = int(seq[-1])
    if a != 0:
        aa = seq + str(a-1)
        que.append(aa)
        l.append(aa)
    aa = seq + str(a)
    que.append(aa)
    l.append(aa)
    if a != 9:
        aa = seq + str(a+1)
        que.append(aa)
        l.append(aa)

print(l[k-1])

Solution (Python):
k=int(input())
L=[]
def f(d,now,L):
  L.append(now)
  
  if d==10:
    return
  
  for j in range(-1,2):
    v=now%10+j
    if 0<=v<=9:
      f(d+1,now*10+v,L)

for l in range(1,10):
  f(1,l,L)
L.sort()
print(L[k-1])

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    K=ii()
    L=list(range(10))

    if K <= 9:
        print(K)
        exit()
    
    
    head_i = 1
    while len(L) < K+10:
        assert head_i < len(L)
        head = L[head_i]
        head_tail = head % 10
        for x in [head_tail-1,head_tail,head_tail+1]:
            if x < 0 or x >= 10: continue
            
            
            
            L.append(head * 10 + x)
        
        head_i += 1

    
    print(L[K])

    


if __name__ == "__main__":
    main()

Solution (Python):

import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()

    que = cl.deque(list(range(1, 10)))

    while N > 1:
        target = que.popleft()
        if target % 10 != 0:
            que.append(target*10 + (target % 10) - 1)

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

        if target % 10 != 9:
            que.append(target*10 + (target % 10) + 1)
        N -= 1

    ans = que.popleft()

    print(ans)


main()

Solution (Python):
from collections import deque

N = int(input())

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

for _ in range(N-1):
  i = q.popleft()
  if i % 10 == 0:
    q.append(i*10)
    q.append(i*10+1)
  elif i % 10 == 9:
    q.append(i*10+8)
    q.append(i*10+9)
  else:
    q.append(i*10+i%10-1)
    q.append(i*10+i%10)
    q.append(i*10+i%10+1)
    
print(q[0])

Solution (Python):
a=[str(i) for i in range(1,10)]
i=0
while len(a)<100000:
    if a[i][-1]!="0":
        a.append(a[i]+str(int(a[i][-1])-1))
    a.append(a[i]+str(int(a[i][-1])))
    if a[i][-1]!="9":
        a.append(a[i]+str(int(a[i][-1])+1))
    i+=1

k=int(input())
print(a[k-1])

Solution (Python):
from collections import deque
k=int(input())
ans=deque([1,2,3,4,5,6,7,8,9])

for i in range(k):
    p=ans.popleft()
    if i==k-1:
        print(p)
    q=p%10
    if q==0:
        ans.append(10*p+0)
        ans.append(10*p+1)
    elif q==9:
        ans.append(10*p+8)
        ans.append(10*p+9)
    else:
        ans.append(10*p+q-1)
        ans.append(10*p+q)
        ans.append(10*p+q+1)

Solution (Python):
from collections import deque

K = int(input())

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

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

print(x)

Solution (Python):
import itertools

K = int(input())

dp = [[0,1,1,1,1,1,1,1,1,1]]
lunlun_cnt = [9]

i = 1

while True:
    dp.append([0]*10)
    lunlun_cnt_tmp = 0

    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][j] + dp[i-1][j+1]
        elif j == 9:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]
        lunlun_cnt_tmp += dp[i][j]
    
    i += 1

    if lunlun_cnt[-1] + lunlun_cnt_tmp >= K:
        break
    else:
        lunlun_cnt.append(lunlun_cnt[-1] + lunlun_cnt_tmp)

if K <= 9:
    pos = K
    digit = 0
else:
    pos = K - lunlun_cnt[-1]
    digit = len(lunlun_cnt)

cnt = 0
flag = False

keta = [-1,0,1]

for i in range(9):
    for keta_shift in itertools.product(keta, repeat=digit):
        flag2 = False
        r = i+1
        for j in range(digit):
            r += keta_shift[j]
            if r < 0 or r > 9:
                flag2 = True
                break
        
        if flag2:
            continue

        cnt += 1
        if cnt == pos:
            flag = True
            break
    if flag:
        break

res = [i+1]
for i in range(digit):
    res.append(res[-1] + keta_shift[i])

print(''.join(list(map(str,res))))

Solution (Python):
from collections import deque

K = int(input())
q = deque([])
if K < 10:
    print(K)
    exit()
for i in range(1, 10):
    q.append(i)
counter = 9
while counter < K:
    tmp = q.popleft()
    f = tmp%10
    tmp = tmp * 10
    if f == 0:
        q.append(tmp)
        q.append(tmp+1)
        counter += 2
    elif f == 9:
        q.append(tmp+f-1)
        q.append(tmp+f)
        counter += 2
    else:
        q.append(tmp+f-1)
        q.append(tmp+f)
        q.append(tmp+f+1)
        counter += 3
for i in range(K, counter):
    q.pop()
print(q.pop())

Solution (Python):




















from collections import deque

a = deque(range(1, 10))
for _ in range(int(input())):
    i = a.popleft()
    m = i % 10
    i = 10 * i + m
    if m > 0:
        a.append(i - 1)
    a.append(i)
    if m < 9:
        a.append(i + 1)
print(i // 10)

Solution (Python):

from heapq import *

a = [*range(1, 10)]
heapify(a)
i = 0
k = int(input())
c = 0
while True:
    t = str(heappop(a))
    i += 1
    if i == k:
        break
    if t[-1] != "0":
        heappush(a, int(t + str(int(t[-1]) - 1)))
    heappush(a, int(t + t[-1]))
    if t[-1] != "9":
        heappush(a, int(t + str(int(t[-1]) + 1)))
print(t)

Solution (Python):

from heapq import *

a = [*range(1, 10)]
heapify(a)
i = 0
k = int(input())
c = 0
while True:
    t = str(heappop(a))
    i += 1
    if i == k:
        break
    if t[-1] != "0":
        heappush(a, int(t + str(int(t[-1]) - 1)))
    heappush(a, int(t + t[-1]))
    if t[-1] != "9":
        heappush(a, int(t + str(int(t[-1]) + 1)))
print(t)

Solution (Python):
from collections import*
a=deque([1,2,3,4,5,6,7,8,9])
k=int(input())
for _ in range(k):
  i=a.popleft()
  if i%10>0:a.append(10*i+i%10-1)
  a.append(10*i+i%10)
  if i%10<9:a.append(10*i+i%10+1)
print(i)

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

from collections import deque
d = deque()
for i in range(1,10):
  d.append(str(i))

for _ in range(K):
  a = d.popleft()
  
  if a[-1] != '0':
    d.append(a+str(int(a[-1])-1))
  d.append(a+a[-1])
  if a[-1] != '9':
    d.append(a+str(int(a[-1])+1))

ans = a
print(ans)

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

total_ls = []
def dfs(A):
    if int(A) > 3234566667:
        return
    global total_ls
    total_ls.append(int(A))
    last = int(A[-1])
    if last == 0:
        nex = [1,0]
    elif last == 9:
        nex = [8,9]
    else:
        nex = [last-1,last,last+1]
    for n in nex:
        A += str(n)
        dfs(A)
        A = A[:-1]

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

Solution (Python):
from collections import deque
K = int(input())
count = 0
todo = deque(range(1, 10))
while todo:
    x = todo.popleft()
    count += 1
    if count == K:
        print(x)
        break
    i = x % 10
    if 0 < i:
        todo.append(x * 10 + i - 1)
    todo.append(x * 10 + i)
    if i < 9:
        todo.append(x * 10 + i + 1)

Solution (Python):
N = int(input()) + 1
Ans = []
def dfs(depth, p):
    if depth==0:
        Ans.append(p)
        if len(Ans) == N:
            print(p)
            exit()
        return
    if p!=0:
        for digit in range(max(0, p%10-1), min(10, p%10+2)):
            dfs(depth-1, p*10+digit)
    else:
        for digit in range(10):
            dfs(depth-1, p*10+digit)
dfs(10, 0)

Solution (Python):
X = []
def dfs(k, L):
    global cnt
    if k:
        X.append(int("".join(map(str, L))))
    if k == K:
        return
    if k == 0:
        for i in range(1, 10):
            dfs(k + 1, L + [i])
    else:
        l = L[-1]
        for i in range(max(l-1, 0), min(l+2, 10)):
            dfs(k + 1, L + [i])

K = 10
dfs(0, [])
print(sorted(X)[int(input()) - 1])

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

    K = int(input())
    q = deque()
    for i in range(1, 10):
        q.append(i)
    for i in range(K - 1):
        s = q.popleft()
        for j in range(-1, 2):
            add = (s % 10) + j
            if add >= 0 and add <= 9:
                q.append(s * 10 + add)
    print(q.popleft())


main()

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

    K = int(input())
    q = deque()
    for i in range(1, 10):
        q.append(i)
    for i in range(K - 1):
        s = q.popleft()
        for j in range(-1, 2):
            add = (s % 10) + j
            if add >= 0 and add <= 9:
                q.append(s * 10 + add)
    print(q[0])


main()

Solution (Python):

def main():
    def rec(d: int, val: int, all: list):
        all.append(val)
        if d == 10:
            return
        for j in range(-1, 2):
            add = (val % 10) + j
            if add >= 0 and add <= 9:
                rec(d + 1, val * 10 + add, all)
    
    K = int(input())

    all = []
    for v in range(1, 10):
        rec(1, v, all)
    print(sorted(all)[K - 1])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

k = int(input())
q = deque(list(range(1,10)))

for i in range(k):
    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(x)