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()
for i in range(1, 10):
    Q.append(i)

while K > 0:
    q = Q.popleft()
    a = q % 10
    if a == 0:
        Q.append(q * 10)
        Q.append(q * 10 + 1)
    elif a == 9:
        Q.append(q * 10 + 8)
        Q.append(q * 10 + 9)
    else:
        Q.append(q * 10 + a - 1)
        Q.append(q * 10 + a)
        Q.append(q * 10 + a + 1)
    K -= 1

print(q)

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

runn=['0','1','2','3','4','5','6','7','8','9']
List=['1','2','3','4','5','6','7','8','9']
while True:
    if len(runn)-1>K:
        print(int(runn[K]))
        break
    else:
        list1=[]
        for i in range(len(List)):
            
            if List[i][-1]=='0':
                list1.append(List[i]+'0')
                list1.append(List[i]+'1')
            
            for u in range(1,9):
                if List[i][-1]=='{}'.format(u):
                    list1.append(List[i]+'{}'.format(u-1))
                    list1.append(List[i]+'{}'.format(u))
                    list1.append(List[i]+'{}'.format(u+1))
            if List[i][-1]=='9':
                list1.append(List[i]+'8')
                list1.append(List[i]+'9')
           
        List=list1
        runn=runn+list1

Solution (Python):
from functools import reduce

from itertools import product
k = int(input())
if k < 10:
    print(k)
else:
    i = 1
    sigma = 9
    while sigma < k:
        L = product([-1, 0, 1], repeat=i)
        

        def f(n, v):
            returnlist = []
            for j in range(len(v)+1):
                if j == 0:
                    returnlist.append(n)
                else:
                    x = returnlist[-1]
                    returnlist.append(x + v[j-1])
            return returnlist
        biglist = []
        for v in L:
            for kk in range(1, 10):
                biglist.append(f(kk, v))
        
        numbers = []
        for lists in biglist:
            if not (- 1 in set(lists) or 10 in set(lists)):
                x = [(10 ** (i - j)) * lists[j] for j in range(i+1)]
                y = reduce(lambda x, y: x + y, x)
                numbers.append(y)
        numbers.sort()
        if sigma + len(numbers) >= k:
            print(numbers[k - sigma - 1])
            sigma += len(numbers)
        else:
            sigma += len(numbers)
            i += 1

Solution (Python):
from collections import deque

k=int(input())


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

i=0
ans=0
while i < k:
    ans=q.popleft()
    if ans%10 != 0:
        q.append(10*ans+ans%10-1)
    q.append(10*ans+ans%10)
    if ans%10 != 9:
        q.append(10*ans+ans%10+1)
    i+=1
print(ans)

Solution (Python):
import queue

q = queue.Queue()
K = int(input())

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

ans = 0
for i in range(K):
    ans = q.get()
    if ans % 10 != 0:
        q.put(ans * 10 + (ans % 10) - 1)

    q.put(ans * 10 + (ans % 10))

    if ans % 10 != 9:
        q.put(ans * 10 + (ans % 10) + 1)


print(ans)

Solution (Python):
import collections
k = int(input())
count = 0
queue = collections.deque(['1','2','3','4','5','6','7','8','9'])
if k <= 12:
    print(k)
else:
    for i in range(k):
        t = queue.popleft()
        s = int(t[-1])
        if(s == 0):
            queue.extend([t + str(s),t + str(s + 1)])
            count+=1
        elif(s == 9):
            queue.extend([t + str(s-1),t + str(s)])
        else:
            queue.extend([t + str(s-1),t + str(s),t + str(s+1)])
            count += 1
    print(int(t))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

k = int(readline())
q = deque(list(map(str, list(range(1, 10)))))
for i in range(k - 1):
    x = q.popleft()
    y = int(x[-1])
    if y != 0:
        q.append(x + str(y - 1))
    q.append(x + x[-1])
    if y != 9:
        q.append(x + str(y + 1))
print(q[0])

Solution (Python):
from collections import deque

k = int(input())

d = deque()
for i in range(1,10):
  d.append(i)
for j in range(k):
  a = d.popleft()
  b = a%10
  if b != 0:
    d.append(10*a+b-1)
  d.append(10*a+b)
  if b != 9:
    d.append(10*a+b+1)
print(a)

Solution (Python):





def rec(d: int, val: int, all):
    all.append(val)

    if d == 10:
        return

    for i in range(-1, 2):
        add = (val % 10) + i
        if add >= 0 and add <= 9:
            rec(d+1, val*10+add, all)


def main():
    K = int(input())
    all = []
    for v in range(1, 10):
        rec(1, v, all)
    all.sort()
    print(all[K-1])


if __name__ == "__main__":
    main()

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

from collections import deque

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

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

print(x)

Solution (Python):
from collections import defaultdict, deque

k = int(input())
l = ["1", "2", "3", "4", "5", "6", "7",  "8", "9"]
m =  ["1", "2", "3", "4", "5", "6", "7",  "8", "9"]
queue = deque(["1", "2", "3", "4", "5", "6", "7",  "8", "9"])
while len(l)<k+1:
    i = queue.popleft()
    if i[-1] == "0":
        l.append(i+"0")
        l.append(i+"1")
        queue.append(i+"0")
        queue.append(i+"1")
    
    elif i[-1] == "9":
        l.append(i+"8")
        l.append(i+"9")
        queue.append(i+"8")
        queue.append(i+"9")
    else:
        l.append(i+str(int(i[-1])-1))
        l.append(i+str(int(i[-1])))
        l.append(i+str(int(i[-1])+1))
        queue.append(i+str(int(i[-1])-1))
        queue.append(i+str(int(i[-1])))
        queue.append(i+str(int(i[-1])+1))

print(l[k-1])

Solution (Python):
from queue import Queue

K = int(input())

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

for k in range(K-1):
    x = q.get()
    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(q.get())

Solution (Python):
from sys import stdin,stdout
from queue import Queue

def solve(K):
    if K < 10: return K
    q = Queue()
    cnt = 0
    for i in range(1,10):
        q.put(i)

    while not q.empty():
        u = q.get()
        cnt += 1
        if cnt == K: return u

        r = u % 10
        if r != 0:
            q.put(10*u + r - 1)

        q.put(10*u + r)
        if r < 9:
            q.put(10*u + r +1)





K = int(stdin.readline())

stdout.write(str(solve(K)))

Solution (Python):
import queue 
q=queue.Queue() 
n=int(input()) 
q.put(1)
q.put(2)
q.put(3)
q.put(4)
q.put(5)
q.put(6)
q.put(7)
q.put(8)
q.put(9) 
j=1 
while j<n:
    x=q.get() 
    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 )
    j+=1 
print(q.get())

Solution (Python):
from collections import deque

K = int(input())
q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9,])

cnt = 0
while cnt < K-1:
    n = q.popleft()
    d = int(str(n)[-1])
    cnt += 1
    for i in [d-1, d, d+1]:
        if(i < 0 or 10 <= i):
            continue
        q.append(10*n+i)
print(q.popleft())

Solution (Python):
if __name__ == '__main__':
    n, = map(int, input().split())
    
    q = list(range(1, 10))
    count = 0
    while True:
      a = q.pop(0)
      count += 1
      if count == n:
        print(a)
        break
      end = a % 10
      end_1 = end - 1
      end_2 = end + 1
      if end_1 >= 0:
        q.append(10*a + end_1)
      q.append(10*a + end)
      if end_2 <= 9:
        q.append(10*a + end_2)

Solution (Python):

import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

K = ir()
que = deque(range(1, 10))
count = 0
while count < K-1:
    count += 1
    x = que.popleft()
    remain = x % 10
    if remain > 0:
        que.append(10*x + remain - 1)
    que.append(10*x + remain)
    if remain < 9:
        que.append((10*x + remain + 1))

answer = que.popleft()
print(answer)

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

K = ir()
num = -1

def dfs(A, i, bl):
    global num
    if i == 11:
        num += 1
        if num == K:
            ans = ''.join(map(str, A))
            ans = int(ans)
            print(ans)
            exit()
        return
    last = A[-1]
    if bl:
        dfs([0], i+1, True)
        for j in range(1, 10):
            dfs([j], i+1, False)
    else:
        if last > 0:
            dfs(A+[last-1], i+1, False)
        dfs(A+[last], i+1, False)
        if last < 9:
            dfs(A+[last+1], i+1, False)

dfs([0], 0, True)

Solution (Python):

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def myappend(n):
    sn = str(n)
    nlast = n%10
    if nlast == 0:
        d.append(10*n + nlast)
        d.append(10*n + nlast + 1)
    elif nlast == 9:
        d.append(10*n + nlast - 1)
        d.append(10*n + nlast)
    else:
        d.append(10*n + nlast - 1)
        d.append(10*n + nlast)
        d.append(10*n + nlast + 1)

cnt = 0
while d:
    val = d.popleft()
    cnt += 1
    if cnt == K:
        print(val)
        exit()
    myappend(val)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque 
def main():
    K = int(readline())
    dq = deque() 
    cnd = []
    for i in range(1, 10):
        dq.append(i)
        cnd.append(i)
    
    while len(dq)>0:
        v = dq.popleft()
        r = v%10 
        if r == 0:
            nx = v*10
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+1
            dq.append(nx)
            cnd.append(nx)
        elif r == 9:
            nx = v*10+8
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+9
            dq.append(nx)
            cnd.append(nx)
        else:
            nx = v*10+(r-1)
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+r
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+(r+1)
            dq.append(nx)
            cnd.append(nx)
        if len(cnd) > K: 
            break
    print(cnd[K-1])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque 
def main():
    K = int(readline())
    dq = deque() 
    cnd = []
    for i in range(1, 10):
        dq.append(i)
        cnd.append(i)
    
    while len(dq)>0:
        v = dq.popleft()
        r = v%10 
        if r == 0:
            nx = v*10
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+1
            dq.append(nx)
            cnd.append(nx)
        elif r == 9:
            nx = v*10+8
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+9
            dq.append(nx)
            cnd.append(nx)
        else:
            nx = v*10+(r-1)
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+r
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+(r+1)
            dq.append(nx)
            cnd.append(nx)
        if len(cnd) > K: 
            break
    print(cnd[K-1])
if __name__ == '__main__':
    main()

Solution (Python):
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)
        z = int(x[-1])
        ans[-1].append(x + str(z))
        if z <= 8:
            ans[-1].append(x + str(z + 1))
        if z >= 1:
            ans[-1].append(x + str(z - 1))
    d += len(ans[-1])
ans[-1].sort()
print(ans[-1][k - d - 1])

Solution (Python):
import math
K = int(input().split()[0])

s = [[0 for _ in range(10)] for _ in range(20)]

for i in range(10):
    s[0][i] = 1

for n in range(1,20):
    for i in range(10):
        if i == 0:
            s[n][i] = s[n-1][i]+s[n-1][i+1]
        elif i == 9:
            s[n][i] = s[n-1][i-1]+s[n-1][i]
        else:
            s[n][i] = s[n-1][i-1]+s[n-1][i]+s[n-1][i+1]

i = -1
Sm = 0
SmOld = 0
while True:
    i += 1
    Sm += sum(s[i][1:])
    if Sm > K:
        Sm = SmOld
        break
    SmOld = Sm

k = 10**i
while True:
    a = list(map(int,str(k)))
    flag = True
    for h in range(i,0,-1):
        if abs(a[h-1]-a[h]) < 2:
            continue
        else:
            flag = False
            k = k-k%(10**(i-h))+10**(i-h)
            break
    if not flag:
        continue
    Sm += 1
    if Sm == K:
        print(k)
        break
    k += 1

Solution (Python):
from collections import deque


k = int(input())
if k<=9:
    print(k)
    exit()

run = deque([int(i) for i in range(1,10)])
rli = [int(i) for i in range(1,10)]
i=0
while len(rli)<=k:
    
    p = run.popleft()
    j=p%10
    if p%10 == 9:
        for h in range(-1,1):
            n = p*10+j+h
            rli.append(n)
            run.append(n)
    elif p%10 == 0:
        for h in range(0,2):
            n = p*10+j+h
            rli.append(n)
            run.append(n)
    else:
        
        for h in range(-1,2):
            n = p*10+j+h
            rli.append(n)
            run.append(n)
    
print(rli[k-1])

Solution (Python):
import heapq

k = int(input())

num_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
mae = 0

if k <= 9:
    print(k)
else:
    k -= 9
    q = []
    heapq.heapify(q)
    for i in range(1, 10):
        heapq.heappush(q, i)
    temp = 0
    while temp < 9:
        temp += 1
        num = heapq.heappop(q)
        if temp == 9:
            heapq.heappush(q, num*10 + num_list[(num%10)-1])
            heapq.heappush(q, num*10 + num_list[(num%10)])
        else:
            heapq.heappush(q, num*10 + num_list[(num%10)-1])
            heapq.heappush(q, num*10 + num_list[(num%10)])
            heapq.heappush(q, num*10 + num_list[(num%10)+1])
    while k > 0:
        k -= 1
        num = heapq.heappop(q)
        if num == mae:
            k += 1
            continue
        elif num%10 == 0:
            heapq.heappush(q, num*10 + num_list[(num%10)])
            heapq.heappush(q, num*10 + num_list[(num%10)+1])
        elif num%10 == 9:
            heapq.heappush(q, num*10 + num_list[(num%10)-1])
            heapq.heappush(q, num*10 + num_list[(num%10)])
        else:
            heapq.heappush(q, num*10 + num_list[(num%10)-1])
            heapq.heappush(q, num*10 + num_list[(num%10)])
            heapq.heappush(q, num*10 + num_list[(num%10)+1])
        mae = num
    print(num)

Solution (Python):
from collections import deque
K = int(input())
que = deque()
que.extend([i for i in range(1,10)])

for k in range(K-1):
    out = que.popleft()
    div = out%10
    if div==0:
        que.extend([out*10,out*10+1])
    elif out%10==9:
        que.extend([out*10+8,out*10+9])
    else:
        que.extend([out*10-1+div,out*10+div,out*10+1+div])
print(que.popleft())

Solution (Python):
from collections import deque
num=deque([1,2,3,4,5,6,7,8,9])
cnt=0
K=int(input())
while(True):
    a=num.popleft()
    cnt+=1
    if cnt==K:
        print(a)
        exit()
    if a%10==0:
        a1=a*10
        a2=a1+1
        num.append(a1)
        num.append(a2)
    elif a%10==9:
        a1=a*10+(a%10)-1
        a2=a*10+(a%10)
        num.append(a1)
        num.append(a2)
    else:
        a1 = a * 10 + (a % 10) - 1
        a2 = a * 10 + (a % 10)
        a3 = a * 10 + (a % 10) + 1
        num.append(a1)
        num.append(a2)
        num.append(a3)

Solution (Python):
from collections import deque


k = int(input())
queue = deque([i for i in range(1, 10)])

ans = 1
for _ in range(k):
    ans = queue.popleft()
    right_digit = ans % 10
    if right_digit == 0:
        queue.append(ans * 10 + right_digit)
        queue.append(ans * 10 + right_digit + 1)
    elif right_digit == 9:
        queue.append(ans * 10 + right_digit - 1)
        queue.append(ans * 10 + right_digit)
    else:
        queue.append(ans * 10 + right_digit - 1)
        queue.append(ans * 10 + right_digit)
        queue.append(ans * 10 + right_digit + 1)
print(ans)

Solution (Python):
from queue import Queue

k = int(input())

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

for _ in range(k):
    x = q.get()
    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):
import sys
sys.setrecursionlimit(1000000)
k = int(input())
lun = []

def dfs(a, last):
    if len(a) > 0:
        lun.append(int(a))
    if len(a) > 11:
        return
    if len(a) == 0:
        for i in range(1, 10):
            a += str(i)
            dfs(a, i)
            a = a[:-1]
    else:
        if last == 0:
            candidates = [last, last + 1]
        elif last == 9:
            candidates = [last - 1, last]
        else:
            candidates = [last - 1, last, last + 1]
        for j in candidates:
            a += str(j)
            dfs(a, j)
            a = a[:-1]

dfs('', 0)
lun.sort()
print(lun[k - 1])

Solution (Python):
from collections import deque

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

cnt = 0
while cnt < K-1:
    n = q.popleft()
    d = int(str(n)[-1])
    cnt += 1
    for i in [d-1, d, d+1]:
        if i < 0 or 10 <= i:
            continue
        q.append(10*n+i)
print(q.popleft())

Solution (Python):
def f(k):
    if 1 <= k <= 9:
        print(k)
    else:
        nxt = [[0,1], [0,1,2], [1,2,3], [2,3,4], [3,4,5], [4,5,6], [5,6,7], [6,7,8], [7,8,9], [8,9]]
        cum_npi = [0, 9, 35, 110, 327, 956, 2782, 8089, 23527, 68468, 199368]
        for length, begin in enumerate(cum_npi):
            if k < begin:
                found = cum_npi[length - 1]
                break
        begin = 10 ** (length - 1)
        
        k -= found
        x = [[]] * (length + 1)
        x[1] = list(range(1, 10))
        

        terminate = False
        i = 1
        while True:
            
            if len(x[i]): 
                digit = x[i][0]
                if i < length: 
                    i += 1
                    x[i] = nxt[digit].copy()
                    
                    
                    if i == length: 
                        while len(x[i]): 
                            k -= 1
                            
                            if k == 0:
                                x.pop(0)
                                
                                ans = "".join([str(j.pop(0)) for j in x])
                                print(ans)
                                terminate = True
                                break
                            else:
                                x[i].pop(0)
                            
                        else:
                            
                            while len(x[i]) == 0:
                                i -= 1
                                x[i].pop(0)
                        if terminate:
                            break

f(int(input()))

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

L = [str(i) for i in range(1, 10)]
a = [str(i) for i in range(1, 10)]
for i in range(10):
    new_l = []
    for l in L:
        if l[-1] == '0':
            new_l.append(l + l[-1])
            new_l.append(l + str(int(l[-1]) + 1))
        elif l[-1] == '9':
            new_l.append(l + l[-1])
            new_l.append(l + str(int(l[-1]) - 1))
        else:
            new_l.append(l + l[-1])
            new_l.append(l + str(int(l[-1]) + 1))
            new_l.append(l + str(int(l[-1]) - 1))
    a.extend(new_l)
    L = copy.deepcopy(new_l)

a_int = [int(x) for x in a]
a_int.sort()
print(a_int[K-1])

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

que=deque([1,2,3,4,5,6,7,8,9])
for _ in range(k):
    x=que.popleft()
    if x%10!=0:
        que.append(x*10+x%10-1)
    que.append(x*10+x%10)
    if x%10!=9:
        que.append(x*10+x%10+1)
print(x)

Solution (Python):
K=int(input())
ANS=[i for i in range(1,10)]
i=0
while len(ANS)<=10**5:
  last=str(ANS[i])[-1]
  if last=="0":
    ANS+=[ANS[i]*10,ANS[i]*10+1]
  elif last=="9":
    ANS+=[ANS[i]*10+8,ANS[i]*10+9]
  else:
    ANS+=[ANS[i]*10+int(last)-1,ANS[i]*10+int(last),ANS[i]*10+int(last)+1]
  i+=1  
ans=ANS[K-1]
print(ans)

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


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

print(x)

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

q=deque([1,2,3,4,5,6,7,8,9])
for i in range(k):
  x=q.popleft()
  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) 
print(x)

Solution (Python):
from collections import deque

k = int(input())
limit = 10

start = [i for i in range(1, 10)]
ans = []
q=deque(start)
while q:
	num=q.popleft()
	if len(str(num))>11:
		continue
	ans.append(num)
	last=str(num)[-1]
	if last == "0":
		add = ['0', '1']
	elif last == '9':
		add = ['8',"9"] 
	else:
		add = [str(int(last) - 1), str(int(last)), str(int(last) + 1)]
	for i in add:
		q.append(int(str(num)+i))

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

Solution (Python):
from collections import deque

k = int(input())
limit = 10

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

while q:
    cur = q.popleft()
    if len(str(cur)) > 11:
        continue
    ans.append(cur)
    r = str(cur)[-1]
    if r == '0':
        add = ['0', '1']
    elif r == '9':
        add = ['8', '9']
    else:
        add = [str(int(r) - 1), str(int(r)), str(int(r) + 1)]

    for i in add:
        q.append(int(str(cur) + i))

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

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

print(x)

Solution (Python):
from collections import deque

k = int(input())
limit = 10

start = [i for i in range(1, 10)]
ans = []
def DFS(num):
	if len(str(num))>11:
		return 1
	ans.append(num)
	last=str(num)[-1]
	if last == "0":
		add = ['0', '1']
	elif last == '9':
		add = ['8',"9"] 
	else:
		add = [str(int(last) - 1), str(int(last)), str(int(last) + 1)]
	for i in add:
		DFS(int(str(num)+i))

for j in start:
	DFS(j)

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

Solution (Python):
K = int(input())
L = [list(range(1, 10))]
A = list(range(1, 10))
for _ in range(9):
    M = []
    for m in L[-1]:
        m = str(m)
        i = int(m[-1])
        cand = []
        if i == 0:
            cand = ['0', '1']
        elif i == 9:
            cand = ['8', '9']
        else:
            cand = [str(i - 1), str(i), str(i + 1)]
        for c in cand:
            M += [int(m + c)]
    L += [M]
    A += M
print(A[K - 1])

Solution (Python):
K=int(input())
nums=[i for i in range(1,10)]
for i in range(K):
    a=nums.pop(0)
    if a%10!=0:
        nums.append(a*10 + a%10 - 1)
    
    nums.append(a*10 + a%10)
    
    if a%10!=9:
        nums.append(a*10 + a%10 + 1)

print(a)

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

        record = []

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

        for v in range(1,10):
                rec(1, v, record)

        record.sort()

        print("{}".format(record[K-1]))



if __name__=="__main__":
        main3()

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

from collections import deque

cnt=1
q=deque([1,2,3,4,5,6,7,8,9])
while cnt<k:
    tmp=q.popleft()
    if tmp%10!=0:
        q.append(tmp*10+tmp%10-1)
    q.append(tmp*10+tmp%10)
    if tmp%10!=9:
        q.append(tmp*10+tmp%10+1)
    cnt+=1

print(q.popleft())

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

que = collections.deque()
for i in range(1, 10, 1):
    que.append(i)
cnt = 0
for i in range(K):
    x = que.popleft()
    cnt += 1
    if cnt == K:
        print(x)
        exit()
    if x%10 == 0:
        que.append(10*x+0)
        que.append(10*x+1)
    elif x%10 == 9:
        que.append(10*x+8)
        que.append(10*x+9)
    else:
        que.append(10*x+(x%10)-1)
        que.append(10*x+(x%10)+0)
        que.append(10*x+(x%10)+1)

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

lunlun_number_list = []

def dfs(N):
    lunlun_number_list.append(N)
    if len(str(N)) > 10:
        return
    now_int = int(str(N)[-1])
    if now_int == 0:
        for i in range(2):
            dfs(N*10 + i)
    elif now_int == 9:
        for i in range(8, 10, 1):
            dfs(N*10 + i)
    else:
        for i in range(now_int-1, now_int+2, 1):
            dfs(N*10 + i)

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

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

Solution (Python):
k = int(input())
l = 10
A = [str(i+1) for i in range(9)]
B= ["0"]+A
ans = []

def dfs(num):
    if len(num)>=l:
        ans.append(int(num))
    else:
        ans.append(int(num))
        for i in B:
            if abs(int(num[-1])-int(i))<2:
                dfs(num+i)
if k<=9:
    print(k)
else:
    for i in A:
        dfs(i)
    ans = sorted(ans)
    print(ans[k-1])

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

def dfs(base, n):
    global K, cnt, ans, flag
    if flag:
        return
    if n == 0:
        cnt += 1
        if cnt == K:
            ans = int(base)
            flag = True
            return
    else:
        last = int(base[-1])
        for l in range(max(0, last-1), min(10, last+2)):
            nextbase = base + str(l)
            dfs(nextbase, n-1)


def main():
    global K, ans, cnt, flag
    K = int(input())
    if K < 10:
        print(K)
        return
    leftK = int(str(K)[0])
    cnt = 9; ans = 0
    flag = False
    for keta in range(1, 10):
        for i in range(1, 10):
            dfs(str(i), keta)
    print(ans)

if __name__ == "__main__":
    main()

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

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

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

nums = [i for i in range(1,10)]
for i in range(k):
  a = nums.pop(0)
  
  if a%10 != 0:
    nums.append(a*10 + a%10 - 1)
    
  nums.append(a*10 + a%10)
  
  if a%10 != 9:
    nums.append(a*10 + a%10 + 1)
print(a)

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

k = int(input())
l = 10
A = [str(i+1) for i in range(9)]
B = ["0"] + A
ans = []


def dfs(num,l):
    if len(num) >= l:
        ans.append(int(num))
    else:
        ans.append(int(num))
        for i in B:
            if abs(int(num[-1])-int(i)) < 2:
                dfs(num + i,l)
if k <= 9:
    print(k)
else:
    for i in A:
        dfs(i,l)
    ans = sorted(ans)
    
    print(ans[k-1])

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    k = int(input())
    count = 0
    q = deque()
    for i in range(1, 10):
        q.append(str(i))
    while True:
        qi = q.popleft()
        last = int(qi[-1])
        if last != 0:
            q.append(qi + str(last - 1))
        q.append(qi + str(last))
        if last != 9:
            q.append(qi + str(last + 1))
        count += 1
        if count == k:
            print(qi)
            break


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
ans = []

def dfs(keta, value):
    ans.append(value)
    if keta == 10:
        return

    for j in range(-1, 2):
        add = (value % 10) + j
        if add >= 0 and add <= 9:
            dfs(keta+1, value * 10 + add)

def solve_D():
    k = int(input())
    for i in range(1, 10):
        dfs(1, i)
    ans.sort()
    return ans[k-1]


print(solve_D())

Solution (Python):
N = int(input())
R=[["1","2","3","4","5","6","7","8","9"]]
count=9
temp=[]
for i in range(N):
  if count>=N:
    break
  else:
    temp=[]
    for r in R[i]:
      if r[-1]=="9":
        temp.append(str(r)+str(int(r[-1])-1))
        temp.append(str(r)+str(int(r[-1])))
      elif r[-1]=="0":
        temp.append(str(r)+str(int(r[-1])))
        temp.append(str(r)+str(int(r[-1])+1))
      else:
        temp.append(str(r)+str(int(r[-1])-1))
        temp.append(str(r)+str(int(r[-1])))
        temp.append(str(r)+str(int(r[-1])+1))
    R.append(temp)
    count+=len(temp)
N=N-(count-len(temp))
print(R[-1][N-1])

Solution (Python):
k = int(input())
q = [1,2,3,4,5,6,7,8,9]
count = 0
if k <= 9:
    print(k)
else:
    while not count == k:
        count += 1
        x = q.pop(0)
        if x % 10 == 9:
            q.append(x * 10 + x % 10 -1)
            q.append(x * 10 + x % 10)
        elif x % 10 == 0:
            q.append(x * 10 + x % 10)
            q.append(x * 10 + x % 10 + 1)
        else:
            q.append(x * 10 + x % 10 - 1)
            q.append(x * 10 + x % 10)
            q.append(x * 10 + x % 10 + 1)
    print(x)

Solution (Python):
from queue import Queue

n = int(input())
if n <= 10:
    print(n)
    exit()
n -= 9
que = Queue()
for i in range(1, 10):
    que.put(i)

while True:
    i = str(que.get())
    last = int(i[-1])
    if last != 0:
        if n == 1:
            print(int(i+str(last-1)))
            break
        que.put(int(i+str(last-1)))
        n -= 1
    if n == 1:
        print(int(i+str(last)))
        break
    que.put(int(i+str(last)))
    n -= 1
    if last != 9:
        if n == 1:
            print(int(i+str(last+1)))
            break
        que.put(int(i+str(last+1)))
        n -= 1