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):
k=[]
def abc(n,s,i,b):
    if b:
        if b==n:
            k.append(s)
            return
        k.append(s)
        if i==0:
            abc(n,s*10+0,0,b+1)
            abc(n,s*10+1,1,b+1)
        elif i==9:
            abc(n,s*10+9,9,b+1)
            abc(n,s*10+8,8,b+1)
        else:
            abc(n,s*10+(i-1),i-1,b+1)
            abc(n,s*10+i,i,b+1)
            abc(n,s*10+i+1,i+1,b+1)
    else:
        for i in range(1,10):
            abc(n,s*10+i,i,b+1)
abc(10,0,0,0)

k.sort()
n=int(input())
print(k[n-1])

Solution (Python):


from collections import deque
def main():
    K = int(input())
    cnt = 0
    mod = 10
    
    q = deque([])
    for i in range(1, 10):
        q.append(i)
    
    while cnt < K:
        x = q.popleft()
        cnt += 1
        if x%mod == 0:
            q.append(10*x + (x%mod))
            q.append(10*x + (x%mod)+1)
        elif x%mod == 9:
            q.append(10*x + (x%mod) -1)
            q.append(10*x + (x%mod))
        else:
            q.append(10*x + (x%mod)-1)
            q.append(10*x + (x%mod))
            q.append(10*x + (x%mod+1))
    print(x)
main()

Solution (Python):



def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    k = int(input())
    d = deque()

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

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

    while n < k:
        di = d.popleft()
        end_digit = di[-1]

        for i in range(10):
            if abs(int(end_digit) - i) <= 1:
                new_di = di + str(i)
                ans.append(new_di)
                d.append(new_di)

                n += 1

    print(ans[k - 1])


if __name__ == '__main__':
    main()

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


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

Solution (Python):
from heapq import heapify,heappop,heappush
def next_num(n):
    if n==0:
        return[0,1]
    elif n==9:
        return[8,9]
    else:
        return[n-1,n,n+1]

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

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

Solution (Python):
from heapq import heapify,heappop,heappush
def next_num(n):
    if n==0:
        return[0,1]
    elif n==9:
        return[8,9]
    else:
        return[n-1,n,n+1]

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

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

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

Solution (Python):

from collections import deque


def f(x):
  s=str(x) 
  y=int(s[-1]) 
  return int(s+str(y-1)) 


def g(x):
  s=str(x) 
  y=int(s[-1]) 
  return int(s+str(y)) 


def h(x):
  s=str(x) 
  y=int(s[-1]) 
  return int(s+str(y+1)) 


K=int(input())


q=deque()


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


for i in range(K-1):
  num=q.popleft() 
  if num%10!=0: 
    q.append(f(num))
    
  q.append(g(num))
  
  if num%10!=9: 
    q.append(h(num))
    
print(q.popleft())

Solution (Python):


import sys
import math
from fractions import gcd
from itertools import count, permutations, combinations, combinations_with_replacement, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint

INF = float('inf')

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
lmtx = lambda h: [list(map(int, lmis())) for _ in range(h)]
sys.setrecursionlimit(1000000000)


def lcm(a, b):
    return (a * b) // gcd(a, b)



k = ii()
d = deque()

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

x = 1

for _ in range(k):
    x = int(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(x)

Solution (Python):
from collections import deque
from math import log10

K = int(input())

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


for _ in range(K):
    v = que.popleft()
    
    d = int(log10(v)+1)
    res = v
    
    l = v % 10

    if l != 0: que.append(v*10 + l-1)
    que.append(v*10 + l)
    if l != 9: que.append(v*10 + l+1)

print(res)

Solution (Python):

k=int(input())

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

def lunlun_generate(p):
    last=p%10
    if last-1>=0:
        yield p*10+last-1
    yield p*10+last
    if last+1<=9:
        yield p*10+last+1


p=0
while len(lunlun)<k:
    for new_lunlun in lunlun_generate(lunlun[p]):
        lunlun.append(new_lunlun)
    p+=1
    
print(lunlun[k-1])

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

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

Solution (Python):
import queue
k = int(input())
q = queue.Queue()
cnt = 0
for i in range(1,10):
    q.put(i)
while True:
    a = q.get()
    cnt += 1
    if cnt == k:
        print(a)
        break
    else:
        s = a%10
        if s != 0:
            q.put(10*a + s-1)
        q.put(10*a + s)
        if s != 9:
            q.put(10*a + s+1)

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

Solution (Python):
import queue

K = int(input())

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

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

Solution (Python):
lunnum = [None for i in range(100)]
lunnum[1] = (1, 2, 3, 4, 5, 6, 7, 8, 9)

def gen_keta(x):
    for y in lunnum[x-1]:
        r = y % 10
        if r > 0:
            yield 10*y + (r-1)
        yield 10*y + r
        if r < 9:
            yield 10*y + (r+1)

for i in range(2,11):
    lunnum[i] = tuple(gen_keta(i))

def ans(x):
    n = 1
    while True:
        if x <= len(lunnum[n]):
            return lunnum[n][x-1]
        x -= len(lunnum[n])
        n += 1

k = int(input())
print(ans(k))

Solution (Python):
def f(N): 
    k = len(N)
    dp = [[[[0 for _ in range(10)] for _ in range(2)] for _ in range(2)] for _ in range(k+1)]
    for j in range(10):
        dp[1][0][0][j]=(j==int(N[0]))
        dp[1][0][1][j]=0
        dp[1][1][0][j]=(j<int(N[0]))
        dp[1][1][1][j]=0
    for i in range(2,k+1):
        for j in range(10):
            for m in range(10):
                dp[i][0][1][j] += (dp[i-1][0][0][m]+dp[i-1][0][1][m])*(abs(m-j)<=1)*(j==int(N[i-1]))
            dp[i][1][0][j]=1
            for m in range(10):
                dp[i][1][1][j] += (dp[i-1][0][0][m]+dp[i-1][0][1][m])*(abs(m-j)<=1)*(j<int(N[i-1]))\
                                    +dp[i-1][1][1][m]*(abs(m-j)<=1)
            for m in range(1,10):
                dp[i][1][1][j] += dp[i-1][1][0][m]*(abs(m-j)<=1)
    cnt = 0
    for j in range(10):
        cnt += dp[k][0][0][j]+dp[k][0][1][j]+dp[k][1][0][j]+dp[k][1][1][j]
    return cnt-1
K = int(input())
low = 0
high = 4*10**9
while high-low>1:
    mid = (high+low)//2
    n = f(str(mid))
    if n<K:
        low = mid
    elif n>=K:
        high = mid
print(high)

Solution (Python):
from collections import deque

max_int=int(input().rstrip())

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

for i in range(max_int):
    int_i = q.popleft()
    i_mod10 = int_i%10 

    if i_mod10==0:
        q.append(10*int_i+i_mod10)
        q.append(10*int_i+i_mod10+1)
    elif i_mod10==9:
        q.append(10*int_i+i_mod10-1)
        q.append(10*int_i+i_mod10)
    else:
        q.append(10*int_i+i_mod10-1)
        q.append(10*int_i+i_mod10)
        q.append(10*int_i+i_mod10+1)
print(int_i)

Solution (Python):

import sys
import copy
from collections import deque

def main():

    k=int(input())
    l = list(map(str, range(1, 10)))
    
    for i in range(k):
        t = l[i][-1]
        
        if t =='0':
            l.append(l[i] + '0')
            l.append(l[i] + '1')
            

        elif t =='9':
            l.append(l[i]+'8')
            l.append(l[i]+'9')

        else:
            for j in range(-1, 2):
                l.append(l[i]+str(int(t)+j))
    
    print(sorted(map(int,l))[k-1])

main()

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

print(a)

Solution (Python):
from collections import deque as dq
d=dq([1,2,3,4,5,6,7,8,9])
k=int(input())
for i in range(k):
  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(x)

Solution (Python):


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

  import copy

  ss = ["1","2","3","4","5","6","7","8","9"]
  ss2 = []
  ss3 = ss

  nx = {"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"],
  }

  i=0
  while i<K:
    for s in ss:
      nxi = nx[s[-1]]
      ss2 += [s+n for n in nxi]
      i+=len(nxi)
    ss = copy.deepcopy(ss2)
    ss3 += ss
    ss2 = []

  print(int(ss3[K-1]))
main()

Solution (Python):
k = int(input())
ans = [1,2,3,4,5,6,7,8,9]
now = 0
for i in ans:
  if now == 100000:
    break
  x = int(str(i)[-1])
  for j in range(max(0,x-1),min(x+2,10)):
    mini_ans = i * 10 + j
    ans.append(mini_ans)
    now += 1
print(ans[k-1])

Solution (Python):
k=int(input())
l=list(map(str,range(1,10)))
for i in range(k):
    x=l[i][-1]
    if x=='0':
        l.append(l[i]+x)
        l.append(l[i]+'1')
    elif x=='9':
        l.append(l[i]+'8')
        l.append(l[i]+x)
    else:
        n=int(x)
        l.append(l[i]+str(n-1))
        l.append(l[i]+x)
        l.append(l[i]+str(n+1))
print(sorted(map(int,l))[k-1])

Solution (Python):
import queue


K = int(input())


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

for i in range(1, K+2):
    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)
    if i == K:
        print(x)

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

b = [[i-1,i,i+1]for i in range(0,10)]
b = [[j for j in i if j >= 0 and j < 10]for i in b]

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

for i in c:
  istr = str(i)
  for k in b[int(istr[-1])]:
    n = i*10 + k
    c.append(n)
  if len(c) >= a:
    break

print(c[a-1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


k = I()
dq = deque([i for i in range(1, 10)])
for i in range(k):
    x = dq.popleft()
    k = x % 10
    if k:
        dq += [x * 10 + k - 1]
    dq += [x * 10 + k]
    if k != 9:
        dq += [x * 10 + k + 1]


print(x)

Solution (Python):
if True:
    n = int(input())
else:
    n = 100000;
    


count =0
list_old = [1,2,3,4,5,6,7,8,9]
count = len(list_old)
if count >= n:
    print(list_old[n-1])
    exit()

while(count < n):
    list_new = []
    keta = len(str(list_old[0]))
    
    
    for num in list_old:
        str_num = str(num)
        last_num = int(str_num[len(str_num) - 1]);
        
        
        
        if last_num == 0:
            list_new.append(num*10 + last_num)
            list_new.append(num*10 + 1)
        elif last_num == 9:
            list_new.append(num*10 + 8)
            list_new.append(num*10 + last_num)
        else:
            list_new.append(num*10 + last_num-1)
            list_new.append(num*10 + last_num)
            list_new.append(num*10 + last_num+1)
    
    
    if count + len(list_new) < n:
        list_old = list_new
        count += len(list_old)
    else:
        print(list_new[n-count-1])
        break

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

ll_list = []

def ll(d, v):
  if d==10:
    return
  
  r = v%10
  v = v*10
  
  for i in (-1, 0, 1):
    if r+i>=0 and r+i<=9:
      ll(d+1, v+r+i)
      ll_list.append(v+r+i)
      
for i in range(1, 10):
  r = i%10
  v = i*10
    
  ll_list.append(i)
  for j in (-1, 0, 1):
    if r+j>=0 and r+j<=9:
      ll(1, v+r+j)
      ll_list.append(v+r+j)
      
      
ll_list.sort()
print(ll_list[k-1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

def check(a):
    for l in range(len(a) - 1):
        if not -1 <= a[l] - a[l + 1] <= 1:
            return False
    return True

x = [0]
k = I()
ret = 0
j = len(x) - 1
while True:
    if x == [9] * len(x):
        x = [1] + [0] * len(x)
        ret += 1
        j = len(x) - 1
        if ret == k:
            print(''.join([str(m) for m in x]))
            exit()
    if j and (x[j - 1] + 1 == x[j] or x[j] == 9):
        j -= 1
        continue
    x[j] += 1
    for n in range(j + 1, len(x)):
        x[n] = x[n - 1] - 1 if x[n - 1] else 0
    j = len(x) - 1
    ret += 1
    if ret == k:
        print(''.join([str(m) for m in x]))
        exit()

Solution (Python):
k = int(input())
num = 0
for _ in range(k):
  num += 1
  digit = [int(digit) for digit in str(num)]
  len_digit = len(digit)
  flag = False
  for i in range(1, len_digit):
    
    
    if digit[-i] == 10:
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] > digit[-i-1] + 1:
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] < digit[-i-1] - 1:
      digit[-i] = -1
  if digit[0] == 10:
    num = 10 ** len_digit
  else:
    for i in range(1, len_digit):
      if digit[i] == -1:
        for j in range(i, len_digit):
          digit[j] = max(digit[j-1] - 1, 0)
        break
    num = 0
    for d in digit:
      num = num * 10 + d
print(num)

Solution (Python):
import heapq
 
heap=[]
N = int(input())
for i in range(1,10):
  heapq.heappush(heap,i)
for i in range(N):
  x = heapq.heappop(heap)
  if x%10!=0:
    heapq.heappush(heap,10*x+(x%10)-1)
  heapq.heappush(heap,10*x+(x%10))
  if x%10!=9:
    heapq.heappush(heap,10*x+(x%10)+1)
  
print(x)

Solution (Python):
n=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)
while n!=1:
    x=q.get();k=x%10
    for i in range(max(0,k-1),min(10,k+2)) :
        q.put(10*x+i)
    n-=1
print(q.get())

Solution (Python):
n=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)
while n!=1:
    x=q.get();k=x%10
    for i in range(max(0,k-1),min(10,k+2)) :
        q.put(10*x+i)
    n-=1
print(q.get())

Solution (Python):
n=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)
while n!=1:
    x=q.get();k=x%10
    for j in [10*x+i for i in range(max(0,k-1),min(10,k+2))] :
        q.put(j)
    n-=1
print(q.get())

Solution (Python):
n=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)
while n!=0:
    x=q.get();k=x%10
    for j in [10*x+i for i in range(max(0,k-1),min(10,k+2))] :
        q.put(j)
    n-=1
print(x)

Solution (Python):
import math
import string
import collections
from collections import Counter
from collections import deque


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor



dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]






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


N = int(input())
dist = []
for i in range(1, 10):
    func(1, i, dist)
    
ans = sorted(dist)
print(ans[N-1])

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):
k=int(input())
a=list(range(1, 10))
b=[]
n=int(len(a))
x=k
while x>n:
  x-=n
  for i in range(n):
    for l in range(3):
      c=(a[i]%10)-1+l
      if 0<=c<=9:
        a.append((a[i]*10)+c)
  del a[0:n]
print(a[x-1])

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])
        break
    else:
        k -= len(a)
        old = a.copy()
        a = []
        for i in old:
            for j in [-1,0,1]:
                d = int(str(i)[-1])+j
                if (d<0) or (d>9):
                    continue
                n = int(str(i)+str(d))
                a.append(n)

Solution (Python):
import queue
q=queue.Queue()

K=int(input())
for i in range(1,10):q.put(i)
while(not q.empty()):
    a=q.get()
    K-=1
    if K==0:
        print(a)
        exit()
    for i in range(a%10-1,a%10+1+1):
        if i<0 or i>9:continue
        q.put(a*10+i)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(K: int):

    X = set()

    def rec(keta, x):
        X.add(x)
        if keta == 10:
            return
        y = x % 10
        if 0 <= y - 1:
            rec(keta+1, x*10 + y-1)
        rec(keta+1, x*10+y)
        if y+1 <= 9:
            rec(keta+1, x*10+y+1)

    for i in range(1, 10):
        rec(1, i)
    X = sorted(X)
    print(X[K-1])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  
    solve(K)


if __name__ == '__main__':
    main()

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

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

if n <= 9:
    print(n)
else:
    count = 9
    while count<=n:
        i = query.pop(0)

        if i%10-1>=0:
            query.append(i*10+(i%10-1))
            count += 1
            if count == n:
                print(i*10+(i%10-1))
                break

        query.append(i*10+(i%10))
        count += 1
        if count == n:
            print(i*10+(i%10))
            break

        if i%10+1<=9:
            query.append(i*10+(i%10+1))
            count += 1
            if count == n:
                print(i*10+(i%10+1))
                break

Solution (Python):
import queue
k = int(input())
q = queue.Queue()
cnt = 0
for i in range(1,10):
    q.put(i)
    
while cnt < 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)
    cnt += 1
    
print(num)

Solution (Python):
import queue

S = int(input())

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

cnt = 9
num = 9
digit = 0

if S <= 9:
    print(S)
else:
    while cnt <= S:
        num = q.get()
        digit = int(str(num)[-1])
        num = num * 10

        if digit == 0:
            for i in range(2):
                cnt += 1
                if cnt == S:
                    print(num + i)
                    exit()
                else:
                    q.put(num + i)

        elif digit == 9:
            num += digit - 1
            for i in range(2):
                cnt += 1
                if cnt == S:
                    print(num + i)
                    exit()
                else:
                    q.put(num+i)
        else:
            num += digit - 1
            for i in range(3):
                cnt += 1
                if cnt == S:
                    print(num + i)
                    exit()
                else:
                    q.put(num+i)

Solution (Python):
k = int(input())
num = 0
for _ in range(k):
  num += 1
  digit = list(map(int, str(num)))
  len_digit = len(digit)
  for i in range(1, len_digit):
    if digit[-i] > min(digit[-i-1] + 1, 9):
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] < digit[-i-1] - 1:
      digit[-i] = -1
  for i in range(1, len_digit):
    if digit[i] == -1:
      for j in range(i, len_digit):
        digit[j] = max(digit[j-1] - 1, 0)
      break
  num = int(''.join(map(str, digit)))
print(num)

Solution (Python):
k = int(input())
num = 0
for _ in range(k):
  num += 1
  digit = [int(digit) for digit in str(num)]
  len_digit = len(digit)
  flag = False
  for i in range(1, len_digit):
    
    
    if digit[-i] == 10:
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] > digit[-i-1] + 1:
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] < digit[-i-1] - 1:
      digit[-i] = -1
  if digit[0] == 10:
    num = 10 ** len_digit
  else:
    for i in range(1, len_digit):
      if digit[i] == -1:
        for j in range(i, len_digit):
          digit[j] = max(digit[j-1] - 1, 0)
        break
    num = 0
    for d in digit:
      num = num * 10 + d
print(num)

Solution (Python):
def lunlun_maker(l: int) -> int:
    next_lunluns = []
    for e in l:
        nxt = e * 10
        mod = e % 10
        if 0 < mod < 9:
            next_lunluns.extend([nxt + mod - 1, nxt + mod, nxt + mod + 1])
        elif mod == 0:
            next_lunluns.extend([nxt, nxt + 1])
        elif mod == 9:
            next_lunluns.extend([nxt + 8, nxt + 9])
    return next_lunluns


def get_lunlun(num: int) -> int:
    lunluns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    counter = len(lunluns)
    counter_tmp = counter
    while counter < num:
        lunluns = lunlun_maker(lunluns)
        counter_tmp = counter
        counter += len(lunluns)
    return lunluns[num - counter_tmp - 1]


K = int(input())
print(get_lunlun(K))

Solution (Python):
k = int(input())
lis = [1,2,3,4,5,6,7,8,9]
i=0
while len(lis) < k:
	m = lis[i]%10
	if m != 0:
		lis.append(int(str(lis[i])+str(m-1)))
	lis.append(int(str(lis[i])+str(m)))
	if m!= 9:
		lis.append(int(str(lis[i])+str(m+1)))
	i+=1
print(lis[k-1])

Solution (Python):
K = int(input())
from collections import deque
que = deque()
for i in range(1,10):
  que.append(i)
  
while K > 0:
  a = que.popleft()
  b = a % 10
  if b == 0:
    que.append(a*10 + b)
    que.append(a*10 + b+1)
  elif b == 9:
    que.append(a*10 + b-1)
    que.append(a*10 + b)
  else:
    que.append(a*10 + b-1)
    que.append(a*10 + b)
    que.append(a*10 + b+1)
  K -= 1
print(a)

Solution (Python):

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def lunlun_num(N):
    N = str(N)
    L = len(N)

    dp = [[0]*10 for j in range(L)]
    for j in range(1,int(N[0])):
        dp[0][j] = 1

    flag = True
    for i in range(L-1):
        d = int(N[i+1])
        b = int(N[i])
        
        dp[i+1][0] += dp[i][0] + dp[i][1]
        dp[i+1][9] += dp[i][8] + dp[i][9]
        for j in range(1,9):
            dp[i+1][j] += dp[i][j-1] + dp[i][j] + dp[i][j+1]
        for j in range(1,10):
            dp[i+1][j] += 1

        if flag:
            if d < b - 1:
                flag = False
            elif d <= b + 1:
                for j in range(max(0, b-1),d):
                    dp[i+1][j] += 1
            else:
                for j in range(max(0, b-1),b+2):
                    dp[i+1][j] += 1
                    flag = False

    return sum(dp[L-1]) + 1 if flag else sum(dp[L-1])


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

    
    left = 0
    right = 10**10
    while left + 1 < right:
        x = (left + right) // 2

        if lunlun_num(x) >= K:
            right = x
        else:
            left = x
    
    print(right)


if __name__ == "__main__":
    main()

Solution (Python):
import queue

k = int(input())
q = queue.Queue()
for l in range(10)[1:]:
    q.put(l)
if k < 10:
    print(q.queue[k-1])
    exit()
k -= 9
for l in range(k):
    dequeued = q.get()
    mod = dequeued % 10
    if mod != 0:
        q.put(dequeued * 10 + mod - 1)
    q.put(dequeued * 10 + mod)
    if mod != 9:
        q.put(dequeued * 10 + mod + 1)
print(q.queue[8])

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

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

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

k -= 9

while k > 0:
    a = q.popleft()
    b = a % 10
    if b == 0:
        q.append(10*a)
        q.append(10*a + 1)
        k -= 2
    elif b != 0 and b != 9:
        q.append(10*a + (b - 1))
        q.append(10*a + b)
        q.append(10*a + (b + 1))
        k -= 3
    else:
        q.append(10*a + 8)
        q.append(10*a + 9)
        k -= 2

if k == -2:
    print(q[-3])
elif k == -1:
    print(q[-2])
elif k == 0:
    print(q[-1])

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(1000000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def is_lunlun(n):
    s = str(n)
    for i in range(len(s)-1):
        if abs(int(s[i])-int(s[i+1])) > 1:
            return False
    return True

def slv(k):
    if k <= 9:
        return k
    lunlun = list(range(1, 10))
    q = deque(lunlun)

    while True:
        n = q.popleft()
        for i in (-1, 0, 1):
            d = n % 10
            if 0 <= d + i <= 9:
                l = n * 10 + d+i
                q.append(l)
                lunlun.append(l)
                if len(lunlun) == k:
                    return lunlun[-1]




def main():
    K = read_int()
    print(slv(K))



if __name__ == '__main__':
    main()

Solution (Python):



from collections import deque,Counter









k = int(input())

que = deque(range(1,10)) 
for _ in range(k):
    tmp = que.popleft()
    if tmp % 10 !=0:
        val = tmp*10 + (tmp%10) - 1
        que.append(val)
    val = tmp*10 + (tmp%10)
    que.append(val)
    if tmp%10 != 9:
        val = tmp*10 + (tmp%10) + 1
        que.append(val)

ans = tmp
print(ans)

Solution (Python):
from collections import deque
k = int(input())
d = deque()
for i in range(1, 10):
  d.append(i)
cc = 0
while cc < k:
  num = d.popleft()
  if num%10 == 0:
    d.append(10*num)
    d.append(10*num + 1)
  elif num%10 == 9:
    d.append(10*num+8)
    d.append(10*num+9)
  else:
    d.append(10*num+num%10-1)
    d.append(10*num+num%10)
    d.append(10*num+num%10+1)
  cc += 1
print(num)

Solution (Python):
import queue

K = int(input())

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

for _ in range(K):
    now_lunlun = que_lunlun.get()
    
    first_digit = now_lunlun % 10
    if first_digit != 0:
        que_lunlun.put(now_lunlun*10 + first_digit-1)
    
    que_lunlun.put(now_lunlun*10 + first_digit)

    if first_digit != 9:
        que_lunlun.put(now_lunlun*10 + first_digit+1)
    
print(now_lunlun)

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

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

for x in a:
    if k<=len(a):
        break
    
    if x%10!=0:
        a.append(10*x+(x%10)-1)
    a.append(10*x+(x%10))
    if x%10!=9:
        a.append(10*x+(x%10)+1)
        
print(a[k-1])

Solution (Python):
k = int(input())
from collections import deque
queue = deque(range(1,10)) 
count = 0
 
while count < k: 
  count += 1
  tmp = queue.popleft()
  tail = tmp % 10 
  if tail!=0:
    queue.append(tmp*10+tail-1)  
  queue.append(tmp*10+tail) 
  if tail!=9:
    queue.append(tmp*10+tail+1) 
  
print(tmp)