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 math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


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

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

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

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

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

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


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

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

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

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

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

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


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


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


def solve():
    K = Scanner.int()
    d = deque()
    for i in range(1, 10):
        d.append(i)
    MAX = 10 ** 5 + 100
    for i in range(MAX):
        n = d[i]
        a = int(str(n)[-1])
        if a != 0:
            d.append(n * 10 + (a - 1))
        d.append(n * 10 + a)
        if a != 9:
            d.append(n * 10 + (a + 1))
        if len(d) >= K:
            print(d[K - 1])
            return


def main():
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

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

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

for i in range(9):
    for x in list(lunlun):
        iti = int(str(x)[-1])
        l = x*10 + (iti-1)
        m = x*10 + (iti+0)
        n = x*10 + (iti+1)

        lunlun.add(m)
        if iti != 9:
            lunlun.add(n)
        if iti != 0:
            lunlun.add(l)

print(sorted(lunlun)[k-1])

Solution (Python):
from collections import deque


def solver(K):
    q = deque([i for i in range(1, 10)])

    if K <= 9:
        ans = q[K - 1]

    else:
        cnt = 9
        for i in range(1, K):
            c = q.popleft()

            if c % 10 != 0:
                q.append(c * 10 + (c % 10) - 1)
                cnt += 1
                if cnt >= K:
                    break

            q.append(c * 10 + (c % 10))
            cnt += 1
            if cnt >= K:
                break

            if c % 10 != 9:
                q.append(c * 10 + (c % 10) + 1)
                cnt += 1
                if cnt >= K:
                    break

        ans = q[-1]
    return ans


def run():
    K = int(input())
    ans = solver(K)

    print(ans)


run()

Solution (Python):
from collections import deque


def solver(K):
    q = deque([i for i in range(1, 10)])

    if K <= 9:
        ans = q[K - 1]

    else:
        cnt = 9
        for i in range(1, K):
            c = q.popleft()

            if c % 10 != 0:
                q.append(c * 10 + (c % 10) - 1)
                cnt += 1
                if cnt >= K:
                    break

            q.append(c * 10 + (c % 10))
            cnt += 1
            if cnt >= K:
                break

            if c % 10 != 9:
                q.append(c * 10 + (c % 10) + 1)
                cnt += 1
                if cnt >= K:
                    break

        ans = q[-1]
    return ans


def run():
    K = int(input())
    ans = solver(K)

    print(ans)


run()

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

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

for i in range(N-1):
  num=q.pop()
  if num%10!=0:
    q.appendleft(num*10+num%10-1)
  q.appendleft(num*10+num%10)
  if num%10!=9:
    q.appendleft(num*10+num%10+1)

print(q.pop())

Solution (Python):
def main():
    from collections import deque

    K = int(input())
    if K <= 9:
        print(K)
        return
    
    q = deque()
    for i in range(1, 10):
        q.append(i)
    
    count = 9
    while True:
        get_num = q.popleft()
        for i in range(-1, 2):
            add_num = get_num % 10 + i
            if 0 <= add_num and add_num <= 9:
                q.append(get_num * 10 + add_num)
                count += 1
                if count == K:
                    print(q.pop())
                    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
k=int(input())
logl=len(str(k))

def bfs(nowres, result=[]):
  if len(result) >= k:
    return sorted(result)
  rescand=[]
  for res in nowres:
    eq=res*10+res%10
    rescand.append(eq)
    if eq % 10>0:
      rescand.append(eq-1)
    if eq % 10<9:
      rescand.append(eq+1)
  return bfs(rescand, result+nowres)

res=bfs(list(range(1,10)))

print(res[k-1])

Solution (Python):
from collections import deque

k = int(input())

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

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

print(s)

Solution (Python):
from collections import deque
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    k=INT()
    que=deque([1,2,3,4,5,6,7,8,9])
    for i in range(k):
        q=que.popleft()
        if q%10!=0:
            que.append(10*q+q%10-1)
        que.append(10*q+q%10)
        if q%10!=9:
            que.append(10*q+q%10+1)
        
    print(q)
if __name__ == '__main__':
    do()

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

i = 0
while i<9:
    X = []
    for L in lis:
        if i == 0 or L >= 10**i:
            s = str(L)
            if s[-1] == "0":
                X.append(10*L)
                X.append(10*L+1)
            elif s[-1] == "9":
                X.append(10*L+8)
                X.append(10*L+9)
            else:
                X.append(10*L+int(s[-1])-1)
                X.append(10*L+int(s[-1]))
                X.append(10*L+int(s[-1])+1)
    for x in X:
        lis.append(x)
    i += 1
print(lis[k-1])

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

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

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

ans = []
for j in range(len(cand)):
  for val in cand[j]:
    ans.append(val)
ans = sorted(ans)

print(ans[k - 1])

Solution (Python):
from collections import deque
dq = deque([1,2,3,4,5,6,7,8,9])
ans = []
while dq:
    p = dq.popleft()
    ans.append(p)
    if p <= 323456666:
        q = p % 10
        if not q in [0,9]:
            for i in range(-1,2):
                dq.append(10*p+q+i)
        else:
            if q == 9:
                dq.append(10*p+8)
                dq.append(10*p+9)
            else:
                dq.append(10*p)
                dq.append(10*p+1)
ans.sort()

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

Solution (Python):
from collections import deque

K = int(input())
Q = deque()
for i in range(1, 10):
    Q.append(i)
temp = 0
for i in range(K):
    temp = Q.popleft()
    if temp%10 != 0:
        Q.append(temp*10+temp%10-1)
    Q.append(temp*10+temp%10)
    if temp%10 != 9:
        Q.append(temp*10+temp%10+1)
print(temp)

Solution (Python):


import sys
input=sys.stdin.readline

def main():
    K=int(input())
    lunlun=[1,2,3,4,5,6,7,8,9]
    ind=0
    lll=9
    for dig in range(12):
        l=lll
        for i in lunlun[ind:]:
            s=str(i)
            x=int(s[dig])
            if 0<=x-1<=9:
                lunlun+=[int(s+str(x-1))]
                lll+=1
            if 0<=x<=9:
                lunlun+=[int(s+str(x))]
                lll+=1
            if 0<=x+1<=9:
                lunlun+=[int(s+str(x+1))]
                lll+=1
            if lll>K:
                break
        ind=l
    lunlun.sort()
    print(lunlun[K-1])
    
    
if __name__=="__main__":
    main()

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

Solution (Python):
k=int(input())
result = []
def dfs(pos, val):
  result.append(val)

  if pos == 10:
    return
  
  for i in range(-1,2):
    add_num = (val % 10) + i
    if 0 <= add_num <= 9:
      dfs(pos+1, val*10+add_num)

for i in range(1,10):
  dfs(1,i)
result.sort()
print(result[k-1])

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

        
if __name__ == '__main__':
    main()

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	k = int(input())
	
	
	l=['_']*50
	l[0]=0
	for _ in range(k):
		for i, v in enumerate(l):
			l[i]+=1
			if l[i] == 10 and l[i+1]=='_':
				l[i+1]=1
				l[:i+1]=[0]*(i+1)
				break
			elif l[i] == 10:
				l[i]=l[i+1]
			elif l[i+1]=='_':
				
				for j in range(1,i+1):
					l[i-j]=max(0, l[i-j+1]-1)
				break				
			elif l[i] <= l[i+1]+1:
				
				for j in range(1,i+1):
					l[i-j]=max(0, l[i-j+1]-1)
				break	
		
		
	print(''.join([str(c) for c in l[::-1] if c != '_']))
				
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
k = int(input())
lunlun = []
def dfs(A):
    if len(A) == 10:
        return
    else:
        start = int(A[-1])
        if start == 9:
            for i in range(start-1, start+1):
                A.append(str(i))
                lunlun.append("".join(A))
                dfs(A)
                A.pop()
        elif start == 0:
            for i in range(start, start+2):
                A.append(str(i))
                lunlun.append("".join(A))
                dfs(A)
                A.pop()
        else:
            for i in range(start-1, start+2):
                A.append(str(i))
                lunlun.append("".join(A))
                dfs(A)
                A.pop()
for j in range(1, 10):
    lunlun.append(str(j))
    dfs([str(j)])
lunlun = list(map(int, lunlun))
lunlun.sort()
print(lunlun[k-1])

Solution (Python):
k = int(input())
lun = [str(i) for i in range(1, 10)]
L = [str(i) for i in range(1, 10)]
nL = []
while len(lun) < 10 ** 5:
    for num in L:
        l = num[-1]
        lm = int(l) - 1
        lp = int(l) + 1
        nL.append(num + l)
        if lm >= 0:
            nL.append(num + str(lm))
        if lp < 10:
            nL.append(num + str(lp))
    lun.extend(nL)
    L = nL
    nL = []
lunlun = [int(x) for x in lun]
lunlun.sort()
print(lunlun[k-1])

Solution (Python):
from collections import deque
dq = deque([1,2,3,4,5,6,7,8,9])
ans = []
while dq:
    p = dq.popleft()
    ans.append(p)
    if p <= 323456666:
        q = p % 10
        if not q in [0,9]:
            for i in range(-1,2):
                dq.append(10*p+q+i)
        else:
            if q == 9:
                dq.append(10*p+8)
                dq.append(10*p+9)
            else:
                dq.append(10*p)
                dq.append(10*p+1)
ans.sort()

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

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    k = int(ipt())
    q = queue.Queue()
    for i in range(1,10):
        q.put(i)
    for _ in [0]*k:
        qi = q.get()
        if not qi%10 == 0:
            q.put(qi*10+qi%10-1)
        q.put(qi*10+qi%10)
        if not qi%10 == 9:
            q.put(qi*10+qi%10+1)
    print(qi)
    return

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

cnt = 0
while q:
    curr = q.popleft()
    cnt += 1
    if cnt == k:
        break
    if curr % 10 == 9:
        q.append(curr * 10 + curr % 10 - 1)
        q.append(curr * 10 + curr % 10)
    elif curr % 10 == 0:
        q.append(curr * 10 + curr % 10)
        q.append(curr * 10 + curr % 10 + 1)
    else:
        q.append(curr * 10 + curr % 10 - 1)
        q.append(curr * 10 + curr % 10)
        q.append(curr * 10 + curr % 10 + 1)

print(curr)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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






N = getN()

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

ans = []

def dfs(s):
    global ans
    if len(s) >= 11:
        return
    
    else:
        ans.append(int(s))
        
        s_last = int(s[-1])
        for i in next[s_last]:
            dfs(s + str(i))


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

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

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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






N = getN()

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

ans = []

def dfs(s):
    global ans
    if len(s) >= 11:
        return
    
    else:
        ans.append(int(s))
        
        s_last = int(s[-1])
        for i in next[s_last]:
            dfs(s + str(i))


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

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

Solution (Python):
def expand(x):
  s = x[0]
  if (s == '0'):
    e = ['0', '1']
  elif (s == '9'):
    e = ['8', '9']
  else:
    e = [str(int(s) + (i-1)) for i in range(3)]
  y = [i+x for i in e]
  return y


Y      = [str(i) for i in range(10)]
result = Y.copy()

for _ in range(10):
  tmp = []
  for i in Y:
    tmp += expand(i)
  result.extend(tmp)
  Y = tmp
  
iY = set(map(int, result))
iY = sorted(list(iY))

X = int(input())
print(iY[X])

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

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

if K < 10:
    print(K)
else:
    now = 0
    K -= 9
    ans = 0
    while True:
        md = lst[now] % 10
        for i in range(10):
            if abs(md - i) <= 1:
                K -= 1
                ans = lst[now] * 10 + i
                lst.append(ans)
                if K == 0:
                    print(ans)
                    exit()
        now += 1

Solution (Python):
K=int(input())
ans=[]
def saiki(A):
    genzai_saigo=int(A[-1])
    ketasu=len(A)
    if ketasu>0:
        B="".join(A)
        ans.append(eval(B))
    if ketasu==10:
        return
    for i in [genzai_saigo-1,genzai_saigo,genzai_saigo+1]:
        if i < 0 or i>9:
            continue
        A.append(str(i))
        saiki(A)
        A.pop()
for i in range(1,10):
    saiki([str(i)])
ans.sort()
print(ans[K-1])

Solution (Python):
K=int(input())
ans=set()
for i in range(1,10):
    ans.add(i)
def saiki(A):
    genzai_saigo=int(A[-1])
    ketasu=len(A)
    if ketasu>0:
        B="".join(A)
        ans.add(eval(B))
    if ketasu==10:
        return
    for i in [genzai_saigo-1,genzai_saigo,genzai_saigo+1]:
        if i < 0 or i>9:
            continue
        A.append(str(i))
        saiki(A)
        A.pop()
for i in range(1,10):
    saiki([str(i)])
kotae=list(ans)
kotae.sort()
print(kotae[K-1])

Solution (Python):
K=int(input())
ans=set()
for i in range(1,10):
    ans.add(i)
def saiki(A):
    genzai_saigo=int(A[-1])
    ketasu=len(A)
    if ketasu>0:
        B="".join(A)
        ans.add(eval(B))
    if ketasu==10:
        return
    for i in [genzai_saigo-1,genzai_saigo,genzai_saigo+1]:
        if i < 0 or i>9:
            continue
        A.append(str(i))
        saiki(A)
        A.pop()
for i in range(1,10):
    saiki([str(i)])
kotae=list(ans)
kotae.sort()
print(kotae[K-1])

Solution (Python):
from sys import stdin
from collections import deque
def main():
    
    readline=stdin.readline
    k=int(readline())

    lunlun_number=[]
    d=deque(map(str,range(1,10)))
    cnt=0
    while cnt<k:
        now=d.popleft()
        lunlun_number.append(now)
        cnt+=1
        if now[-1]=="0":
            nex=("0","1")
        elif now[-1]=="9":
            nex=("8","9")
        else:
            last=int(now[-1])
            nex=(str(last-1),str(last),str(last+1))
        for x in nex:
            d.append(now+x)

    print(lunlun_number[k-1])

if __name__=="__main__":
    main()

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

L = list(range(10))
i = 1
while len(L) <= k:
    Li = L[i]
    a = Li % 10
    for b in range(a - 1, a + 2):
        if b < 0 or b > 9:
            continue
        L.append(Li * 10 + b)
    i += 1

print(L[k])

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    k = int(input())
    q = collections.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.popleft())

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

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

q = collections.deque()
for i in range(1, 10):
    q.append(i)
i = 9
while True:
    x = q.popleft()
    lsk = x % 10
    shifted = x * 10
    if lsk != 0:
        q.append(shifted + lsk - 1)
        i += 1
        if i == K:
            print(shifted + lsk - 1)
            break
    q.append(shifted + lsk)
    i += 1
    if i == K:
        print(shifted + lsk)
        break
    if lsk != 9:
        q.append(shifted + lsk + 1)
        i += 1
        if i == K:
            print(shifted + lsk + 1)
            break

Solution (Python):
from collections import deque


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

Solution (Python):
import sys
import itertools

import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

k = int(input())


import queue
q = queue.Queue()

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

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

total = 9
while total <= k:
    x = q.get()
    if x % 10 != 0:
        val = x * 10 + x % 10 - 1
        q.put(val)
        total += 1
        if total == k:
            print(val)
            exit()

    val = x * 10 + x % 10
    q.put(val)
    total += 1
    if total == k:
        print(val)
        exit()
    if x % 10 < 9:
        val = x * 10 + x % 10 + 1
        q.put(val)
        total += 1
        if total == k:
            print(val)
            exit()
    
    if total >= k:
        for i in range(total - k):
            q.get()
        print(q.get())
        exit()

Solution (Python):
from collections import deque
n = int(input())
L = list(range(1, 10))
count = 9
d = deque([1,2,3,4,5,6,7,8,9])
while count < n:
    p = d.popleft()
    p1 = p%10
    if p1 == 0:
        lunlun = p*10 + p1
        d.append(lunlun)
        L.append(lunlun)
        count += 1
        lunlun += 1
        d.append(lunlun)
        L.append(lunlun)
        count += 1
    elif p1 == 9:
        lunlun = p*10 + p1 - 1
        d.append(lunlun)
        L.append(lunlun)
        count += 1
        lunlun += 1
        d.append(lunlun)
        L.append(lunlun)
        count += 1
    else:
        lunlun = p*10 + p1 - 1
        d.append(lunlun)
        L.append(lunlun)
        count += 1
        lunlun += 1
        d.append(lunlun)
        L.append(lunlun)
        count += 1
        lunlun += 1
        d.append(lunlun)
        L.append(lunlun)
        count += 1
print(L[n-1])

Solution (Python):
from collections import deque

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

cnt = 0
while cnt < k:
    s = q.popleft()
    cnt += 1
    t = s % 10
    if t != 0:
        q.append(10 * s + (t - 1))
    q.append(10 * s + t)
    if t != 9:
        q.append(10 * s + (t + 1))
    
print(s)

Solution (Python):
import numpy as np
import math
import collections
import fractions
import itertools

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

def solve():
    k = int(input())
    all = []
    for i in range(1,10):
        rec(1, i, all)
    all.sort()
    print(all[k-1])
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque
K = int(input())
d = deque(["1","2","3","4","5","6","7","8","9"])
ans = 0
for i in range(K):
    now = d.popleft()
    num = int(now[-1])
    if num == 0:
        d.append(now+"0")
        d.append(now+"1")
    elif num == 9:
        d.append(now+"8")
        d.append(now+"9")
    else:
        d.append(now+str(num-1))
        d.append(now+str(num))
        d.append(now+str(num+1))
print(now)

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

K = int(input())


luns = [[]]
luns.append(list("123456789"))
for keta in range(2, 11):
    keta_lun = []
    for s in luns[-1]:
        lst = int(s[-1])
        if lst - 1 >= 0:
            keta_lun.append(s + str(lst - 1))
        keta_lun.append(s + str(lst))
        if lst + 1 < 10:
            keta_lun.append(s + str(lst + 1))
    luns.append(keta_lun)

index = 0
for keta_luns in luns:
    for lun in keta_luns:
        index += 1
        if index == K:
            print(lun)
            quit()

Solution (Python):

from collections import deque


def solve(K):
    lunlun = deque([i for i in range(1, 10)])

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

    print(ans)


if __name__ == '__main__':
    K = int(input())
    solve(K)

Solution (Python):
def solve(K):
    lun = [0]

    def nextLunlun(arr, d=0):
        arr[d] += 1
        if arr[d] == 10:
            if d + 1 == len(arr):
                arr.append(1)
                arr[d] = 0
                return arr
            else:
                arr = nextLunlun(arr, d + 1)
                arr[d] = arr[d + 1] - 1 if arr[d + 1] > 0 else 0
                return arr
        if d + 1 != len(arr):
            if abs(arr[d] - arr[d + 1]) > 1:
                if arr[d] < arr[d + 1]:
                    arr[d] = arr[d + 1] - 1
                    return arr
                else:
                    arr = nextLunlun(arr, d + 1)
                    arr[d] = arr[d + 1] - 1 if arr[d + 1] > 0 else 0
                    return arr
        return arr

    for _ in range(K):
        lun = nextLunlun(lun)

    ans = 0
    for i in range(len(lun)):
        ans += lun[i] * (10 ** i)

    print(ans)


if __name__ == '__main__':
    K = int(input())
    solve(K)

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

Solution (Python):

import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

'''
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,100 (36)
101,110,111,112,121,122,123,210,211,212,221,222,223,232,233,234,

1
10
11
12
100
101
110
111
112
121
122
123
1000
1001
1002


'''

nums = []
def precomp(i):
    temp = str(i)
    x=[-1,0,1]
    for j in range(3):
        foo = int(temp[-1])+x[j]
        if(foo>=0 and foo<=9):
            toadd = int(temp+str(foo))

            if (i > 3234566667):
                return
            nums.append(toadd)
            precomp(toadd)

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

nums.sort()

k = INT()

print(nums[k-1])

Solution (Python):
from collections import deque
que=deque([i for i in range(1,10)])
k=int(input())
count=0
while count!=k:
  a=que.popleft()
  count+=1
  if a%10==9:
    que.extend([10*a+8,10*a+9])
  elif a%10==0:
    que.extend([10*a,10*a+1])
  else:
    b=a*10+(a%10)-1
    que.extend([b,b+1,b+2])
print(a)

Solution (Python):
import sys
readline = sys.stdin.readline

K = int(readline())

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

cnt = 0
while q:
  n = q.popleft()
  cnt += 1
  if cnt == K:
    print(n)
    break
  right = n % 10
  for c in range(max(right - 1, 0),min(right + 2,10)):
    q.append(n * 10 + c)