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 sys import stdin
import heapq
def main():

    input = stdin.readline

    K = int(input())

    h = []
    
    for i in range(1,10):
        heapq.heappush(h,i)
    
    for i in range(K):
        ans = heapq.heappop(h)

        if ans % 10 != 0:
            heapq.heappush(h,ans * 10 + (ans % 10 - 1))
        heapq.heappush(h,ans*10 + (ans%10))
        if ans % 10 != 9:
            heapq.heappush(h,ans * 10 + (ans % 10 + 1))
    
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
runrun = []


def dfs(x):
    if x > 3234566667:
        return
    runrun.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)

runrun = sorted(runrun)
K = int(input())

print(runrun[K-1])

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

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

for i in range(K):
    temp = que[i]
    if i == K-1:
        print(que[i])
        break
    mod = temp % 10
    if mod == 0:
        que += [temp*10+(mod), temp*10+(mod)+1]
    elif temp % 10 == 9:
        que += [temp*10+(mod)-1, temp*10+(mod)]
    else:
        que += [temp*10+(mod)-1, temp*10+(mod), temp*10+(mod)+1]

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

prev_c = 'a'
while cnt < 10**6:
    c = q.popleft()
    if c != prev_c:
        cnt += 1
        
    prev_c = c
    if cnt == K:
        print(int(c))
        break
    if c[-1] != '0':
        q.append(c+str(int(c[-1])-1))
    q.append(c+str(int(c[-1])))
    if c[-1] != '9':
        q.append(c+str(int(c[-1])+1))

Solution (Python):
k = int(input())
 
table = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in table:
  if len(table) > k:
    break
  x = i % 10
  for j in range(max(0, x - 1), min(x + 2, 10)):
    table.append(i * 10 + j)


print(table[k - 1])

Solution (Python):
from queue import Queue
k = int(input())
q = Queue()
for i in range(9):
    q.put(i + 1)
for i in range(k):
    x = q.get()
    y = x % 10
    if x % 10 != 0:
        q.put(10 * x + y - 1)
    q.put(10 * x + y)
    if x % 10 != 9:
        q.put(10 * x + y + 1)
print(x)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
k = int(input())
ans = []
def bfs(que):
    finished = set()
    while que and len(ans) <= 10**5:
        x = que.popleft()
        ans.append(int(x))
        if x not in finished:
            finished.add(x)
            p = int(x[-1])
            if 1 <= p <= 8:
                que.append(x + str(p-1))
                que.append(x + str(p))
                que.append(x + str(p+1))
            elif p == 0:
                que.append(x + str(p))
                que.append(x + str(p+1))
            else:
                que.append(x + str(p-1))
                que.append(x + str(p))
que = deque([])
for i in range(1,10):
    que.append(str(i))
bfs(que)
ans.sort()
print(ans[k-1])

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


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

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

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

print(queue[0])

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

    now = d.popleft()
    if now%10 != 0:
        d.append(10 * now + now % 10 - 1)
    d.append(10 * now + now % 10)
    if now%10 != 9:
        d.append(10 * now + now % 10 + 1)
print(now)

Solution (Python):
from collections import deque

k = int(input())
q = deque(range(1, 10))
for _ in range(k):
    x = q.popleft()
    r = x % 10
    if r != 0:
        q.append(10*x + (r - 1))
    q.append(10*x+r)
    if r != 9:
        q.append(10*x + (r + 1))
print(x)

Solution (Python):
from collections import deque

K = int(input())
Q = list(range(1, 10))

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

print(Q[K-1])

Solution (Python):
from collections import deque

k = int(input())
que = deque([i for i in range(1, 10)])
i = 0
while True:
    i += 1
    num = que.popleft()
    if i == k:
        print(num)
        exit()
    if num % 10 > 0:
        que.append(num * 10 + ((num % 10) - 1))
    que.append(num * 10 + (num % 10))
    if num % 10 < 9:
        que.append(num * 10 + ((num % 10) + 1))

Solution (Python):
from collections import deque

K = int(input())
if K <= 9:
    print(K)
else:
    que = deque([9,8,7,6,5,4,3,2,1])
    count = 0

    while True:
        x = que.pop()
        count += 1
        if count == K:
            break
        if x%10 != 0:
            que.appendleft(x*10+x%10-1)
        que.appendleft(x*10+x%10)
        if x%10 != 9:
            que.appendleft(x*10+x%10+1)
    
    




            

    print(x)

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


def next_int(n):
    nums = {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]}
    return nums[n]

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

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

print(queue[0])

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

Solution (Python):
from collections import deque

K = int(input())
queue = deque(range(1, 10))

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

print(x)

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


def next_int(n):
    nums = {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]}
    return nums[n]

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

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

print(heappop(queue))

Solution (Python):
import queue

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

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

    for i in range(k):
        x = int(q.get())
        mod = x % 10

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

        if mod != 9:
            q.put(10 * x + mod + 1)

    print(x)
    
resolve()

Solution (Python):
import heapq as hq
import sys

k=int(input())
if k<10:
    print(k)

else:
    A=[1,2,3,4,5,6,7,8,9]
    hq.heapify(A)
    now=9
    while True:
        a=hq.heappop(A)
        r=a%10
        if r==0:
            for i in range(2):
                p=a*10+i
                hq.heappush(A,p)
                now+=1
                if k==now:
                    print(p)
                    sys.exit()
        elif r==9:
            for i in range(2):
                p=a*10+8+i
                hq.heappush(A,p)
                now+=1
                if k==now:
                    print(p)
                    sys.exit()
        else:
            for i in range(3):
                p=a*10+r+i-1
                hq.heappush(A,p)
                now+=1
                if k==now:
                    print(p)
                    sys.exit()

Solution (Python):
import queue

k = int(input())

q = queue.Queue()

for i in range(9):
    q.put(i + 1)

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

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


def next_int(n):
    nums = {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]}
    return nums[n]

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

for _ in range(K-1):
    now = heappop(queue)  
    
    for next_i in next_int(int(str(now)[-1])):
        heappush(queue, int(str(now)+str(next_i)))

print(heappop(queue))

Solution (Python):
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
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(10*x+x%10-1)
    d.append(10*x+x%10)
    if x%10 != 9:
        d.append(10*x+x%10+1)
print(d.popleft())

Solution (Python):
def jud(n1,n2):
	if abs(n1-int(str(n2)[0]))<=1:
		return 1
	else:
		return 0

rnrn = [[1,2,3,4,5,6,7,8,9],[10,11,12,21,22,23,32,33,34,43,44,45,54,55,56,65,66,67,76,77,78,87,88,89,98,99]]

for div in range(1,10):
	rnrn.append([])
	for i in range(len(rnrn[div])):
		y = str(rnrn[div][i])
		x = int(y[-1])
		if x-1!=-1:
			rnrn[div+1].append(int(y+str(x-1)))
		rnrn[div+1].append(int(y+str(x)))
		if x+1!=10:
			rnrn[div+1].append(int(y+str(x+1)))
		
rnrn2 = []
for i in range(len(rnrn)):
	rnrn2.extend(rnrn[i])

print(rnrn2[int(input())-1])

Solution (Python):
N = int(input())
tmp = [i for i in range(1, 10)]
ans = list(tmp)
for i in range(10):
    tmp2 = []
    for x in tmp:
        k = int(str(x)[-1])
        if k != 0:
            ans.append(10*x-1 + k)
            tmp2.append(10*x-1 + k)
        if k != 9:
            tmp2.append(10*x+1 + k)
            ans.append(10*x+1 + k)
        tmp2.append(10*x + k)
        ans.append(10*x + k)
    tmp = list(tmp2)

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

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

K = int(input())
for _ in range(K - 1):
    i = d.pop()
    if i % 10 != 0:
        d.appendleft(i * 10 + i % 10 - 1)
    d.appendleft(i * 10 + i % 10)
    if i % 10 != 9:
        d.appendleft(i * 10 + i % 10 + 1)
print(d.pop())

Solution (Python):
from collections import deque

K = int(input())

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

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

print(x)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = []
    A = [[] for j in range(10)]
    for i in range(1, 10):
        A[0].append(i)

    for i in range(1, 10):
        for x in A[i - 1]:
            y = x % 10
            if y == 0:
                A[i].append(x * 10)
                A[i].append(x * 10 + 1)
            elif y == 9:
                A[i].append(x * 10 + 9)
                A[i].append(x * 10 + 8)
            else:
                A[i].append(x * 10 + y - 1)
                A[i].append(x * 10 + y)
                A[i].append(x * 10 + y + 1)

    ans = []
    for a in A:
        for b in a:
            ans.append(b)
    ans.sort()

    print(ans[K - 1])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
k = int(input())
q = deque(range(1,10))
while k:
    k-=1
    t=q.popleft()
    if t%10 !=0 : q.append(10*t+t%10-1)
    q.append(10*t+t%10)
    if t%10 !=9 : q.append(10*t+t%10+1)

print(t)

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


def fun(h, n):
    tmp = n % 10
    if tmp != 0:
        heapq.heappush(h, 10 * n + tmp - 1)
    heapq.heappush(h, 10 * n + tmp)
    if tmp != 9:
        heapq.heappush(h, 10 * n + tmp + 1)


h = list(range(1, 10))
while K > 0:
    n = heapq.heappop(h)
    fun(h, n)
    K -= 1
else:
    print(n)

Solution (Python):
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect



import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  k= int(readline())
  l = [1,2,3,4,5,6,7,8,9]
  q = deque(l)
  x = 0
  for _ in range(k):
    x = q.popleft()
    sue = x%10
    if sue != 0:
      q.append(10*x+sue-1)
    q.append(10*x+sue)
    if sue!=9:
      q.append(10*x+sue+1)
  print(x)
if __name__ == '__main__':
  main()

Solution (Python):
import queue

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

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

num = 0
while num < K:
        emp = A.get()
        var = emp % 10
        if var != 0:
                A.put(emp*10+var-1)
        A.put(10*emp+var)
        if var != 9:
                A.put(emp*10+var+1)
        num += 1

print(emp)

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

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

if (k < 10):
    print(ans1[k - 1])
else:
    while (ite < k):
        ans2 = []
        for num in ans1:
            keta1 = num % 10
            if (keta1 == 0):
                ans2.append(num * 10)
                ite += 1
                if (ite == k):
                    break
                ans2.append(num * 10 + 1)
                ite += 1
                if (ite == k):
                    break
                
                
                
                
            elif (keta1 == 9):
                
                
                
                
                ans2.append(num * 10 + keta1 - 1)
                ite += 1
                if (ite == k):
                    break
                ans2.append(num * 10 + keta1)
                ite += 1
                if (ite == k):
                    break
            else:
                ans2.append(num * 10 + keta1 - 1)
                ite += 1
                if (ite == k):
                    break
                ans2.append(num * 10 + keta1)
                ite += 1
                if (ite == k):
                    break
                ans2.append(num * 10 + keta1 + 1)
                ite += 1
                if (ite == k):
                    break
        ans1 = ans2[:]
    print(ans2[-1])

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

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

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

from collections import deque

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

x = 0
while 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)
    k -= 1

print(x)

Solution (Python):

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

cnt = 0
while True:
    cnt += 1
    a = q.popleft()
    if a%10 > 0:
        q.append(10*a+a%10-1)
    q.append(10*a+a%10)
    if a%10 < 9:
        q.append(10*a+a%10+1)
    
    if cnt == K:
        print(a)
        exit()

Solution (Python):
import queue

K=int(input())

q=queue.Queue()
for i in range(1,10):
  q.put(i)
  
for i in range(K):
  p=q.get()
  p1=p%10
  
  if p1!=0:
    q.put(10*p+p1-1)
  q.put(10*p+p1)
  if p1!=9:
    q.put(10*p+p1+1)
    
print(p)

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

def bfs():
    from collections import deque

    que = deque()
    cnt = 1
    memo = {}
    for i in range(1, 10):
        que.append(str(i))
        memo[cnt] = str(i)
        cnt += 1
    while que:
        x = que.popleft()
        last = int(x[-1])
        if last != 0:
            que.append(x+str(last-1))
            memo[cnt] = x + str(last-1)
            cnt += 1
        que.append(x+str(last))
        memo[cnt] = x+str(last)
        cnt += 1
        if last != 9:
            que.append(x+str(last+1))
            memo[cnt] = x + str(last+1)
            cnt += 1
        if cnt > K:
            return memo

K = INT()

res = bfs()
print(res[K])

Solution (Python):
k = int(input())
l = ['1','2','3','4','5','6','7','8','9']
lf = l.copy()
sum = 9
while sum < k:
    lff = []
    for i in lf:
        if i[-1] == '0':
            lff.append(i+'0')
            lff.append(i+'1')
        elif i[-1] == '9':
            lff.append(i+'8')
            lff.append(i+'9')
        else:
            lff.append(i+str(int(i[-1])-1))
            lff.append(i+str(int(i[-1])))
            lff.append(i+str(int(i[-1])+1))
    lf = lff
    l += lff
    sum += len(lff)
print(int(l[k-1]))

Solution (Python):
from collections import deque

k = int(input())

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

num = 0

while True:
    x = q.popleft()
    num += 1
    if num == k:
        break
    y = x % 10
    if y != 0:
        q.append(10*x+y-1)
    q.append(10*x+y)
    if y != 9:
        q.append(10*x+y+1)

print(x)

Solution (Python):
from collections import deque

k = int(input())

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

for n in range(0, k):
  x = que.popleft()
  if x % 10 != 0:
    que.append(x * 10 + x % 10 - 1)
  que.append(x * 10 + x % 10)
  if x % 10 != 9:
    que.append(x * 10 + x % 10 + 1)

print(x)

Solution (Python):
K = int(input())
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):


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

def bfs():
    from collections import deque

    que = deque()
    cnt = 1
    memo = {}
    for i in range(1, 10):
        que.append(str(i))
        memo[cnt] = str(i)
        cnt += 1
    while que:
        x = que.popleft()
        last = int(x[-1])
        if last != 0:
            que.append(x+str(last-1))
            memo[cnt] = x + str(last-1)
            cnt += 1
        que.append(x+str(last))
        memo[cnt] = x+str(last)
        cnt += 1
        if last != 9:
            que.append(x+str(last+1))
            memo[cnt] = x + str(last+1)
            cnt += 1
        if cnt > K:
            return memo

K = INT()

res = bfs()
print(res[K])

Solution (Python):
import queue

K = int(input())
q = queue.Queue()
for i in range(1, 10):
    q.put(i)
ans = 1
for _ in range(K):
    ans = q.get()
    if ans % 10 != 0:
        q.put(ans * 10 + ans % 10 - 1)
    q.put(ans * 10 + ans % 10)
    if ans % 10 != 9:
        q.put(ans * 10 + ans % 10 + 1)

print(ans)

Solution (Python):
import math
import random
import sys
import heapq
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, UserString
from functools import lru_cache, cmp_to_key
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)

sys.setrecursionlimit(10**7)
input = sys.stdin.readline
MAX_INT = 2**62-1


def main():
    k = int(input())
    queue = deque(list(range(1,10)))
    x = 0
    while k > 0:
        
        k -= 1
        x = queue.popleft()
        tail = x % 10
        if x % 10 != 0:
            queue.append(10*x + tail - 1)
        queue.append(10*x + tail)
        if x % 10 != 9:
            queue.append(10*x + tail + 1)
    print(x)

    

if __name__ == "__main__":
    main()

Solution (Python):
K = int(input())
table = [n + 1 for n in range(9)]
for i in table:
    if len(table) > K:
        break
    x = i % 10
    for j in range(max(0, x - 1), min(x + 2, 10)):
        table.append(i * 10 + j)
print(table[K - 1])

Solution (Python):
from copy import copy
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappush, heappop
setrecursionlimit(1000000)


INF = int(1e10)

def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    K = int(input())

    heap = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    heapify(heap)
    count = 0
    while True:
        count += 1
        v = heappop(heap)
        if v % 10 != 0:
            heappush(heap, 10 * v + (v % 10) - 1)
        heappush(heap, 10 * v + (v % 10))
        if v % 10 != 9:
            heappush(heap, 10 * v + (v % 10) + 1)

        if count == K:
            print(v)
            exit()

if __name__ == '__main__':
    main()

Solution (Python):
import math as m

def is_lunlun(n):
    d=int(m.log10(n))

    for i in range(d):
        q = n // (10**(d-i))
        r = n % 10**(d-i)
        if i == 0:
            q_pre = q
        
        if abs(q_pre-q) >1:
            return False
        if i == d-1:
            if abs(r-q) > 1:
                return False
        n=r
        q_pre=q
    return True

K=int(input())

tbl = [[0]*10 for _ in range(10)]
accum = [[0]*10 for _ in range(10)]
cnt = 0
i=0
j=0
for j in range(10):
    if cnt >= K:
        break

    for i in range(10):
        if j == 0:
            tbl[i][j] = 1
        else:
            if i == 0:
                tbl[i][j] = tbl[i][j-1] + tbl[i+1][j-1]
            elif i==9:
                tbl[i][j] = tbl[i-1][j-1] + tbl[i][j-1]
            else:
                tbl[i][j] = tbl[i-1][j-1] + tbl[i][j-1] + tbl[i+1][j-1]

        if i != 0:
            cnt += tbl[i][j]
        accum[i][j]=cnt
        if cnt >= K:
            i_s=i
            j_s=j
            break

i=i_s
j=j_s

digit=str(i)

base=accum[i-1][j] if i>0 else accum[j-1][9]

while j > 0:
    j=j-1
    for itmp in [i-1,i,i+1]:
        if itmp < 0 or itmp >9:
            continue
        base += tbl[itmp][j]
        if base >= K:
            base -= tbl[itmp][j]
            break
    digit+=str(itmp)
    i=itmp
print(digit)

Solution (Python):
K = int(input())
lun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
cnt = 0

while(len(lun) < K):
  target = lun[cnt]
  num = target % 10
  if num != 0:
      lun.append(target * 10 + num - 1)
  lun.append(target * 10 + num)
  if num != 9:
      lun.append(target * 10 + num + 1)
  cnt += 1

print(lun[K-1])

Solution (Python):
K = int(input())
A = [1,2,3,4,5,6,7,8,9]
for i in range(len(A)):
    if A[i] != 9:
        for j in range(-1,2):
            a = int(str(A[i]) + str(A[i]+j))
            A.append(a)
    else:
        A.append(98)
        A.append(99)
A.append(100)
A.append(101)
L1 = 10
L2 = len(A.copy())
for i in range(8):
    for i in range(L1,L2):
        B = A[i]
        if B % 10 == 0:
            A.append(int(str(B) + '0'))
            A.append(int(str(B) + '1'))
        elif B % 10 == 9:
            A.append(int(str(B) + '8'))
            A.append(int(str(B) + '9'))
        else:
            for j in range(-1, 2):
                a = int(str(B) + str((B % 10) + j))
                A.append(a)
    L1 = L2
    L2 = len(A.copy())
print(A[K-1])

Solution (Python):
def add(n):
    l = []
    if(n%10 == 0):
        l.append(n*10)
        l.append(n*10+1)
    elif(n%10 == 9):
        l.append(n*10+8)
        l.append(n*10+9)
    else:
        l.append(n*10+n%10-1)
        l.append(n*10+n%10)
        l.append(n*10+n%10+1)
    return l
k = int(input())
list = [1,2,3,4,5,6,7,8,9]
i = 0
while(len(list)<k):
    list += add(list[i])
    i += 1
print(list[k-1])

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

q = [1,2,3,4,5,6,7,8,9]
i = 0
n = 9
while n < K:
    x = q[i]
    m = x % 10
    if m > 0:
        q.append(x * 10 + m - 1)
        n += 1
    q.append(x * 10 + m)
    n += 1
    if m < 9:
        q.append(x * 10 + m + 1)
        n += 1
    i += 1
print(q[K-1])

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

Solution (Python):
import queue
K = int(input())
number = queue.Queue()
number_list = list()
for i in range(1, 10):
    number.put(i)
    number_list.append(i)
vector = [-1, 0, 1]
while len(number_list) <= K:
    n = number.get()
    amari = n % 10
    for v in vector:
        dn = amari + v
        N = n * 10 + dn
        if 0 <= dn <= 9:
            number.put(N)
            number_list.append(N)

print(number_list[K-1])

Solution (Python):
from collections import deque

K = int(input())
q = deque([9,8,7,6,5,4,3,2,1])
while K>1:
    a = q.pop()
    if a % 10 != 0:
        q.appendleft(10*a + ((a%10)-1))
    q.appendleft(10*a + a%10)
    if a % 10 != 9:
        q.appendleft(10*a + ((a%10)+1))
    K -= 1

print(q.pop())

Solution (Python):
from collections import deque

K = int(input())
q = deque(list(range(1, 10)))
ans = 0
for _ in range(K):
  ans = q.popleft()
  if ans % 10 != 0:
    q.append(ans*10+ans%10-1)
  q.append(ans*10+ans%10)
  if ans % 10 != 9:
    q.append(ans*10+ans%10+1)
print(ans)

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


from collections import deque

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

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

print(tmp)

Solution (Python):
from queue import Queue


def solve():

    K = int(input())

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


if __name__ == "__main__":
    solve()

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

for i in range(1,10):
    lunlun.append(i)
for i in lunlun:
    if len(lunlun)>K:
        break
    x = i % 10
    for j in range(max(0,x-1), min(x+2,10)):
        lunlun.append(i*10+j)
 
print(lunlun[K-1])

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

    val = 0
    hits = 0
    hit_tails = {}
    while hits < k:
        val += 1
        if len(str(val)) == 1:
            hits += 1
            hit_tails[val] = int(str(val)[-1])
            
            pass
        else:
            lst = list(map(int, str(val)))
            
            for i in range(len(lst) - 1):
                if lst[i] > lst[i+1] + 1:
                    lst[i+1] = lst[i] - 2
                    if(i < len(lst) - 2):
                        lst[i+2:] = [9] * len(lst[i+2:])
                    val = int(''.join(map(str, lst)))
                    
                    break
                elif lst[i] < lst[i+1] - 1:
                    lst[i+1:] = [9] * len(lst[i+1:])
                    val = int(''.join(map(str, lst)))
                    
                    break
                elif i == len(lst) - 2:
                    hits += 1
                    hit_tails[val] = int(str(val)[-1])
                    
                    pass

    print(val)



if __name__ == "__main__":
    d()

Solution (Python):
from collections import deque

K = int(input())

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

cnt = 1

while cnt < K:
    c = q.popleft()
    if c % 10 != 0:
        q.append(c * 10 + c % 10 - 1)
    q.append(c * 10 + c % 10)
    if c % 10 != 9:
        q.append(c * 10 + c % 10 + 1)
    cnt += 1

print(q.popleft())

Solution (Python):
K = int(input())
A = [1,2,3,4,5,6,7,8,9]
for i in range(len(A)):
    if A[i] != 9:
        for j in range(-1,2):
            a = int(str(A[i]) + str(A[i]+j))
            A.append(a)
    else:
        A.append(98)
        A.append(99)
A.append(100)
A.append(101)
L1 = len(A.copy())
for i in range(10, L1):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L2 = len(A.copy())
for i in range(8):
    for i in range(L1,L2):
        B = A[i]
        if B % 10 == 0:
            A.append(int(str(B) + '0'))
            A.append(int(str(B) + '1'))
        elif B % 10 == 9:
            A.append(int(str(B) + '8'))
            A.append(int(str(B) + '9'))
        else:
            for j in range(-1, 2):
                a = int(str(B) + str((B % 10) + j))
                A.append(a)
    L1 = L2
    L2 = len(A.copy())
print(A[K-1])