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 heapq import heapify, heappop, heappush

def next_num(n):
    if n == 0:
        return [0, 1]
    elif n == 9:
        return [8, 9]
    else:
        return [n-1, n, n+1]

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

for _ in range(K-1):
    now = heappop(queue)
    for next_i in next_num(now%10):
        heappush(queue, now*10 + next_i)

print(queue[0])

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

k=int(input())

def dfs(keta,num):
  lunlun.append(int(num))
  if keta==10:
    return

  min_v=max(0,int(num[-1])-1)
  max_v=min(9,int(num[-1])+1)

  for i in range(min_v,max_v+1):
    dfs(keta+1,num+str(i))

lunlun=[]
for i in range(1,10):
  dfs(0,str(i))

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

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

def lunlun(d,v,L):
    L.append(v)
    if d == 10:
        return
    for i in range(-1,2):
        t = v%10 + i
        
        if 0 <= t <=9:
            lunlun(d+1,v*10+t,L)

for v in range(1,10):
    lunlun(1,v,L)
print(sorted(L)[k-1])

Solution (Python):
K = int(input())
L = [i for i in range(1, 10)]
cnt = 9
i = 0

while K > cnt:
  x = L[i]
  r = x % 10
  if r != 0:
    L.append(10*x + r - 1)
    cnt += 1
  L.append(10*x + r)
  cnt += 1
  if r != 9:
    L.append(10*x + r + 1)
    cnt += 1
  i += 1

print(L[K-1])

Solution (Python):
from itertools import chain

l = [[] for _ in range(11)]
l[0] = list(map(str, range(1, 10)))
for i in range(10):
    for x in l[i]:
        last = int(x[-1])
        for m in {max(0, last-1), last, min(9 ,last+1)}:
            m = str(m)
            l[i+1].append(x+m)

q = list(map(int, chain(*l)))
q.sort()

K = int(input())

print(q[K-1])

Solution (Python):
from collections import deque

K = int(input())

ans = []

queue = deque(range(1, 10))

while len(ans) < K:
    n = queue.popleft()
    ans.append(n)
    n_str = str(n)
    p = int(n_str[-1])
    if p - 1 >= 0:
        queue.append(int(n_str+str(p-1)))
    queue.append(int(n_str+str(p)))
    if p + 1 <= 9:
        queue.append(int(n_str+str(p+1)))

print(ans[-1])

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

Solution (Python):
import sys
from collections import deque
K = int(input())
q = deque([])
for i in range(1, 10):
    q.append(str(i))
ans = 0
while ans != K:
    l = q.popleft()
    ans += 1
    if ans == K:
        print(l)
        sys.exit()
    if l[-1] == '0':
        q.append(l + '0')
        q.append(l + '1')
    elif l[-1] == '9':
        q.append(l + '8')
        q.append(l + '9')
    else:
        q.append(l + str(int(l[-1]) - 1))
        q.append(l + str(int(l[-1])))
        q.append(l + str(int(l[-1]) + 1))

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

q=["1","2","3","4","5","6","7","8","9"]
x=9
for i in q:
    if x>100000:
        break
    x+=1
    a=i[-1]
    for j in ([-1,0,1]):
        bb=int(a)+j
        if bb<10 and bb>=0:
            q.append(i+str(bb))


print(q[k-1])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from decimal import *
 
K = INT()

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

for i in range(K):
    n = q.popleft()
    r = n%10

    if r != 0:
        q.append(10*n + r-1)

    q.append(10*n + r)

    if r != 9:
        q.append(10*n + r+1)

print(n)

Solution (Python):


import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    k = ni()
    q = deque(map(str, range(1, 10)))
    for i in range(k):
        n = q.popleft()
        last_n = n[-1]
        for diff in range(-1, 2):
            next_n = int(last_n) + diff
            if next_n >= 0 and next_n <= 9:
                q.append(n+str(next_n))
    print(n)
if __name__ == "__main__":
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from decimal import *
 
K = INT()


n = [-1]*11
cnt = 0

def DFS(n):
    global cnt
    for i in range(1, 11):
        if n[-i] == 9:
            continue
        elif n[-i-1] != -1 and n[-i] == n[-i-1]+1:
            continue
        else:
            if n[-i] == -1:
                n[-i] = 1
            else:
                n[-i] += 1

            for j in range(i-1, 0, -1):
                n[-j] = max(0, n[-j-1] - 1)
            break
    cnt += 1
    if cnt == K:
        print(*n[bisect(n, -1):], sep = "")
        exit()
    DFS(n)


DFS(n)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from decimal import *
 
K = INT()

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

n = [-1]*11
n[-1] = 9
cnt = 9


def DFS(n):
    global cnt
    for i in range(1, 11):
        if n[-i] == 9:
            continue
        elif n[-i-1] != -1 and n[-i] == n[-i-1]+1:
            continue
        else:
            if n[-i] == -1:
                n[-i] = 1
            else:
                n[-i] += 1

            for j in range(i-1, 0, -1):
                n[-j] = max(0, n[-j-1] - 1)
            break
    cnt += 1
    if cnt == K:
        print(*n[bisect(n, -1):], sep = "")
        exit()
    DFS(n)


DFS(n)

Solution (Python):
def f(k):
    import itertools

    N = [[str(i) for i in range(10)]]
    n = 0
    while n < k:
        T = []
        U = [n[0] for n in N[-1]]
        anchor = 0
        for i in range(len(U) - 1):
            if U[i] != U[i + 1]:
                T.append((anchor, i + 1))
                anchor = i + 1
        else:
            T.append((anchor, len(U)))
        M = []
        for i in range(10):
            for d in (-1, 0, 1):
                if 0 <= i + d < len(T):
                    for j in range(*T[i + d]):
                        M.append("{}{}".format(i, N[-1][j]))
        N[-1] = [n for n in N[-1] if not n.startswith("0")]
        n += len(N[-1])
        N.append(M)
    N = list(itertools.chain.from_iterable(N))
    return N[k - 1]


K = int(input())
print(f(K))

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

print(l[K-1])

Solution (Python):
def dfs(lls, curr_num, lim):
    if curr_num > lim: return
    lls.append(curr_num)
    last_num = int(str(curr_num)[-1])
    if last_num > 0:
        dfs(lls, curr_num*10+last_num-1, lim)
    if last_num < 9:
        dfs(lls, curr_num*10+last_num+1, lim)
    dfs(lls, curr_num*10+last_num, lim)


def main():
    k = int(input())
    lls = []
    for i in range(1,10):
        dfs(lls, i, 3234566668)

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


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


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


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)


def main():
    K = I()
    q = deque()
    for i in range(1, 10):
        q.append(i)
    for _ 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)


main()

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

def dfs(d,now,lunluns):
    lunluns.append(now)

    if d == 10:
        return
    
    for i in [-1,0,1]:
        add = now % 10 + i

        if 0 <= add <= 9:
            dfs(d+1,now*10+add, lunluns)
        
if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque
def bfs(k):
    lunlun = []
    q = deque()
    count = 0
    for i in range(1, 10):
        lunlun.append(i)
        q.append(i)
        count += 1

    if count >= k:return lunlun[k - 1]

    while True:
        num = q.popleft()
        tail = num % 10
        for i in [-1, 0, 1]:
            temp = tail + i
            if temp == -1 or temp == 10:continue
            q.append(num * 10 + temp)
            lunlun.append(num * 10 + temp)
            count += 1
            if k == count:return lunlun[k - 1]

k = int(input())
print(bfs(k))

Solution (Python):
from collections import deque

n=int(input())

if n < 10:
    print(n)
else:
    check_box = deque([1,2,3,4,5,6,7,8,9])
    check_num = 9
    while True:
        add_num = check_box.popleft()
        add_num = str(add_num)

        if int(add_num[-1]) - 1 >= 0:
            check_box.append(int(add_num + str(int(add_num[-1]) - 1)))
            check_num += 1
            if check_num == n:
                    print(add_num + str(int(add_num[-1]) - 1))
                    exit()

        check_num += 1
        check_box.append(int(add_num + add_num[-1]))
        if check_num == n:
                print(add_num + add_num[-1])
                exit()

        if int(add_num[-1]) + 1 <= 9:
            check_box.append(int(add_num + str(int(add_num[-1]) + 1)))
            check_num += 1
            if check_num == n:
                    print(add_num + str(int(add_num[-1]) + 1))
                    exit()

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

l = []

def c(depth, a, d):
    ans = 0
    if depth == d:
        l.append(a)
        return
    if int(a[-1]) - 1 >= 0:
        c(depth + 1, a + str(int(a[-1]) - 1), d)
    c(depth + 1, a + a[-1], d)
    if int(a[-1]) + 1 <= 9:
        c(depth + 1, a + str(int(a[-1]) + 1), d)
    return

for d in range(10):
    for i in range(1, 10):
        c(0, str(i), d)
        
print(l[K - 1])

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

al = []
def f(d, v, al):
    
    al.append(v)
    
    if d == 10:
        return
    
    for i in range(-1,2):
        add = (v%10) + i
        if add >= 0 and add <= 9:
            f(d+1, v*10+add, al)
            
            
for i in range(1,10):
    f(0, i, al)
    
al = sorted(al)

print(al[k-1])

Solution (Python):
import queue

k = int(input())

q = queue.Queue()

for i in range(9):
  q.put(i+1)
  
for i 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
n=int(input())-10
q=deque(range(1,10))
while n>=0:
    a=str(q.popleft())
    a=int(a+a[-1])
    for i in range(a-1,a+2):
        if str(i)[-2]==str(a)[-1]:
            q.append(i)
            n-=1
print(q[n])

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

def SUM(num,cnt,keta):
    global luncnt
    if luncnt > 10**5:
        return
    if int(cnt) > int(keta):
        lunlun.append(int(num))
        luncnt += 1
        return


    if len(num) == 0:
        for i in range(1,10):
            SUM(num+str(i),str(int(cnt)+1),keta)
    else:
        min = int(num[(len(num)-1)])-1
        max = min + 3
        for i in range(min,max):
            if i < 0 or i > 9:
                continue
            SUM(num+str(i),str(int(cnt)+1),keta)

keta = 0
while True:
    SUM('','0',str(keta))
    if luncnt > 10**5:
        break
    keta += 1

print(lunlun[K-1])

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

def dfs(keta, val):
  lunlun.append(val)

  if keta==10:
    return

  for i in range(-1,2):
    add=(val%10)+i
    if 0<=add<=9:
      dfs(keta+1, val*10+add)

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

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

Solution (Python):
k=int(input())
from collections import deque
q=deque([])
i=0
while True:
  if i<=8:
    q.append(i+1)
    i+=1
    if i==k:break
    continue
  
  x=q.popleft()
  
  if x%10!=0:
    q.append(x*10+x%10-1)
    i+=1
    if i==k:break
    
  q.append(x*10+x%10)
  i+=1
  if i==k:break
  
  if x%10!=9:
    q.append(x*10+x%10+1)
    i+=1
    if i==k:break
      
print(q.pop())

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



memo = set([])

PM = [-1,0,1]

def rec(n):
    if n > 3234566667:
        return
    ichi = n % 10
    for pm in PM:
        if (ichi + pm) != -1 and (ichi + pm) != 10:
            m = n*10 + ichi + pm
            if m not in memo:
                
                
                
                memo.add(m)
                rec(m)
    return

for i in range(1,10):
    memo.add(i)
    rec(i)







memo = list(memo)
memo.sort()



            
print(memo[K-1])

Solution (Python):
from queue import Queue

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

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

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

for i in range(1,K+1):
    ans = X.popleft()
    if ans%10!=0:
        temp = ans*10 + (ans%10)-1
        X.append(temp)

    temp = ans*10 + (ans%10)
    X.append(temp)
    
    if ans%10!=9:
        temp = ans*10 + (ans%10)+1
        X.append(temp)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def dfs(s):
  if len(s)==11:
    return
  if s!="":
    a.append(int(s))
  for c in "0123456789":
    if s=="" and c=="0":continue
    if len(s)>0:
      if abs(ord(s[-1])-ord(c))<=1:
        dfs(s+c)
    else:
        dfs(s+c)
k=int(input())
a=[]
dfs("")
a=list(set(a))
a.sort()
print(a[k-1])

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

if K <= 9:
  print(K)
else:
  for i in range(K):
    num = d[0]
    d.popleft()
    plus = int(10*num + num%10)
    if num % 10 != 0:
      d.append(plus-1)
    d.append(plus)
    if (i<K) and (num%10!=9):
      d.append(plus+1)
  print(num)

Solution (Python):
from functools import lru_cache

(K,) = [int(x) for x in input().split()]


def solve(K):
    def getNext(x):
        if x == 0:
            return [0, 1]
        if x == 9:
            return [8, 9]
        return [x - 1, x, x + 1]

    @lru_cache(maxsize=None)
    def getNum(begin, digits):
        if digits == 0:
            assert False
            return 0
        if digits == 1:
            return 1
        ans = 0
        for x in getNext(begin):
            ans += getNum(x, digits - 1)
        return ans

    ans = []
    count = 0
    for digits in range(1, 30):
        for i in range(1, 10):
            delta = getNum(i, digits)
            if count < K <= count + delta:
                ans.append(i)
                while digits > 1:
                    for x in getNext(ans[-1]):
                        delta = getNum(x, digits - 1)
                        if count < K <= count + delta:
                            ans.append(x)
                            digits -= 1
                            break
                        count += delta
                return "".join(map(str, ans))

            count += delta


print(solve(K))

Solution (Python):
K = int(input())
l = list(range(1,10))

for x in l:
    if x > 3234566667: break
    back = int(str(x)[-1])
    for b in [back-1, back, back+1]:
        if 0 <= b <= 9:
            l.append(10*x + b)

print(l[K-1])

Solution (Python):

import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, input().split()))


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


K = z()
lunlun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
if (K <= 9):
    print(lunlun[K-1])
    exit()
while len(lunlun) < K:
    for lun in lunlun:
        right = int(str(lun)[-1])
        if (right == 0):
            add = [0, 1]
        elif (right == 9):
            add = [8, 9]
        else:
            add = [right-1, right, right+1]
        for ad in add:
            
            lunlun.append(lun * 10 + ad)
        if (len(lunlun) >= K):
            break_flg = True
            break


print(lunlun[K-1])

Solution (Python):
K = int(input())
ans_list = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
nex = ans_list.copy()


def resp(n):
    if n == "0":
        return ["0", "1"]
    elif n == "9":
        return ["8", "9"]
    else:
        n_tmp = int(n)
        return [n, str(n_tmp + 1), str(n_tmp - 1)]


for j in range(1000):
    tmp = nex.copy()
    nex = []
    for i in tmp:
        nex += [i + x for x in resp(i[-1])]
    ans_list += nex
    if len(ans_list) > 10 ** 5:
        break

ans_list = list(map(int, ans_list))
ans_list.sort()
print(ans_list[K - 1])

Solution (Python):
from collections import deque
k = int(input())
def solve():
  count = 0
  stack_strings = deque([str(i) for i in range(9, -1, -1)])
  for _ in range(10):
    for _ in range(len(stack_strings)):
      lunstring = stack_strings.pop()
      if lunstring[0] != "0":
        count += 1
        if count == k:
          return(int(lunstring))
      right_char = lunstring[-1]
      if right_char == "0":
        [stack_strings.appendleft(lunstring+x) for x in ["0", "1"]]
      elif right_char == "9":
        [stack_strings.appendleft(lunstring+x) for x in ["8", "9"]]
      else:
        [stack_strings.appendleft(lunstring+x) for x in [str(int(right_char)-1), right_char, str(int(right_char)+1)]]
print(solve())

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


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 copy import copy
K = int(input())


lunlun_start =["1","2","3","4","5","6","7","8","9"]
lunlun_roop =copy(lunlun_start)
lunlun =[]
ans =copy(lunlun_start)
x=""
while len(ans) <K:

    lunlun =[]
    for i in lunlun_roop:
        if i[-1] =="0":
            lunlun.append(i+"0")
            lunlun.append(i+"1")
        elif i[-1] =="9":
            lunlun.append(i+"8")
            lunlun.append(i+"9")
        else:
            x =int(i+i[-1])-1
            lunlun.append((str(x) ))
            x +=1
            lunlun.append((str(x) ))
            x +=1
            lunlun.append((str(x) ))
        if len(lunlun) >K:
            break
    lunlun_roop =copy(lunlun)
    ans.extend(lunlun)
print(ans[K-1])

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


for i in range(k-1):
    a = q.popleft()
    last = int(a[-1:])
    if last == 0:
        q.append(a+"0")
        q.append(a + "1")
    elif last ==9:
        q.append(a+"8")
        q.append(a + "9")
    else:
        q.append(a + str(last - 1))
        q.append(a + str(last ))
        q.append(a + str(last + 1))

print(q.popleft())

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


def rec(past: int, num: int):
    nums.add(num)
    if num > 10**10:
        return
    if past > 0:
        rec(past - 1, num * 10 + past - 1)
    rec(past, num * 10 + past)
    if past < 9:
        rec(past + 1, num * 10 + past + 1)


for i in range(1, 10):
    rec(i, i)
ans = sorted(nums)
print(ans[k - 1])

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


def rec(past: int, num: int):
    nums.add(num)
    if num > 10**10:
        return
    if past > 0:
        rec(past - 1, num * 10 + past - 1)
    rec(past, num * 10 + past)
    if past < 9:
        rec(past + 1, num * 10 + past + 1)


for i in range(1, 10):
    rec(i, i)
ans = sorted(nums)
print(ans[k - 1])

Solution (Python):
from collections import deque
def main():
    k = int(input())
    d = deque(list(range(1, 10)))
    ans = 0
    for _ in range(k):
        ans = d.popleft()
        if ans % 10 != 0:
            d.append(10 * ans + (ans % 10) - 1)
        d.append(10 * ans + (ans % 10))
        if ans % 10 != 9:
            d.append(10 * ans + (ans % 10) + 1)
    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):
from collections import deque
K=int(input())
queue=deque(list(range(1,10)))
for i in range(K):
    k=queue.popleft()
    mod=k%10
    for diff in range(mod-1,mod+2):
        if diff<0 or 9<diff:
            continue
        queue.append(10*k+diff)
print(k)

Solution (Python):
def main():
    K = int(input())
    ans = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    count = 9
    if K <= count:
        print(ans[K-1])
    else:
        for x in ans:
            mod = x % 10
            base = 10*x + mod

            if mod != 0:
                ans.append(base-1)
                count += 1

            ans.append(base)
            count += 1

            if mod != 9:
                ans.append(base+1)
                count += 1

            if count >= K:
                break
        print(ans[K-1])


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
K=int(input())
queue=deque(list(range(1,10)))
for i in range(K):
    k=queue.popleft()
    if k%10!=0:
        queue.append(10*k+(k%10)-1)
    queue.append(10*k+(k%10))
    if k%10!=9:
        queue.append(10*k+(k%10)+1)
print(k)

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

Solution (Python):
def main():
    K = int(input())
    ans = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    count = 9
    if K <= count:
        print(ans[K-1])
    else:
        for x in ans:
            mod = x % 10
            base = 10*x + mod

            if mod != 0:
                ans.append(base-1)
                count += 1

            ans.append(base)
            count += 1

            if mod != 9:
                ans.append(base+1)
                count += 1

            if count >= K:
                break
        print(ans[K-1])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
from collections import deque
K = int(input())
queue = deque([1,2,3,4,5,6,7,8,9])
def rec(queue,i):
    x = queue[i]
    if x >= 3234566667:
        return queue
    r = x % 10
    if (r != 0):
        new_x = x * 10 + (r) - 1
        queue.append(new_x)
    new_x = x * 10 + (r)
    queue.append(new_x)
    if (r != 9):
        new_x = x * 10 + r + 1
        queue.append(new_x)
    return rec(queue,i+1)
res = rec(queue,0)
print(res[K-1])

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

n=int(input())
L=deque([i for i in range(1,10)])
if n<=9:
    ans = L[n-1]
else:
    cnt = 9
    for i in range(1,n):
        c=L.popleft()
        
        if c%10!=0:
            L.append(c*10+(c%10)-1)
            cnt+=1
            if cnt>=n:
                break
        L.append(c*10+(c%10))
        cnt+=1
        if cnt>=n:
            break
        
        if c%10!=9:
            L.append(c*10+(c%10)+1)
            cnt+=1
            if cnt>=n:
                break
    ans = L[-1]
print(ans)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

n=int(input())
L=deque(list(range(1,10)))
if n<=9:
    ans = L[n-1]
else:
    cnt = 9
    for i in range(1,n):
        c=L.popleft()
        
        if c%10!=0:
            L.append(c*10+(c%10)-1)
            cnt+=1
            if cnt>=n:
                break
        L.append(c*10+(c%10))
        cnt+=1
        if cnt>=n:
            break
        
        if c%10!=9:
            L.append(c*10+(c%10)+1)
            cnt+=1
            if cnt>=n:
                break
    ans = L[-1]
print(ans)

Solution (Python):
def chk(l):
  s=0
  for r in l:
    s+=r
    if (s<0)|(s>9):
      return False
  return True
def nml(l):
  ln=len(l)
  for i in range(1,ln):
    if l[-i]==2:
      l[-i]=-1
      l[-i-1]+=1
  if l[0]==10:
    return True
  return False


a=[1]
for i in range(int(input())-1):
  while True:
    if len(a)==1:
      a[0]+=1
      if a[0]==10:
        a=[1,-1]
    else:
      a[-1]+=1
      if nml(a):
        a=[1]+[-(j==0) for j in range(len(a))]
    if chk(a):
      break
rt=""
ss=0
for i in a:
  ss+=i
  rt+=str(ss)
print(rt)

Solution (Python):
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
q=deque(list(range(1,10)))
c=0
while c<a:
  t=q.popleft()
  c+=1
  if t%10!=0:
    q.append(10*t+(t%10)-1)
  q.append(10*t+(t%10))
  if t%10!=9:
    q.append(10*t+(t%10)+1)
print(t)

Solution (Python):
from heapq import heappop, heappush, heapify
k = int(input())
def next_num(n):
  if n == 0:
    return [0, 1]
  elif n == 9:
    return [8, 9]
  else:
    return [n-1, n, n+1]
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]
heapify(queue)
for _ in range(k-1):
  now = heappop(queue)
  for next_i in next_num(now%10):
    heappush(queue, now*10 + next_i)
    
print(heappop(queue))