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**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]









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

Solution (Python):

from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

queue = deque()


def main():
    k = int(input())
    queue.extend([1, 2, 3, 4, 5, 6, 7, 8, 9])

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


if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    from collections import deque
    K = int(input())
    q = deque([])
    cnt = 1
    while cnt <= K:
        if cnt < 10:
            q.append(cnt)
            cnt += 1
        else:
            base = q.popleft()
            last_digit = base % 10
            for diff in [-1, 0, 1]:
                if cnt > K:
                    continue
                new_last_digit = last_digit + diff
                if 0 <= new_last_digit <= 9:
                    new_lunlun = base*10 + new_last_digit
                    q.append(new_lunlun)
                    cnt += 1
    print(q[-1])

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
k = int(input()) 
ls = [[] for _ in range(10**4)] 
i = 0
ls[0] = [e for e in range(1,10)]
di = [0]*(10**4)
di[0] = 9
if k <= 9:
    print(k)
    sys.exit()
while True:
    for j in ls[i]:
        p = str(j)[-1]
        q = int(p)
        if p == "0":
            ls[i+1].append(10*j)
            ls[i+1].append(10*j+1)
        elif p == "9":
            ls[i+1].append(10*j+8)
            ls[i+1].append(10*j+9)
        else:
            ls[i+1].append(10*j+q-1)
            ls[i+1].append(10*j+q)
            ls[i+1].append(10*j+q+1)
    di[i+1] = di[i] + len(ls[i+1])
    if di[i+1] >= k:
        print(ls[i+1][k-di[i]-1])
        break
    i += 1

Solution (Python):
k = int(input())
from collections import deque
queue = deque([i+1 for i in range(9)])
anses = [i+1 for i in range(9)]
while len(anses) < k:
    now = deque.popleft(queue)
    last = now%10
    if last == 0:
        look = [0, 1]
    elif last == 9:
        look = [8, 9]
    else:
        look = [last-1, last, last+1]
    for i in look:
        anses.append((10*now) + i)
        queue.append((10*now) + i)
print(anses[k-1])

Solution (Python):
from collections import deque

k = int(input())

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

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

Solution (Python):
from collections import deque

k = int(input())

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

if k < 10:
    print(k)
    
else:
    while True:
        x = num.popleft()
        if x % 10 != 0:
            num.append(10*x +(x % 10)-1)
            num0.append(10*x +(x % 10)-1)
            if len(num0) == k:
                break
        num.append(10*x +(x % 10))
        num0.append(10*x +(x % 10))
        if len(num0) == k:
            break
        if x % 10 != 9:
            num.append(10*x +(x % 10)+1)
            num0.append(10*x +(x % 10)+1)
            if len(num0)==k:
                break
    print(num0[-1])

Solution (Python):








from collections import deque

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

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

    for _ in range(K):
        n=lnln.popleft()
        if n%10!=0:
            lnln.append(n*10+(n%10)-1)
        lnln.append(n*10+(n%10))
        if n%10!=9:
            lnln.append(n*10+(n%10)+1)

    print(n)

if __name__=="__main__":
    main()

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-1):
    num = d.popleft()
    mod = num % 10
    if mod != 0:
        d.append(num*10+mod-1)
    d.append(num*10+mod)
    if mod != 9:
        d.append(num*10+mod+1)
print(d.popleft())

Solution (Python):
from collections import deque

k = int(input())

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

for idx in range(k):
    ret = deq.popleft()
    
    residue = ret % 10
    if residue != 0:
        deq.append(ret * 10 + residue - 1)
    
    deq.append(ret * 10 + residue)

    if residue != 9:
        deq.append(ret * 10 + residue + 1)

print(ret)

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

neighbors = {'0': ['0', '1'], '1': ['0', '1', '2'], '2': ['1', '2', '3'], 
             '3': ['2', '3', '4'], '4': ['3', '4', '5'], '5': ['4', '5', '6'], 
             '6': ['5', '6', '7'], '7': ['6', '7', '8'], '8': ['7', '8', '9'], 
             '9': ['8', '9']}
queue = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
count = 0

while True:
  num = queue.pop(0)
  count += 1
  if count == k:
    print(int(num))
    break
  else:
    num_last = num[-1]
    lst = neighbors[num_last]
    for ele in lst:
      num_add = num + ele
      queue.append(num_add)

Solution (Python):
K = int(input())
import sys
from queue import Queue
queue = Queue()
for i in range(1,10):
  queue.put(i)
if K <= 9:
  print(K)
  sys.exit()
count = 0
while True:
  j = queue.get()
  count += 1
  if count == K:
    print(j)
    break
  if j % 10 != 0:
    queue.put(10*j+(j%10)-1)
  queue.put(10*j+(j%10))
  if j % 10 != 9:
    queue.put(10*j+(j%10)+1)

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

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

if k<10:
    print(num[k-1])
    exit()

ans=9

def hantei():
    global ans
    ans+=1
    if ans==k:
        print(num[-1])
        exit()

for i in range(10**10):

    hitoketa=num[0]%10

    if hitoketa==0:
        num.append(10*num[0]+0)
        hantei()
        num.append(10*num[0]+1)
        hantei()
        num.pop(0)

    elif hitoketa==9:
        num.append(10*num[0]+8)
        hantei()
        num.append(10*num[0]+9)
        hantei()
        num.pop(0)

    else:
        num.append(10*num[0]+(hitoketa-1))
        hantei()
        num.append(10*num[0]+(hitoketa))
        hantei()
        num.append(10*num[0]+(hitoketa+1))
        hantei()
        num.pop(0)

Solution (Python):
from collections import deque

K = int(input())
q = deque()

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

k = 0
while True:
	n = q.popleft()
	k += 1
	if k == K:
		break
	if (n % 10) % 10 != 0:
		q.append(10 * n + (n % 10) - 1)
	q.append(n * 10 + (n % 10))
	if (n % 10) % 10 != 9:
		q.append(10 * n + (n % 10) + 1)
print(n)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import ceil, log
def main():
    k = int(input())
    k2 = int(log(ceil(k / 10), 3)) + 1
    def getlun(n, keta, last):
        lunluns.append(n)
        if keta > k2:
            pass
        else:
            l1 = n * 10 + last
            getlun(l1, keta + 1, last)
            if last > 0:
                l2 = n * 10 + last - 1
                getlun(l2, keta + 1, last - 1)
            if last < 9:
                l3 = n * 10 + last + 1
                getlun(l3, keta + 1, last + 1)
    lunluns = []
    for i1 in range(1, 10):
        getlun(i1, 0, i1)
    lunluns.sort()
    print(lunluns[k-1])

if __name__ == '__main__':
    main()

Solution (Python):

from collections import deque

K = int(input())
q = deque(list(range(1, 10)))
for _ in range(K - 1):
    u = q.popleft()
    n = u % 10
    for x in range(max(0, n - 1), min(9, n + 1) + 1):
        q.append(u * 10 + x)

print(q.popleft())

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()
  y = 10 * x + x % 10
  if x % 10:
    q.append(y - 1)
  q.append(y)
  if x % 10 != 9:
    q.append(y + 1)

print(x)

Solution (Python):
k=int(input())
a=[]
for i in range(1,10):
    a.append(i)
s=0
t=8
for i in range(1,10):
    for j in range(s,t+1):
        if str(a[j])[len(str(a[j]))-1]=="0":
            a.append(str(a[j])+"0")
            a.append(str(a[j])+"1")
        elif str(a[j])[len(str(a[j]))-1]=="9":
            a.append(str(a[j])+"8")
            a.append(str(a[j])+"9")
        else:
            c=int(str(a[j])[len(str(a[j]))-1])-1
            d=int(str(a[j])[len(str(a[j]))-1])
            e=int(str(a[j])[len(str(a[j]))-1])+1
            a.append(str(a[j])+str(c))
            a.append(str(a[j])+str(d))
            a.append(str(a[j])+str(e))
    s=t+1
    t=len(a)-1
print(a[k-1])

Solution (Python):
from collections import deque

k = int(input())

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

while count <= k:
    v = d.popleft()
    count += 1
    last = str(v)[-1]
    if last == '0':
        d.append(int(str(v) + '0'))
        d.append(int(str(v)+'1'))
    elif last == '9':
        d.append(int(str(v) + '8'))
        d.append(int(str(v) + '9'))
    else:
        d.append(int(str(v) + str(int(last) - 1)))
        d.append(int(str(v) + str(int(last) )))
        d.append(int(str(v) + str(int(last) + 1)))
    


print(v)

Solution (Python):
from collections import deque

k = int(input())


if k < 10:
    print(k)
    exit()

q = deque()
lun = []
for i in range(1, 10):
    q.append(i)
    lun.append(i)

cnt = 9
while cnt < k:
    x = q.popleft()
    if x % 10 == 0:
        nx = 10 * x
        q.append(nx)
        lun.append(nx)
        nx = 10 * x + 1
        q.append(nx)
        lun.append(nx)
        cnt += 2
    elif x % 10 == 9:
        nx = 10 * x + 8
        q.append(nx)
        lun.append(nx)
        nx = 10 * x + 9
        q.append(nx)
        lun.append(nx)
        cnt += 2
    else:
        m = x % 10
        nx = 10 * x + m - 1
        q.append(nx)
        lun.append(nx)
        nx = 10 * x + m
        q.append(nx)
        lun.append(nx)
        nx = 10 * x + m + 1
        q.append(nx)
        lun.append(nx)
        cnt += 3
lun.sort()
print(lun[k-1])

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


for i in range(k):
    x = l.popleft()
    mod = x % 10
    if mod != 0:
        l.append(x*10 + mod - 1)
    l.append(x*10 + mod)
    if mod != 9:
        l.append(x*10 + mod + 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):
  num = q.popleft()
  if num%10 != 0:
    q.append(num*10+num%10-1)
  q.append(num*10+num%10)
  if num%10 != 9:
    q.append(num*10+num%10+1)

print(num)

Solution (Python):
from collections import deque

K = int(input())

q = deque()

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

cnt = 0

while True:
    a = q.pop()
    cnt += 1
    if cnt == K:
        print(a)
        exit()
    for i in (-1, 0, 1):
        m = a % 10 + i
        if not m < 0 and not m > 9:
            q.appendleft(a * 10 + m)

Solution (Python):
k = int(input())
prev_lunlun = list(range(1, 10))
lunlun = prev_lunlun[:]

while len(lunlun) < k:
    next_lunlun = []
    for x in prev_lunlun:
        r = x % 10
        y = x * 10 + r
        next_lunlun.append(y)
        if r != 9:
            next_lunlun.append(y+1)
        if r != 0:
            next_lunlun.append(y-1)
    lunlun += next_lunlun
    prev_lunlun = next_lunlun
lunlun.sort()
print(lunlun[k-1])

Solution (Python):
k = int(input())
hp = [i for i in range(k+4)]
r, w = 1, 10
while w <= k:
  n = hp[r]
  r += 1
  nm = n % 10
  val = n * 10 + nm
        
  if nm != 0:
    hp[w] = val - 1
    w += 1
  hp[w] = val
  w += 1
  if nm != 9:
    hp[w] = val + 1
    w += 1

print(hp[k])

Solution (Python):
import sys
import lzma
import pickle
k = int(sys.stdin.read())
t = pickle.loads(lzma.decompress(b'\xfd7zXZ\x00\x00\x04\xe6\xd6\xb4F\x02\x00!\x01\x16\x00\x00\x00t/\xe5\xa3\xe5\xfa\xa3\xef\xfe]\x00@\x01\x0em\x19\xae\x1d\xcdM\xd6N\x1eW\x07\xb6\x84\x97\x07\xa6\xf8\xc1\xd0\x952\xbb\xb6\x16\xaaA\x07f\xe8*\x94\x7fa\xdaI\xa1\xd4\xcbVt\x07\xf5\xefX\xef=\xb4\'\x9e\xe1\xca\xa6\x9d?\x08\xe6\xb2\x98\x8e\xd7-X\x90\xcd\xbb\x99\x19\x95\xe4\xd3\xa3\x8fE\xba\xb1\x8d=\x1a\x93\xffP\xd5\xe7\xa8s\xffL\x16}\x8c\xa28\xc3~KT4\xe8g\xa6\xae\xe0.q\xdf3\xe7?\xea\x0bR\rcr~\xd8,er\x15\xc4t\xff\xbb\x81\xf4\xaa\x10u\xf4\xebGc\xd7\x1a\x99\xda5\x18\xf4\xa2\xe2@\xc8\x9b\xaf\x992\xda\x86\xd8\xd8\x0fD\x1a\xcdT\x0f\x90\xbff\x17y\xa3q\x83\x05\xdai\x96\xcexPEOoo?\x08e\xf6E\xdb\xf2\xadJ\xab\x86\xe4\x81y\x0c\xaa\x95c\xdb\x84)d\xca\x96\x82\xfe\xcb\x07-\x88\xa0\xf3M\xec\xe66i~\xceW\xaf\xd0\xadZ:\xd3\x0f\xb8+\x1c\xec\x86-x\x9f\xf8\xa8s\x9f\xd8H`EU]\xe8\xaf\xf5\xb8\x7f4=\x98\x8c\xa1 \x99b\xcd6\x82ov]\xc6\xbe\x11+\xaf\xa5}i\xed\\=\x81\xbe\xb2\xadMV\xcb\xf0\xaf3
print(t[k - 1])

Solution (Python):
import sys
import collections


def resolve(in_):
    k = int(next(in_))

    q = collections.deque(range(1, 10))
    lunlun = q.popleft()

    for _ in range(k - 1):
        a = lunlun * 10
        m = lunlun % 10
        if (b := m - 1) >= 0:
            q.append(a + b)
        q.append(a + m)
        if (b := m + 1) <= 9:
            q.append(a + b)
        lunlun = q.popleft()

    return lunlun


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

k = inp()

runrun = [["1","2","3","4","5","6","7","8","9"]]
runrun_int = []

for j in range(2,11):
    tmp = []
    for i in range(len(runrun[j - 2])):
        if runrun[j-2][i][j-2] == "0":
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2])))
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2]) + 1))
        elif runrun[j-2][i][j-2] in ["1","2","3","4","5","6","7","8"]:
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2]) - 1))
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2])))
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2]) + 1))
        elif runrun[j-2][i][j-2] == "9":
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2]) - 1))
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2])))
    runrun.append(tmp)

ans = []
for i in range(len(runrun)):
    for j in range(len(runrun[i])):
        ans.append(int(runrun[i][j]))
ans.sort()

print(ans[k - 1])

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

K = int(input())

Q = queue.Queue()

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

ans = 1
for k in range(K):
    ans = Q.get()
    ansm = ans % 10
    if ans%10 != 0:
        Q.put(10 * ans + ansm - 1)
    Q.put(10 * ans + ansm)
    if ans%10 != 9:
        Q.put(10 * ans + ansm + 1)

print(ans)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


lun = [[str(i)] for i in range(10)] + [[]]
olun =[[str(i)] for i in range(10)] + [[]]

ans = [str(i) for i in range(1,10)]

while True:
    for i in range(0,10):
        lun[i] = list(map(lambda x: str(i) + x, (olun[i-1]+olun[i]+olun[i+1])))
        if i>= 1: ans += lun[i]

    if len(ans) >= 10**5 + 5: break
    olun = copy.deepcopy(lun)

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

Solution (Python):
from collections import deque

k = int(input())
cnt = 9
q = deque([])
for i in range(1,10):
    q.append(i)
ans = 0

if k < 10:
    print(k)
else:
    while cnt != k:
        n = q.popleft()
        if n%10 == 0:
            tmp = n*10
            q.append(n*10)
            cnt += 1
            if cnt == k:
                print(tmp)
                break
            q.append(1+tmp)
            cnt += 1
            if cnt == k:
                print(tmp+1)
                break
        elif n%10 == 9:
            tmp = n*10
            q.append(tmp+8)
            cnt+=1
            if cnt == k:
                print(tmp+8)
                break
            q.append(tmp+9)
            cnt += 1
            if cnt == k:
                print(tmp+9)
                break
        else:
            tmp = n%10
            q.append(tmp-1+(n*10))
            cnt += 1
            if cnt ==k:
                print(tmp-1+(n*10))
                break
            q.append(tmp+(n*10))
            cnt +=1
            if cnt == k:
                print(tmp+(n*10))
                break
            q.append(tmp+1+(n*10))
            cnt += 1
            if cnt == k:
                print(tmp+1+(n*10))
                break

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

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

while True:
    if k <= len(RunRun):
        print(RunRun[k-1])
        exit()
        
    k -= len(RunRun)
    
    now = []
    now, RunRun = RunRun, now

    for r in now:
        for i in range(-1, 2):
            tmp = r % 10 + i
            if tmp < 0 or 9 < tmp: continue
            tmp = (r * 10) + tmp
            RunRun.append(tmp)

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

S=[str(_) for _ in range(10)]
ans=S[1:]
S_=[]
for i in range(10):
    for s in S:
        if abs(int(s[0])-i)<=1:
            S_.append(str(i)+s)
            if i!=0:
                ans.append(str(i)+s)
            
for _ in range(9):

    S=S_.copy()
    S_=[]
    
    S_dict={}

    for i in range(10):
        S_dict[i]=[]

    s_zero=0
    for i in range(10):
        for s in S:
            if abs(int(s[0])-i)<=1:
                S_.append(str(i)+s)
                if i!=0:
                    ans.append(str(i)+s)
                    
    if len(ans)>K+10:
        break
                                
print(ans[K-1])

Solution (Python):
import queue

def main():
    k = int(input())
    q = queue.Queue()
    for i in range(1, 10):
        q.put(str(i))
    ans = ""
    for i in range(1, k+1):
        ans = q.get()
        if i < k:
            p = int(ans[-1])
            if p == 0:
                q.put(ans + "0")
                q.put(ans + "1")
            elif p == 9:
                q.put(ans + "8")
                q.put(ans + "9")
            else:
                for v in range(p-1, p+2):
                    q.put(ans + str(v))
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

k = int(input())

x = 0
q = deque(list(range(1, 10)))
for _ in range(k):
    x = q.popleft()
    d = x % 10
    y = 10 * x + d
    if d > 0:
        q.append(y - 1)
    q.append(y)
    if d < 9:
        q.append(y + 1)
print(x)

Solution (Python):
from collections import deque

n = int(input())
q = deque(range(1, 10))
for _ in range(n - 1):
    x = q.popleft()
    r = x % 10
    y = 10 * x
    if r == 0:
        q.extend([y, y+1])
    elif r == 9:
        q.extend([y+8, y+9])
    else:
        q.extend([y+r-1, y+r, y+r+1])
print(q.popleft())

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):
    x = queue.popleft()
    

    if x % 10 != 0:
        queue.append(10 * x + (x % 10) - 1)

    queue.append(10 * x + x % 10)

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

print(x)

Solution (Python):

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

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

a = 0
while count < K:
  
  a = q.get()
  fp = int(str(a)[-1])
  if fp == 0:
    q.put(a*10)
    q.put(a*10 + 1)
  elif fp == 9:
    q.put(a*10 + 8)
    q.put(a*10 + 9)
  else:
    q.put(a*10 + fp - 1)
    q.put(a*10 + fp)
    q.put(a*10 + fp + 1)
  count += 1

print(a)

Solution (Python):
from collections import deque

n = int(input())
q = deque(range(1, 10))
for _ in range(n - 1):
    x = q.popleft()
    r = x % 10
    y = 10 * x
    if r == 0:
        q.extend([y, y+1])
    elif r == 9:
        q.extend([y+8, y+9])
    else:
        q.extend([y+r-1, y+r, y+r+1])
print(q.popleft())

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

queue = list(range(1,10))
counter = 0
while counter != K - 1:
    num = queue[counter]
    ichi = num % 10
    num *= 10
    if ichi != 0:
        queue.append(num + ichi - 1)
    queue.append(num + ichi)
    if ichi != 9:
        queue.append(num + ichi + 1)
    counter += 1
print(queue[counter])

Solution (Python):
def main():
    k = int(input())
    if k<10:
        print(k)
        return
    que = [i for i in range(1,10)]
    cnt = 0
    while True:
        q = que.pop(0)
        cnt += 1
        if cnt==k:
            print(q)
            return
        if q%10==0:
            que.append(q*10)
            que.append(q*10+1)
        elif q%10==9:
            que.append(q*10+9-1)
            que.append(q*10+9)
        else:
            que.append(q*10+q%10-1)
            que.append(q*10+q%10)
            que.append(q*10+q%10+1)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

K = int(input())

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

count = 0
while queue:
    number = queue.pop()
    count += 1

    if count == K:
        print(number)
        break

    last_number = int(str(number)[-1])
    add_center = number * 10 + last_number

    if last_number > 0:
        queue.appendleft(add_center - 1)

    queue.appendleft(add_center)

    if last_number < 9:
        queue.appendleft(add_center + 1)

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):
    x = queue.popleft()
    if x % 10 != 0:
        queue.append(10 * x + (x % 10) - 1)
    queue.append(10 * x + x % 10)
    if x % 10 != 9:
        queue.append(10 * x + x % 10 + 1)

print(x)

Solution (Python):
import collections

def main():
    k = int(input())
    Q = collections.deque([int(i) for i in range(1, 10)])
    chk = False
    for i in range(k):
        x = Q.popleft()
        if i + len(Q) > k:
            chk = True
        if chk:
            continue
        else:
            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)

if __name__ == "__main__":
    main()

Solution (Python):
import collections

k = int(input())
Q = collections.deque([int(i) for i in range(1, 10)])
chk = False
for i in range(k):
    x = Q.popleft()
    if i + len(Q) > k:
        chk = True
    if chk:
        continue
    else:
        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)

Solution (Python):
import collections

k = int(input())
Q = collections.deque([int(i) for i in range(1, 10)])
for _ 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)

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

for _ in range(k):
    x = que.popleft()
    if not x % 10 == 0:
        
        que.append(10*x+(x%10)-1)
    que.append(10*x+(x%10))
    if not x %10 == 9:
        que.append(10*x+(x%10)+1)
print(x)

Solution (Python):
k = int(input())
cur = [[1]*10 for i in range(11)]
if k <= 9:
  print(k)
  exit()
c = 9
i = 0
while c < k:
  i += 1
  for j in range(10):
    cur[i][j] = cur[i-1][j]
    if j != 0:
      cur[i][j] += cur[i-1][j-1]
    if j != 9:
      cur[i][j] += cur[i-1][j+1]
  if c+sum(cur[i][1:]) >= k:
    break
  else:
    c += sum(cur[i][1:])
ans = ''
for j in range(i,-1,-1):
  for l in range(10):
    if j == i and l == 0:
      continue
    if j != i and abs(l-int(ans[-1])) > 1:
      continue
    if c + cur[j][l] >= k:
      ans += str(l)
      break
    else:
      c += cur[j][l]
print(ans)

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

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

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

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

Solution (Python):
from collections import deque
import heapq
k = int(input())
s =[1,2,3,4,5,6,7,8,9,10]
heapq.heapify(s)
li = set()
for val in range(1,2**11):
    v = int(str(bin(val)[2:]))
    li.add(v)
while len(li)<=301000:
    val = heapq.heappop(s)
    li.add(val)
    if str(val)[-1]=='0':
        heapq.heappush(s,10*val)
        heapq.heappush(s,10*val + 1)
    elif str(val)[-1]=='9':
        heapq.heappush(s,10*val + 8)
        heapq.heappush(s,10*val + 9)
    else:
        heapq.heappush(s,10*val + int(str(val)[-1]))
        heapq.heappush(s,10*val + int(str(val)[-1])+1)
        heapq.heappush(s,10*val + int(str(val)[-1])-1)
L = list(li)
L.sort()
print(L[k-1])

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

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

cnt = 0
while True:
    n = l.popleft()
    cnt +=1
    if cnt ==K:
        print(n)
        exit()

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

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

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

Solution (Python):

from collections import deque

K = int(input())
q = deque(list(range(1, 10)))
cnt = 0
ans = 0
while True:
    u = q.popleft()
    cnt += 1
    if cnt == K:
        ans = u
        break

    ll = u % 10
    for i in range(max(0, ll - 1), min(9, ll + 1) + 1):
        q.append(u * 10 + i)

print(ans)

Solution (Python):
def skip_num(num_digits:list, compare_digit):
    compare_upper_digit = num_digits[compare_digit]
    compare_lower_digit = num_digits[compare_digit + 1]
    if compare_upper_digit > compare_lower_digit:
        num_digits[compare_digit + 1] = compare_lower_digit + 1
        if compare_digit + 2 > len(num_digits):
            num_digits[compare_digit + 2:] = [0] * (len(num_digits) - compare_digit - 2)
    else: 
        num_digits[compare_digit] = compare_upper_digit + 1
        num_digits[compare_digit + 1:] = [0] * (len(num_digits) - compare_digit - 1)
    
    return int("".join([str(i) for i in num_digits]))

K = int(input())

lunlun_count = 0
num = 0
while True:
    num += 1
    if num < 10:
        lunlun_count += 1
    else:
        num_digits = list(map(int, str(num)))
        is_lunlun = True
        for i in range(len(num_digits) - 1):
            if abs(num_digits[i] - num_digits[i + 1]) > 1:
                is_lunlun = False
                num = skip_num(num_digits, i) - 1
                break
            
        if is_lunlun:
            lunlun_count += 1
    if lunlun_count >= K:
        break

print(num)

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

Solution (Python):
from collections import deque
k=int(input())
d=deque()
for i in range(1,10): d.append(i)
for i in range(k):
  x=d.popleft()
  if i==k-1:
    print(x)
    break
  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)

Solution (Python):
from collections import deque

K = int(input())
L = deque()
for i in range(9):
    L.append((i+1))

for i in range(K):
    ans = L.popleft()
    if ans % 10:
        L.append(10*ans+ans%10-1)
    L.append(10*ans+ans%10)
    if ans % 10-9:
        L.append(10*ans+ans%10+1)

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

K = int(input())

ans = set()
def dfs(last, lis):
    ans.add(int(''.join(lis)))
    if len(lis)==11:
        return
    dfs(last, lis+str(last))
    if last!=0:
        dfs(last-1, lis+str(last-1))
    if last!=9:
        dfs(last+1, lis+str(last+1))

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

ans = list(ans)
ans.sort()
print(ans[K-1])

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

q = collections.deque()
for i in range(9):
    q.append(i+1)
while(q):
    x = q.popleft()
    k = x % 10
    for j in range(3):
        if k == 0 and j == 0:
            continue
        elif k == 9 and j == 2:
            continue
        else:
            if j == 0:
                q.append(x*10+k-1)
            elif j == 1:
                q.append(x*10 + k)
            else:
                q.append(x*10+k+1)
    
    
    K -= 1
    if K == 0:
        print(x)
        break