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()) 
a = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

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

Solution (Python):
from collections import deque
k = int(input())
c = 0
q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
i = 0
while True:
    i = q.popleft()
    c += 1
    if c == k:
        break
    else:
        e = int(str(i)[-1])
        if e == 0:
            q.append(int(str(i)+str(e)))
            q.append(int(str(i)+str(e+1)))
        elif e == 9:
            q.append(int(str(i)+str(e-1)))
            q.append(int(str(i)+str(e)))
        else:
            q.append(int(str(i)+str(e-1)))
            q.append(int(str(i)+str(e)))
            q.append(int(str(i)+str(e+1)))

print(i)

Solution (Python):
k=int(input())
num=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]
keta=0
for i in range(0,k):
  for j in range(0,len(num)-1):
    if num[j]==-1:
      num[j]=1
      keta=j
      break
    elif num[j]!=9 and (num[j+1]==-1 or (num[j]-num[j+1])<1):
      num[j]+=1
      break
  for x in range(j-1,-1,-1):
    num[x]=max(0,num[x+1]-1)

for i in range(keta,-1,-1):
  print(num[i],end='')
print()

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

a = []
for i in range(1, 10):
    a.append(i)

while True:
    if k <= len(a):
        print(a[k - 1])
        exit(0)
    else:
        k -= len(a)
    old = a
    a = []
    for x in old:
        d = x % 10
        if d > 0:
            a.append(x * 10 + d - 1)
        a.append(x * 10 + d)
        if d < 9:
            a.append(x * 10 + d + 1)

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

q = queue.Queue()

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

for i in range(K-1):
    x = q.get()

    if x%10 == 0:
        q.put(x*10 + 0)
        q.put(x*10 + 1)
    elif x%10 == 9:
        q.put(x*10 + 8)
        q.put(x*10 + 9)
    else:
        q.put(x*10 + x%10-1)
        q.put(x*10 + x%10)
        q.put(x*10 + x%10+1)
    
print(q.get())

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

List = [i for i in range(1, 10)]
latest_added = List.copy()
newly_add = []

count = 9
for _ in range(10000000):
    for i in latest_added:
        mod10 = i % 10
        if mod10 != 0:
            newly_add.append(i * 10 + mod10 - 1)
            count += 1

        newly_add.append(i * 10 + mod10)
        count += 1

        if mod10 != 9:
            newly_add.append(i * 10 + mod10 + 1)
            count += 1


    List += newly_add
    latest_added = newly_add.copy()
    newly_add = []

    if count >= k:
        break

print(List[k - 1])

Solution (Python):


MOD = 10**9
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors




K = int(input())

r = [1,2,3,4,5,6,7,8,9]
if K < 10:
    print(r[K-1])
    exit()
f = True
index = 10
cnt = 0
start = 0
while f==True:
    r_len = len(r)
    for i in range(start, r_len):
        s = str(r[i])
        migi = len(s)-1
        ix1 = str(int(s[migi])-1)
        ix2 = str(int(s[migi])+1)
        if int(ix1)>=0:
            r.append(int(s+ix1))
        r.append(int(s+s[migi]))
        if int(ix2)<=9:
            r.append(int(s+ix2))
    start = r_len
    if len(r) > 100000:
        f = False

r = sorted(r)
print(r[K-1])

Solution (Python):

from sys import stdin
from operator import itemgetter
from collections import deque
import math


K = int(stdin.readline().rstrip())
a = deque(range(1,10))
ans_list = deque()
attack = 100000
while attack > 0:
    ans = a.popleft()
    ue = ans*10
    shimo = ans%10
    ans_list.append(ans)
    if shimo == 0:
        a.append(ue)
        a.append(ue+1)
    elif shimo == 9:
        a.append(ue+shimo-1)
        a.append(ue+shimo)
    else:
        a.append(ue+shimo-1)
        a.append(ue+shimo)
        a.append(ue+shimo+1)
    attack -= 1

print(ans_list[K-1])

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

MAX = 3234566667
ans = []
def rec(x):
    if int(x) > MAX:
        return
    ans.append(int(x))
    last = int(x[-1])
    rec(x+str(last))
    if last != 0:
        rec(x+str(last-1))
    if last != 9:
        rec(x+str(last+1))
    return

K = INT()

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

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

Solution (Python):

from sys import stdin
from operator import itemgetter
from collections import deque
import math


K = int(stdin.readline().rstrip())
a = deque(range(1,10))
ans_list = []
attack = 100000
while attack > 0:
    ans = a.popleft()
    ue = ans*10
    shimo = ans%10
    ans_list.append(ans)
    if shimo == 0:
        a.append(ue)
        a.append(ue+1)
    elif shimo == 9:
        a.append(ue+shimo-1)
        a.append(ue+shimo)
    else:
        a.append(ue+shimo-1)
        a.append(ue+shimo)
        a.append(ue+shimo+1)
    attack -= 1

print(ans_list[K-1])

Solution (Python):
q=[]

k=int(input())

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




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

ops=0
t=[]
while(ops<k):

    x = q.pop(0)
    t.append(x)
    if(x%10!=0):
        ops+=1
        q.append(10*x + x%10 -1)
    q.append(10*x+ x%10)
    ops+=1

    if(x%10!=9):
        q.append(10*x + x%10 + 1)
        ops+=1
final = t+q

print(final[k-1])

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

MAX = 3234566667
ans = []
def rec(x, di):
    if di == 10:
        return
    if int(x) > MAX:
        return
    ans.append(int(x))
    last = int(x[-1])
    rec(x+str(last), di+1)
    if last != 0:
        rec(x+str(last-1), di+1)
    if last != 9:
        rec(x+str(last+1), di+1)
    return

K = INT()

for i in range(1, 10):
    rec(str(i), 0)

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

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

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

    q = deque()
    for i in range(1, 10):
        q.append(i)
    now = 0
    for _ in range(N):
        now = q.popleft()
        tmp = now%10
        if tmp != 0:
            q.append(now * 10 + tmp - 1)
        q.append(now * 10 + tmp)
        if tmp != 9:
            q.append(now * 10 + tmp + 1)
    print(now)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

d = deque()

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

n=int(input())
if n<10:
    print(n)
else:
    i=0
    cnt=0
    now=d.popleft()
    while i<n-9:
        if cnt==0:
            if now%10!=0:
                d.append(now*10+now%10-1)
                i+=1
            cnt+=1
            continue
        if cnt==1:
            d.append(now*10+now%10)
            cnt+=1
            i+=1
            continue
        if cnt==2:
            if now%10!=9:
                d.append(now*10+now%10+1)
                i+=1
            cnt=0
            now=d.popleft()
    print(d.pop())

Solution (Python):
from heapq import heappush, heappop

K = int(input())
hq = []
for i in range(1,10):
  heappush(hq,i)
cnt = 0
while(cnt < K):
  x = heappop(hq)
  cnt += 1
  for i in [-1,0,1]:
    d = (x%10)+i
    if 0 <= d <= 9:
      heappush(hq,x*10+d)
print(x)

Solution (Python):
from collections import deque

k = int(input())
q = deque()

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

while True:
    
    if len(q)>= k:
        print(q[k-1])
        exit()
    k -= len(q)

    for _ in range(len(q)):
        x = q.popleft()
        for i in [-1, 0, 1]:
            d = x % 10 + i
            if d < 0 or d > 9:
                continue
            q.append(10 * x + d)

Solution (Python):
from collections import deque
lunlun=[i for i in range(1,10)]
def bfs(K):
    d=deque([1,2,3,4,5,6,7,8,9])
    while(len(lunlun)<K):
        s=d[0]
        d.popleft()
        n=[]
        if(s%10!=0):
            n.append((s%10-1)+s*10)
        n.append(s%10+s*10)
        if(s%10!=9):
            n.append((s%10+1)+s*10)
        lunlun.extend(n);d.extend(n)
K=int(input())
bfs(K)
print(lunlun[K-1])

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

a = []

def dfs(x):
    if x > 3234566667:
        return
    a.append(x)
    for i in range(10):
        if abs(x % 10 - i) <= 1:
            dfs(x * 10 + i)

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

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

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

p = [None for _ in range(100)]

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

def getByKeta(n):
    for i in p[n-1]:
        for j in range(-1, 2):
          d = i % 10 + j
          if d < 0 or d > 9:
              continue

          yield i * 10 + d

for i in range(2, 11):
    p[i] = tuple(getByKeta(i))

ans = 0
for i in range(1, 11):
    if x <= len(p[i]):
        ans = p[i][x-1]
        break
    x -= len(p[i])
print(ans)

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

q = queue.Queue()

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

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

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

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

Solution (Python):
import collections
 
k = int(input())
 
li = [str(i) for i in range(1,10)]
st_li = li[:]
q = collections.deque(li)
count = 0
n = 10 ** 10
 
for i in range(1, n):
    a = q.popleft()
    num = int(a[-1])
    if num != 0:
        aa = a + str(num-1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    aa = a + str(num)
    st_li.append(aa)
    q.append(aa)
    count += 1
    if num != 9:
        aa = a + str(num+1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    if count > k+1:
        print(st_li[k - 1])
        exit(0)

Solution (Python):
import collections

k = int(input())

li = [str(i) for i in range(1,10)]
st_li = li[:]
q = collections.deque(li)
count = 0
n = 10 ** 10

for i in range(1, n):
    a = q.popleft()
    num = int(a[-1])
    if num != 0:
        aa = a + str(num-1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    aa = a + str(num)
    st_li.append(aa)
    q.append(aa)
    count += 1
    if num != 9:
        aa = a + str(num+1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    if count > k+1:
        print(st_li[k - 1])
        exit(0)

Solution (Python):
a = int(input())
last_run_dict = {0:["0"],1:["1"],2:["2"],3:["3"],4:["4"],5:["5"],6:["6"],7:["7"],8:["8"],9:["9"]}
s = 9
"""
新しい桁の数に対して前の桁の前後1の辞書から値をとってきて頭に足したものを再度格納する

"""
if a <= 9:
    print(a)
else:
    flag = False
    answer = ""
    while True:
        keta = 2
        tmp_dict = {0:[],1:[],2:[],3:[],4:[],5:[],6:[],7:[],8:[],9:[]}
        
        for i in last_run_dict[0]:
            tmp_dict[0].append("0"+i)
        for i in last_run_dict[1]:
            tmp_dict[0].append("0"+i)
        
        for i in range(1,10):
            if i != 9:
                for num in range(-1,2):
                    for j in last_run_dict[int(i)+num]:
                        tmp_dict[i].append(str(i) + j)
                        s += 1
                        if s == a:
                            flag = True
                            answer = str(i) + j
                            break
                    if flag:
                        break
            else:
                for num in range(-1,1):
                    for j in last_run_dict[int(i)+num]:
                        tmp_dict[i].append(str(i) + j)
                        s += 1
                        if s == a:
                            flag = True
                            answer = str(i) + j
                            break
                    if flag:
                        break
            if flag:
                break
        if flag:
            break
        last_run_dict = tmp_dict
    print(answer)

Solution (Python):
import queue
def main():
    k = int(input())
    q = queue.Queue()
    for i in range(1,10):
        q.put(i)
    cnt = 0
    for i in range(1,k + 1):
        cnt += 1
        val_i = q.get()
        if cnt == k:
            print(val_i)
        keta_1 = val_i % 10
        if keta_1 != 0:
            q.put(val_i * 10 + keta_1 - 1)
        q.put(val_i * 10 + keta_1)
        if keta_1 != 9:
            q.put(val_i * 10 + keta_1 + 1)


if __name__=='__main__':
    main()

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

    def dfs(value, digit, digit_max=10):
        ans.append(value)

        if digit == digit_max:
            return  

        
        for j in (-1, 0, 1):
            lsd = (value % 10) + j
            if 0 <= lsd <= 9:
                dfs(10 * value + lsd, digit + 1)

    ans = []
    for leading in range(1, 10):
        dfs(leading, 1)
    return sorted(ans)[K - 1]

print(d_lunlun_number_dfs())

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def isOK(A):
    A.sort()
    for i in range(len(A) - 1):
        if A[i] + 1 != A[i + 1]:
            return False
    return True


def func(x):
    return 1


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


def main():
    
    solve()


if __name__ == "__main__":
    main()

Solution (Python):


def min_lunlun(lmd, dnum):
    
    lst = [lmd]
    for i in range(1, dnum):
        lst.append(max(0, lst[i - 1] - 1))
    return lst


def next_lunlun(lst):
    
    
    add_d = -1
    for i in reversed(range(1, len(lst))):
        if lst[i] < 9 and lst[i - 1] >= lst[i]:
            add_d = i
            break
    lst[add_d] = lst[add_d] + 1
    for i in range(add_d + 1, len(lst)):
        lst[i] = max(lst[i - 1] - 1, 0)

    return lst



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

    if k < 10:
        print(k)
        return

    
    d = [[0 for _ in range(11)] for _ in range(10)]
    for x in range(10):
        d[x][1] = 1

    for j in range(1, 10):
        for i in range(10):
            if 0 <= i - 1:
                d[i][j + 1] += d[i - 1][j]
            if i + 1 < 10:
                d[i][j + 1] += d[i + 1][j]
            d[i][j + 1] += d[i][j]

    total = 0
    lmd = dnum = -1
    for j in range(1, 11):
        for i in range(1, 10):
            if total + d[i][j] >= k:
                prev_total = total
                lmd = i
                dnum = j
                break
            total += d[i][j]
        if lmd > 0:
            break

    lst = min_lunlun(lmd, dnum)
    for i in range(k - prev_total - 1):
        next_lunlun(lst)
    print("".join(map(str, lst)))
    

submit()

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

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

idx=0
l=list(range(1,10))

while len(l)<K:
    m=l[idx]
    for i in (-1,0,1):
        n=(m%10)+i
        if n in{-1,10}:
            continue
        tmp=m*10+n
        l.append(tmp)
    idx=idx+1

print(l[K-1])

Solution (Python):
def main():
    k = int(input())
    ary = [1,2,3,4,5,6,7,8,9]
    cnt = 9
    now = 0
    up_tmp = 0
    if k < 10:
        print(k)
        return
    while True:
        tmp = []
        for i in range(up_tmp,len(ary)):
            a_i = ary[i]
            keta_1 = int(list(str(a_i))[-1])
            if keta_1 != 0:
                cnt += 1
                now = a_i * 10 + keta_1 - 1
                tmp.append(now)

                if cnt == k:
                    print(now)
                    
                    
                    return
            cnt += 1
            now = a_i * 10 + keta_1
            tmp.append(now)
            if cnt == k:
                print(now)
                
                
                return
            if keta_1 != 9:
                cnt += 1
                now = a_i * 10 + keta_1 + 1
                tmp.append(now)

                if cnt == k:
                    print(now)
                    
                    
                    return
        up_tmp = len(ary)
        ary.extend(tmp)



if __name__=='__main__':
    main()

Solution (Python):
_,*s=range(10)
for v in s:*t,=range(v*10+max(0,v%10-1),v*10+min(10,v%10+2));s+=t*(v<4e8)
print(s[int(input())-1])

Solution (Python):
from collections import deque

k = int(input())

q = deque([])

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

count = 0

while count < k:
    p = q.popleft()
    
    rem = p % 10
    
    if rem != 0 and rem != 9:
        q.append(10*p + rem -1)
        q.append(10*p + rem)
        q.append(10*p + rem + 1)
    if rem == 0:
        q.append(10*p + rem)
        q.append(10*p + rem + 1)
    if rem == 9:
        q.append(10*p + rem -1)
        q.append(10*p + rem)
    
    count += 1

print(p)

Solution (Python):
from collections import deque


def nth_ll(k):
    if k < 10:
        return k
    queue = deque([i for i in range(1, 10)])
    cnt = 9
    while True:
        n = queue.popleft()
        first_d = n % 10
        for i in range(-1, 2):
            if first_d + i < 0 or first_d + i > 9:
                continue
            queue.append(10 * n + first_d + i)
            cnt += 1
            if cnt == k:
                return queue.pop()

print(nth_ll(int(input())))

Solution (Python):
_,*s=range(10)
for v in s:s+=[w+v*10for w in range(max(0,v%10-1),min(10,v%10+2))]*(v<4e8)
print(s[int(input())-1])

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

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

lunlun = queue.popleft()
print(lunlun)

Solution (Python):
a={0}
_,*s=range(10)
while s:
  v=s.pop()
  a|={v}
  for w in range(max(0,v%10-1),min(10,v%10+2)):
    w+=v*10
    if w<4e9:s+=w,
print(sorted(a)[int(input())])

Solution (Python):
a={0}
_,*s=range(10)
while s:
  v=s.pop()
  a|={v}
  for w in range(max(0,v%10-1),min(10,v%10+2)):
    w+=v*10
    if w<4e9:s+=w,
print(sorted(a)[int(input())])

Solution (Python):
from collections import deque


def nth_ll(k):
    if k < 10:
        return k
    queue = deque([i for i in range(1, 10)])
    cnt = 9
    while True:
        n = queue.popleft()
        for i in range(-1 if n % 10 != 0 else 0, 2 if n % 10 != 9 else 1):
            queue.append(10 * n + n % 10 + i)
            cnt += 1
            if cnt == k:
                return queue.pop()

print(nth_ll(int(input())))

Solution (Python):
from collections import deque

k=int(input())
ans=deque([1,2,3,4,5,6,7,8,9])
if k<=9:
  print(ans[k-1])
  exit()
k-=9
while True:
  x=ans.popleft()
  r=x%10
  if r==0:
    q=x*10
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()
    q+=1
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()
  elif r!=0 and r!=9:
    q=x*10+r-1
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()
    q+=1
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()
    q+=1
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()
  elif r==9:
    q=x*10-1+r
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()
    q+=1
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()

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

lunlun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 0

def generate_lunlun(n):
    last = n % 10
    if last - 1 >= 0:
        yield n * 10 + last - 1
    yield n * 10 + last
    if last + 1 < 10:
        yield n * 10 + last + 1

while len(lunlun) < k:
    for new_lunlun in generate_lunlun(lunlun[n]):
        lunlun.append(new_lunlun)
    n += 1

print(lunlun[k-1])

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

from collections import deque

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

print(x)

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


xs = [str(x) for x in range(1,10)]

def get_lunlun(xs):
    ret = []
    for x in xs:
        last = x[-1]
        if last ==  "0":
            ret.append(x+"0")
            ret.append(x+"1")
        elif last == "9":
            ret.append(x+"8")
            ret.append(x+"9")
        else:
            ret.append(x+ str(int(last)-1))
            ret.append(x+ str(int(last)))
            ret.append(x+ str(int(last)+1))
    return ret

while K > len(xs):
    K = K -  len(xs)
    xs = get_lunlun(xs)
print(xs[K-1])

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


def get_result(data):
    K = data[0]
    lunlun_num_q = deque([str(i+1) for i in range(9)])
    cnt = 9
    while cnt < K:
        tmp_num = lunlun_num_q.popleft()
        if tmp_num[-1] == '0':
            lunlun_num_q.extend([tmp_num + '0', tmp_num + '1'])
            cnt += 2
        elif tmp_num[-1] == '9':
            lunlun_num_q.extend([tmp_num + '8', tmp_num + '9'])
            cnt += 2
        else:
            last_digit = int(tmp_num[-1])
            lunlun_num_q.extend(
                [tmp_num + str(last_digit-1), tmp_num + str(last_digit),
                 tmp_num + str(last_digit+1)])
            cnt += 3

    return lunlun_num_q[-1+K-cnt]


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)

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

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

Solution (Python):
from queue import Queue

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

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

ans = 0
count = 9
while True:
    ne = Queue()
    while not q.empty():
        now = str(q.get())
        if now[-1] == '0':
            for i in range(0, 2):
                count += 1
                rep = int(now + str(i))
                if count == k:
                    ans = rep
                    break
                ne.put(rep)
        elif now[-1] == '9':
            for i in range(8, 10):
                count += 1
                rep = int(now + str(i))
                if count == k:
                    ans = rep
                    break
                ne.put(rep)
        else:
            cen = int(now[-1])
            for i in range(cen - 1, cen + 2):
                count += 1
                rep = int(now + str(i))
                if count == k:
                    ans = rep
                    break
                ne.put(rep)
        if ans != 0:
            break
    if ans != 0:
        break
    q = ne
print(ans)

Solution (Python):
K=int(input())
A=[1,2,3,4,5,6,7,8,9]
I=0
while I<=K:
    if not A[I]%10==0:
        A.append(A[I]%10+10*A[I]-1)
    A.append(A[I]%10+10*A[I])
    if not A[I]%10==9:
        A.append(A[I]%10+10*A[I]+1)
    if len(A)>=K:
      break
    I+=1
print(A[K-1])

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

from collections import deque
que = deque()

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

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[0]
    Queue.popleft()
    oneplace = x % 10

    
    if oneplace == 0: 
        pass
    else:   
        enqueue = x * 10 + (oneplace - 1)
        Queue.append(enqueue)
    
    
    enqueue = x * 10 + oneplace
    Queue.append(enqueue)

    
    if oneplace == 9:   
        pass
    else:
        enqueue = x * 10 + (oneplace + 1)
        Queue.append(enqueue)

print(x)

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

Solution (Python):


import queue
q = queue.Queue()


for i in range(1,10):
    q.put(i)
K = int(input())


for k in range(K):
    
    x =q.get()

    
    last = x % 10

    
    if last != 0:
        
        q.put(10*x + last - 1)
    
    q.put(10*x + last)
    
    if last != 9:
        
        q.put(10*x + last + 1)
print (x)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
 
K = int(input())
 
lis = []
def dfs(nowD, maxD, x):
    if nowD == maxD:
        lis.append(x)
        if len(lis) >= K:
            print(lis[K-1])
            exit()
    else:
        y = x%10
        x *= 10
        if y-1 >= 0:
            dfs(nowD+1, maxD, x+y-1)
        dfs(nowD+1, maxD, x+y)
        if y+1 <= 9:
            dfs(nowD+1, maxD, x+y+1)
 
for d in range(1, 11):
    for x in range(1, 10):
        dfs(1, d, x)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
 
K = int(input())
 
lis = deque()
def dfs(nowD, maxD, x):
    if nowD == maxD:
        lis.append(x)
        if len(lis) >= K:
            print(lis.pop())
            exit()
    else:
        y = x%10
        x *= 10
        if y-1 >= 0:
            dfs(nowD+1, maxD, x+y-1)
        dfs(nowD+1, maxD, x+y)
        if y+1 <= 9:
            dfs(nowD+1, maxD, x+y+1)
 
for d in range(1, 11):
    for x in range(1, 10):
        dfs(1, d, x)

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