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
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


k = int(input())
queue = deque([str(i) for i in range(1, 10)])
ans = ""
for i in range(k):
    ans = queue.popleft() 
    if ans[-1] != "0":
        queue.append(ans + str(int(ans[-1]) - 1))
    queue.append(ans + ans[-1])
    if ans[-1] != "9":
        queue.append(ans + str(int(ans[-1]) + 1))
print(ans)

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

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

print(d.popleft())

Solution (Python):
k = int(input())
lis = [i for i in range(1,10)]
tmp = [i for i in range(1,10)]
while len(lis)<k+1:
    tmp2 = []
    for i in tmp:
        la = i%10
        if la==0:
            tmp2.append(i*10)
            tmp2.append(i*10+la+1)
        elif la==9:
            tmp2.append(i*10+la)
            tmp2.append(i*10+la-1)
        else:
            tmp2.append(i*10+la-1)
            tmp2.append(i*10+la)
            tmp2.append(i*10+la+1)
    lis.extend(tmp2)
    tmp = [i for i in tmp2]

lis.sort()

print(lis[k-1])

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline





def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))





from collections import deque

def main():
	k=II()

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

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














if __name__ == "__main__":
	main()

Solution (Python):
from queue import deque

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

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 queue import deque

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

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

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

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *













































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	K = inputInt()

	dp = []
	dp.append(["1","2","3","4","5","6","7","8","9"])
	ans = [1,2,3,4,5,6,7,8,9]

	for i in range(10):
		testcase = dp[-1]
		nextcalse = []
		for val in testcase:
			base = val[-1]
			manaka = val + base
			nextcalse.append(manaka)
			ans.append(int(manaka))

			samp = int(base)
			if samp - 1 >= 0:
				rinko = val + str(samp - 1)
				nextcalse.append(rinko)
				ans.append(int(rinko))

			if samp + 1 <= 9:
				nene = val + str(samp + 1)
				nextcalse.append(nene)
				ans.append(int(nene))
		dp.append(nextcalse)

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










def bisect_left_reverse(a, x):
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

def bisect_right_reverse(a, x):
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok





def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None




def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)




def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y




def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv



def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)



if __name__ == "__main__":
	main()

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

qu=deque(list(range(1,10)))
count=0
while True:
  x=qu.popleft()
  count+=1
  if count==k:
    print(x)
    break
  if str(x)[-1]!="0":
    qu.append(int(str(x)+str(int(str(x)[-1])-1)))
  qu.append(int(str(x)+str(x)[-1]))
  if str(x)[-1]!="9":
    qu.append(int(str(x)+str(int(str(x)[-1])+1)))

Solution (Python):
def generate(n):
    if n == 1:
        for i in range(1, 10):
            yield [i]
    else:
        for A in generate(n - 1):
            for i in range(10):
                if abs(A[-1] - i) <= 1:
                    yield A + [i]


L = []
for n in range(1, 11):
    for A in generate(n):
        L.append(int(''.join([str(a) for a in A])))
k = int(input())
print(L[k - 1])

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

Solution (Python):
from statistics import median


from fractions import gcd
from itertools import combinations 
from collections import deque
from collections import defaultdict
import bisect










import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
k = I()
que = deque([])
for i in range(1,10):
    que.append(i)
if k <= 9:
    print(que[k-1])
    exit()
while que:
    num = que.popleft()
    if k == 1:
        print(num)
        exit()
    lo = num%10
    if 0 <= lo - 1:
        que.append(num*10 + lo-1)
    que.append(num*10 + lo)
    if lo + 1 <= 9:
        que.append(num*10 + lo + 1)
    k -= 1

Solution (Python):
def lunlun(K,S):
    if len(S) >= K:
        S.sort()
        print(S[K-1])
        return

    for a in range(len(S)):
        i = S[a]
        rem = i%10
        n = 10*i + rem

        if rem == 9:
            S.append(n)
            S.append(n-1)
        elif rem == 0:
            S.append(n)
            S.append(n+1)
        else:
            S.append(n)
            S.append(n+1)
            S.append(n-1)
    lunlun(K,list(set(S)))


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

lunlun(K,S)

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

if k <= 9:
    print(k)
k -= 9

lst = list(range(1, 10))
while k > 0:
    new = []
    for num in lst:
        amari = num % 10
        if amari == 0:
            new.append(num*10)
            new.append(num*10+1)
        elif amari == 9:
            new.append(num*10+8)
            new.append(num*10+9)
        else:
            new.append(num*10+(amari-1))
            new.append(num*10+amari)
            new.append(num*10+(amari+1))
    if len(new) >= k:
        print(new[k-1])
        exit()
    else:
        k -= len(new)
        lst = new

Solution (Python):
K = int(input())
S = set([1,2,3,4,5,6,7,8,9])
prev = set([1,2,3,4,5,6,7,8,9])

while len(S) < K:
    temp = set([])
    for e in prev:
        if e%10 == 0:
            temp.add(e*10)
            temp.add(e*10+1)
        elif e%10 == 9:
            temp.add(e*10+8)
            temp.add(e*10+9)
        else:
            temp.add(e*10+e%10-1)
            temp.add(e*10+e%10)
            temp.add(e*10+e%10+1)
    prev = temp
    S = S|temp
print(sorted(list(S))[K-1])

Solution (Python):
from heapq import heapify, heappush, heappop

K = int(input())

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

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

for _ in range(K-1):
    lli = heappop(ll)
    next_nums = next_num(lli)
    for ni in next_nums:
        heappush(ll, lli*10+ni)

ans = ll[0]
print(ans)

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

a = list(range(1, 10))
i = 0
while len(a) < K:
  A = []
  for j in range(3):
    n = str(a[i])
    if j == 0 and int(n[-1]) - 1 >= 0:
      A.append(int(n + str(int(n[-1]) - 1)))
    elif j == 1:
      A.append(int(n + n[-1]))
    elif j == 2 and int(n[-1]) + 1 < 10:
      A.append(int(n + str(int(n[-1]) + 1)))
  a += A
  i += 1
print(a[K-1])

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()

k = int(input())

lunlun_num = []

def dfs(s):
    if len(s) > 10:
        return
    s = list(s)
    s_last = int(s[-1])
    for i in range(s_last - 1, s_last + 2):
        if 0 <= i <= 9:
            s.append(str(i))
            lunlun_num.append(int("".join(s)))
            dfs("".join(s))
            s.pop()

for i in range(1, 10):
    dfs(str(i))
    lunlun_num.append(int(i))

lunlun_num.sort()


print(lunlun_num[k - 1])

Solution (Python):
from collections import deque

k = int(input())

LL = [i for i in range(1, 10)]
LL = deque(LL)
for j in range(k):
    num = LL.popleft()
    amari = num % 10
    kouho = [amari - 1, amari, amari + 1]
    for nn in kouho:
        if nn >= 0 and nn < 10:
            LL.append(10 * num + nn)
print(num)

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

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

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

cnt = 0
    
while q:
    v = q.popleft()
    cnt += 1
    
    if cnt==K:
        print(v)
        exit()
    
    for i in range(max(0, v%10-1), min(9, v%10+1)+1):
        q.append(10*v+i)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
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(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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 queue

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

counter = 0
for i in range(9):
    q.put(i+1)
while counter < k:
    n = q.get()
    counter += 1
    mod = n % 10
    if mod != 0:
        q.put(10*n+mod-1)
    q.put(10*n+mod)
    if mod != 9:
        q.put(10*n+mod+1)
print(n)

Solution (Python):
K = int(input())
A = [list(range(1, 10))]
cnt = 0

while cnt < K * 2:
    B = []
    for a in A[-1]:
        r = a % 10
        a *= 10
        for i in range(max(0, r - 1), min(r + 2, 10)):
            B.append(a + i)
    cnt += len(B)
    A.append(B)

A = [a for B in A for a in B]
A.sort()
print(A[K - 1])

Solution (Python):
import sys
from io import StringIO
import unittest


def recursive(base, lunluns):

    lunluns.append(base)

    
    if len(base) > 10 or len(base) > 9 and int(base[0]) > 3:
        return
    target = int(base[-1])

    if target is 0:
        add_num = ["0", "1"]
    elif target is 9:
        add_num = ["8", "9"]
    else:
        add_num = [str(target - 1), str(target), str(target+1)]

    for i in add_num:
        recursive("".join(base + str(i)), lunluns)


def resolve():

    k = int(input())

    
    lunluns = ["0"]

    
    for i in ["1", "2", "3", "4", "5", "6", "7", "8", "9"]:
        recursive(i, lunluns)

    lunluns = list(map(int, lunluns))
    lunluns.sort()

    print(lunluns[k])


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """15"""
        output = """23"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """1"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """13"""
        output = """21"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """100000"""
        output = """3234566667"""
        self.assertIO(input, output)


if __name__ == "__main__":
    
    resolve()

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

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

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

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

Solution (Python):
from collections import deque

K=int(input())

num_str=[str(i) for i in range(10)]

numbers=deque()
for i in range(1,len(num_str)):
    numbers.append((i,num_str[i]))

times=0
while numbers:
    times+=1
    if times==K:
        break
    else:
        num=numbers.popleft()
        for i in range(3):
            index=num[0]-1+i
            if index>=0 and index<10:
                numbers.append((num[0]-1+i,num[1]+num_str[num[0]-1+i]))


print(numbers.popleft()[1])

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

Q = deque([1,2,3,4,5,6,7,8,9])
a = 0
for i in range(N):
  a = Q.popleft()
  if a%10 > 0:
    Q.append(a*10 + (a%10 -1))
  Q.append(a*10 + a%10)
  if a%10 < 9:
    Q.append(a*10 + (a%10 +1))

print(a)

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

Q = deque([1,2,3,4,5,6,7,8,9])
a = 0
for i in range(N):
  a = Q.popleft()
  if a%10 > 0:
    Q.append(a*10 + (a%10 -1))
  Q.append(a*10 + a%10)
  if a%10 < 9:
    Q.append(a*10 + (a%10 +1))

print(a)

Solution (Python):
import sys


from queue import Queue


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

    queue = Queue()
    for i in [ 1, 2, 3, 4, 5, 6, 7, 8, 9, ]:
        queue.put(i)

    for i in range(1, K+1):
        lunlun = queue.get()
        digit = lunlun % 10

        new_lunluns = []
        
        if digit == 0:
            new_lunluns.append(lunlun * 10 + digit)
            new_lunluns.append(lunlun * 10 + digit + 1)
        elif digit == 9:
            new_lunluns.append(lunlun * 10 + digit - 1)
            new_lunluns.append(lunlun * 10 + digit)
        else:
            new_lunluns.append(lunlun * 10 + digit - 1)
            new_lunluns.append(lunlun * 10 + digit)
            new_lunluns.append(lunlun * 10 + digit + 1)

        for new_lunlun in new_lunluns:
            queue.put(new_lunlun)

    print(lunlun)
    return 0

if __name__ == '__main__':
    sys.exit(main())

Solution (Python):
import heapq

K = int(input())
q = [i for i in range(1, 10)]
ans = []
for i in range(K):
  n = heapq.heappop(q)
  ans += [n]
  stn = str(n)
  last = (stn[-1])
  cand1 = int(str(n) + last)
  heapq.heappush(q, cand1)
  if 0 < int(last):
    cand2 = int(str(n) + str(int(last)-1))
    heapq.heappush(q, cand2)
  if int(last) < 9:
    cand3 = int(str(n) + str(int(last)+1))
    heapq.heappush(q, cand3)

print(ans[-1])

Solution (Python):

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

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

main()

Solution (Python):
def dfs(s,l):
  if s!="":
    if len(s)>10 or s[0]=="0":
      return
  if s!="":
    l.append(int(s))
  for c in "0123456789":
    if s!="":
      if abs(int(s[-1])-int(c))<=1:
        dfs(s+c,l)
    else:
      if c!="0":
        dfs(s+c,l)

k=int(input())
l=[]
dfs("",l)
l.sort()
print(l[k-1])

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

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

for i in range(k):
    l=q.pop(0)
    if l%10!=0:
        q.append(10*l+l%10-1)
    q.append(10*l+l%10)
    if l%10!=9:
        q.append(10*l+l%10+1)
    
print(l)

Solution (Python):
import sys

k=int(input())

lun=[i for i in range(1,10)]
while 1>0:
    if k <=len(lun): 
        print(lun[k-1])
        sys.exit()
    else:
        k-=len(lun)
        lunw=[]
        for i in range(len(lun)):
            if lun[i]%10!=0:
                lunw.append(lun[i]*10+lun[i]%10-1)
            lunw.append(lun[i]*10+lun[i]%10)
            if lun[i]%10!=9:
                lunw.append(lun[i]*10+lun[i]%10+1)
    lun =lunw

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue

Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  
    all = []

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

    k = int(input())
    for i in range(1, 10):
        dfs(1, i)
        
    all.sort()
    print(all[k-1])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(500000)
K = int(input())

ans_list = []
def dfs(A):
    if len(A)!=0 and int("".join(A))<=10**10:
        ans_list.append(int("".join(A)))
    elif len(A)!=0 and int("".join(A))>10**10:
        return
    if len(A)==0:
        for i in range(1, 10, 1):
            A.append(str(i))
            dfs(A)
            A.pop()
        return

    for i in range(0, 10, 1):
        if abs(int(A[-1])-i)<=1:
            A.append(str(i))
            dfs(A)
            A.pop()
    return
dfs([])
ans_list.sort()
print(ans_list[K-1])

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

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

while(1):
    if k <= len(runrun):
        print(runrun[k-1])
        break
    k -= len(runrun)
    old = []
    runrun, old = old, runrun
    for x in old:
        for i in range(-1, 2):
            d = x%10 + i
            if d < 0 or d > 9:
                continue
            nx = x*10 + d
            runrun.append(nx)

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

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

while K > len(old):
    new = []
    K -= len(old)
    for i in range(len(old)):
        tmp = old[i]
        l = tmp % 10
        if l != 0:
            new.append(tmp*10+l-1)
        new.append(tmp*10+l)
        if l != 9:
            new.append(tmp*10+l+1)
    old = new[:]



print(old[K-1])

Solution (Python):
k = int(input())
from collections import deque
lun = deque([str(n)for n in list(range(1,10))])
if k<=9:
    print(lun[k-1])
    exit()
l = 9
while l<k:
    n = lun.popleft()
    c = int(n[-1])
    if c>0:
        lun.append(n+str(c-1))
        l+=1
        if l==k:break
    lun.append(n+str(c))
    l+=1
    if l==k:break
    if c<9:
        lun.append(n+str(c+1))
        l+=1
        if l==k:break
    
print(lun[-1])

Solution (Python):
from collections import deque

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

for i in range(k-1):
    
    x = q.popleft()
    y = int(str(x)[-1])
    if y-1 >= 0:
        q.append(int(str(x)+str(y-1)))
    q.append(int(str(x)+str(x)[-1]))
    if y+1 < 10:
        q.append(int(str(x)+str(y+1)))

print(q[0])

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

class Myqueue:
  def __init__(self):
    self.queue = []
    
  def enqueue (self, item):
    self.queue.append(item)
  
  def dequeue (self):
    if len(self.queue) ==0:
      return None
    result =self.queue[0]
    del self.queue[0]
    return result

myq = Myqueue()
myq.enqueue(1)
myq.enqueue(2)
myq.enqueue(3)
myq.enqueue(4)
myq.enqueue(5)
myq.enqueue(6)
myq.enqueue(7)
myq.enqueue(8)
myq.enqueue(9)

K = 9
s = 9
if k < 10:
  None
elif k >= 10:
  while s <= k:
    x = myq.dequeue()
    I = x % 10
    if I == 0:
      myq.enqueue(x*10 + I)
      myq.enqueue(x*10 + (I+1))
      s += 2
    elif I ==9:
      myq.enqueue(x*10 + (I-1))
      myq.enqueue(x*10 + I)
      s += 2
    else:
      myq.enqueue(x*10 + (I-1))
      myq.enqueue(x*10 + I)
      myq.enqueue(x*10 + (I+1))
      s += 3

if k < 10:
  print(k)
elif s - 2 == k:
  print(myq.queue[-3])
elif s - 1 == k:
  print(myq.queue[-2])
elif s == k:
  print(myq.queue[-1])
elif s -3 == k:
  print(myq.queue[-4])

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

def dfs(num, A):
  A.append(num)

  if(len(str(num)) == 10):
    return 0

  for i in range(-1, 2):
    s = num%10 + i
    if(s >= 0 and s <= 9):
      dfs(num * 10 + s, A)

  return 0

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

n = sorted(n)

print(n[k - 1])

Solution (Python):
def main():
    runrun = {1: [1, 2, 3, 4, 5, 6, 7, 8, 9]}
    for i in range(2, 13):
        r = []
        for v in runrun[i-1]:
            num = v % 10
            for j in range(max(0, num-1), min(10, num+2)):
                r.append(v*10+j)
        runrun[i] = r

    mrunrun = []
    for _, v in runrun.items():
        mrunrun.extend(v)
    mrunrun.sort()
    k = int(input())
    print(mrunrun[k-1])


if __name__ == '__main__':
    main()

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

lun_ls = []
def change_to_num(ls):
    ls = list(map(str, ls))
    strnum = ''.join(ls)
    return int(strnum)
def lun(num):
    '''
    渡された数が上限行ってなければlun_lsに追加して、次の数で再帰呼出
    '''
    if num > 3234566667:
        return

    lun_ls.append(num)
    last = num % 10
    for nex in range(last-1, last+2):
        if 0<= nex < 10:
            new_str = str(num) + str(nex)
            new = int(new_str)
            lun(new)
            
for start in range(1,10):
    lun(start)
lun_ls.sort()
print(lun_ls[k-1])

Solution (Python):
from collections import deque

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

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

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

    if k%d!=d-1:
        X.append(k*10+(k%d)+1)

print(k)

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

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

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

def check(n,cc):
    cc += 1
    if(cc == k):
        print(n)
        sys.exit()
    return cc


for i in lun:
    new_lun = []
    for j in i:
        a = j*10
        b = j%10
        if(b != 0):
            new_lun.append(a + b - 1)
            count = check(a + b - 1,count)
        new_lun.append(a + b)
        count = check(a + b,count)
        if(b != 9):
            new_lun.append(a + b + 1)
            count = check(a + b + 1, count)
    lun.append(new_lun)