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 math import *
from copy import *
from string import *				
from random import *				
from bisect import *				
from sys import stdin				
from sys import maxsize
from operator import *				
from itertools import *
from collections import Counter		
from collections import defaultdict 

'''

'''

def solve(k):
	q = [1,2,3,4,5,6,7,8,9]
	last = 0
	i = 0
	while(k > 0):
		last = q[i]
		rem = last%10
		lower = 0
		bigger = 0
		if(rem != 0):
			lower = 10*last + rem - 1
		if(rem != 9):
			bigger = 10*last + rem + 1
		equal = 10*last + rem
		
		if(lower):
			q.append(lower)
		q.append(equal)
		if(bigger):
			
			q.append(bigger)
		i += 1
		k -= 1
	
	return last
	

K = int(stdin.readline())
ans = solve(K)
print(ans)

Solution (Python):
from queue import Queue

k = int(input())

q = Queue()

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

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

print(x)

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

k = int(input())

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

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

Solution (Python):
import heapq

K = int(input())

q = [i for i in range(1, 10)]
heapq.heapify(q)
cnt = 0
while cnt < K:
    x = heapq.heappop(q)
    cnt += 1
    heapq.heappush(q, 10 * x + x % 10)
    if x % 10 != 0:
        heapq.heappush(q, 10 * x + x % 10 - 1)
    if x % 10 != 9:
        heapq.heappush(q, 10 * x + x % 10 + 1)
print(x)

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

while 1:
    x = len(a)
    if k <= x:
        print(a[k-1])
        sys.exit( )
    b=[]
    for z in a:
        if z[-1]!='0':
            b.append(z+str(int(z[-1])-1))
        b.append(z+z[-1])
        if z[-1]!='9':
            b.append(z+str(int(z[-1])+1))
    k-=x
    a=b[:]

Solution (Python):
import queue

q = queue.Queue()

num = int(input())
if num < 13:
    print(num)
    exit()
for _ in range(1,10):
    q.put(_)
for _ in range(num):
    x = q.get()
    t = x % 10

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

Solution (Python):
K = int(input())
A = [i for i in range(1, 10)]
count = 10
for i in range(0, K-1):
    if K >= 10:
        for j in range(0, 10):
            if abs(j - A[0] % 10) <= 1 and count <= K:
                A.append(A[0]*10+j)
                count += 1
        del A[0]
if K < 10:
    print(A[K-1])
else:
    print(A[-1])

Solution (Python):
from collections import deque
k = int(input())
d = deque()
for i in range(1, 10):
    d.append(i)
while k > 1:
    k -= 1
    temp = d.popleft()
    if temp % 10:
        d.append(10 * temp + (temp % 10)-1)
    d.append(10 * temp + (temp % 10))
    if temp % 10 != 9:
        d.append(10 * temp + (temp % 10) + 1)
print(d.popleft())

Solution (Python):
import unittest
import collections


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(15), 23)

    def test_2(self):
        self.assertEqual(think(1), 1)

    def test_3(self):
        self.assertEqual(think(13), 21)

    def test_4(self):
        self.assertEqual(think(100000), 3234566667)


def solve():
    k = read()
    result = think(k)
    write(result)


def read():
    return read_int(1)[0]


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(k):
    k_max = 10 ** 5
    list_of_lunlun_number = prepare_lunlun_number(k_max)
    return list_of_lunlun_number[k - 1]


def write(result):
    print(result)


def prepare_lunlun_number(k_max):
    lunlun_number = collections.deque([])
    deque = collections.deque(list(range(1, 10)))
    length = 0
    while length < k_max:
        d = deque.popleft()
        lunlun_number.append(d)
        length += 1
        if d % 10 == 0:
            deque.append(d * 10 + 0)
            deque.append(d * 10 + 1)
        elif d % 10 == 9:
            deque.append(d * 10 + 8)
            deque.append(d * 10 + 9)
        else:
            m = d % 10
            deque.append(d * 10 + m - 1)
            deque.append(d * 10 + m)
            deque.append(d * 10 + m + 1)
    return lunlun_number


if __name__ == '__main__':
    
    solve()

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

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

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

Solution (Python):
def generate_lunlun(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

if __name__ == '__main__':
    k = int(input())
    lunlun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    p = 0

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

    print(lunlun[k-1])

Solution (Python):
from queue import Queue

k = int(input())



q = Queue()

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

ans = 0
for j in range(k):
  ans = q.get()
  f = ans % 10
  n = ans * 10 + f
  
  if f != 0:
    q.put(n-1)
  
  q.put(n)
  
  if f != 9:
    q.put(n+1)
print(ans)

Solution (Python):

from collections import deque

def main():

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

    cnt = 0
    dq = deque()
    for i in range(1, 10):
        dq.append(i)

    while len(dq):
        v = dq.popleft()
        x = v%10 
        cnt += 1
        if x == 0:
            for j in (0, 1):
                nx = v*10 + j
                cand.append(nx)
                dq.append(nx)
        elif x == 9:
            for j in (-1, 0):
                nx = v*10 + 9 + j
                cand.append(nx) 
                dq.append(nx)
        else:
            for j in (-1, 0, 1):
                nx = v*10 + x + j
                cand.append(nx)
                dq.append(nx)
        if len(cand) > 2*k:
            break    

    print(cand[k-1])
main()

Solution (Python):
import heapq
import sys

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

k = int(input())

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

ans = 9

while True:
  x = heapq.heappop(a)
  
  if x%10 ==0:
    for i in [0,1]:
      y = x*10 + i
      ans += 1
      if ans == k:
        print(y)
        sys.exit()
      heapq.heappush(a,y)
  elif x%10 == 9:
    for i in [-1,0]:
      y = x*10 + x%10 + i
      ans += 1
      if ans == k:
        print(y)
        sys.exit()
      heapq.heappush(a,y)
  else:
    for i in [-1,0,1]:
      
      y = x*10 + x%10 + i
      ans += 1
      if ans == k:
        print(y)
        sys.exit()
      heapq.heappush(a,y)

Solution (Python):
K=int(input())
import queue
a=queue.Queue()
if K<=9:
  print(K)
else:
  for i in range(1,10):
    a.put(i)
  n=K
  while n>1:
    p=a.get()
    x=p%10
    if x%10!=0:
      a.put(10*p+x-1)
    a.put(10*p+x)
    if x%10!=9:
      a.put(10*p+x+1)
    n-=1
  ans=a.get()
  print(ans)

Solution (Python):

from collections import deque

def main():

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

    cnt = 0
    dq = deque()
    for i in range(1, 10):
        dq.append(i)

    while len(dq):
        v = dq.popleft()
        x = v%10 
        cnt += 1
        if x == 0:
            for j in (0, 1):
                nx = v*10 + j
                cand.append(nx)
                dq.append(nx)
        elif x == 9:
            for j in (-1, 0):
                nx = v*10 + 9 + j
                cand.append(nx) 
                dq.append(nx)
        else:
            for j in (-1, 0, 1):
                nx = v*10 + x + j
                cand.append(nx)
                dq.append(nx)
        if len(cand) > 2*k:
            break    

    cand.sort()
    print(cand[k-1])
main()

Solution (Python):
from collections import deque

n= int(input())

if n < 10:
    print(n);exit()

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

for _ in range(1,n):

    t = q.popleft()

    
    tt = int(str(t)[-1])

    for j in range(-1,2):
        ttt = tt+j
        if ttt >= 0 and ttt <= 9:
            
            q.append(int(str(t) + str(ttt)))

print(q.popleft())

Solution (Python):
from collections import deque

n= int(input())

if n < 10:
    print(n);exit()

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

for _ in range(1,n):

    t = q.popleft()

    tt = t%10

    for j in range(-1,2):
        ttt = tt+j
        if ttt >= 0 and ttt <= 9:
            q.append(t * 10 + ttt)

print(q.popleft())

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

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


def dfs(d, val, all):
    all.append(val)
    if d == 10:
        return
    for j in [-1, 0, 1]:
        add = (val) % 10 + j
        if 0 <= add <= 9:
            dfs(d+1, val*10+add, all)


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

Solution (Python):
from collections import deque

k = int(input())

q = deque()

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

for _ in range(k):
    temp = q.popleft()
    if temp % 10 != 0:
        q.append(temp*10+int(str(temp)[-1])-1)
    
    q.append(temp*10+int(str(temp)[-1]))

    if temp % 10 != 9:
        q.append(temp*10+int(str(temp)[-1])+1)

print(temp)

Solution (Python):
def main():
    import sys
    
    K = int(sys.stdin.readline())
    
    lunlun_list = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
    
    if K <= 9:
        ans = lunlun_list[0][K - 1]
    else:
        count = 9
        n = 0
        while count < K:
            add_list = []
            for m in lunlun_list[n]:
                if m % 10 == 0:
                    m_1 = m * 10
                    add_list.append(m_1)
                    count += 1
                    if count == K:
                        ans = m_1
                        break
                    m_2 = m * 10 + 1
                    add_list.append(m_2)
                    count += 1
                    if count == K:
                        ans = m_2
                        break
                elif m % 10 == 9:
                    m_1 = m * 10 + 8
                    add_list.append(m_1)
                    count += 1
                    if count == K:
                        ans = m_1
                        break
                    m_2 = m * 10 + 9
                    add_list.append(m_2)
                    count += 1
                    if count == K:
                        ans = m_2
                        break
                else:
                    l = m % 10
                    m_1 = m * 10 + l - 1
                    add_list.append(m_1)
                    count += 1
                    if count == K:
                        ans = m_1
                        break
                    m_2 = m * 10 + l
                    add_list.append(m_2)
                    count += 1
                    if count == K:
                        ans = m_2
                        break
                    m_3 = m * 10 + l + 1
                    add_list.append(m_3)
                    count += 1
                    if count == K:
                        ans = m_3
                        break
            lunlun_list.append(add_list)
            n += 1
            
    print(ans)
                    
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import queue

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

    i = 0
    while True:
        i += 1

        n = q.get()
        center_num = (10 * n) + (n % 10)
        
        if n % 10 != 0:
            q.put(center_num - 1)
        
        q.put(center_num)

        if n % 10 != 9:
            q.put(center_num + 1)

        if i >= K:
            
            print(n)
            sys.exit()

if __name__ == '__main__':
    main()

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

Solution (Python):


import queue

k = int(input())

q = queue.Queue()

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

for i in range(k):
    a = q.get()
    if i==k-1:
        print(a)
        exit()
    c = int(str(a)[-1])
    if c==0:
        q.put(a * 10 + c)
        q.put(a * 10 + c + 1)
    elif c==9:
        q.put(a * 10 + c - 1)
        q.put(a * 10 + c)
    else:
        q.put(a*10+c-1)
        q.put(a*10+c)
        q.put(a*10+c+1)

Solution (Python):
k=int(input())
total=0
def count(keta,s,ans):
    global total
    if keta==1:
        total+=1
        if k==total:
            print(ans) 
        return 
    for m in range(10):
        if abs(s-m)<=1:
            count(keta-1,m,ans+str(m))
for i in range(1,11):
    for j in range(1,10):
        count(i,j,str(j))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
K=input()

L=[]

def dfs(n,depth):
    L.append(n)
    if depth==9: return
    ichi_no_kurai=n%10
    for i in range(max(0,ichi_no_kurai-1),min(ichi_no_kurai+2,10)):
        next=n*10+i
        dfs(next,depth+1)

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

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

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

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

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

Current = [1, 2, 3, 4, 5, 6, 7, 8, 9]
while 1:
    Next = deque([])
    cnt = len(Current) 
    if K <= cnt:
        
        ans = Current[K - 1]
        break
    else:   
        
        for i in Current:
            key = i % 10
            for j in [key - 1, key, key + 1]:
                if 0 <= j and j <= 9:
                    Next.append(i * 10 + j)
                else: 
                    pass
        K -= cnt
        Current = Next


print(ans)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd

sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

a = []

def g(x):
    for i in range(-1,2):
        last = (x%10) + i
        if x <= 3234566667 and last != -1 and last != 10:
            f(10*x+last)
def f(x):
    a.append(x)
    g(x)

for i in range(1,10):
    f(i)
a.sort()

def main():
    n = inp()
    print(a[n-1])
    
if __name__ == "__main__":
    main()

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

Current = [1, 2, 3, 4, 5, 6, 7, 8, 9]
cnt = 9
times = 0
while 1:
    Next = deque([])
    cnt = len(Current) 
    if K <= cnt:
        
        ans = Current[K - 1]
        break
    else:   
        
        for i in Current:
            key = i % 10
            for j in [key - 1, key, key + 1]:
                if 0 <= j and j <= 9:
                    Next.append(i * 10 + j)
                else: 
                    pass
        K -= cnt
        Current = Next


print(ans)

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

from collections import deque
queue = deque([1,2,3,4,5,6,7,8,9])

count = 0

while queue:
    now = queue.popleft()
    count += 1
    if count == k:
        print(now)
        exit()
    now_ = now%10
    if now_ == 0:
        queue.append(10*now+now_)
        queue.append(10*now+now_+1)
    elif now_ == 9:
        queue.append(10*now+now_-1)
        queue.append(10*now+now_)
    else:
        queue.append(10*now+now_-1 )
        queue.append(10*now+now_)
        queue.append(10*now+now_+1)

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

ans=0
cnt=0

while 1:
    x=q.popleft()
    cnt+=1
    if cnt==k:
        ans=x
        break
    xmod10 = x % 10
    if xmod10 != 0:
        q.append(10*x+(xmod10-1))
    q.append(10*x+(xmod10))
    if xmod10 != 9:
        q.append(10*x+(xmod10+1))

print(ans)

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

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

K = int(input())
t = 0
ans = 0

while t < K:
  t += 1
  ans = q.get()
  p = int(str(ans)[-1])
  for i in range(-1, 2):
    if 0 <= p+i < 10: q.put(int(str(ans) + str(p+i)))

print(ans)

Solution (Python):
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from queue import Queue


def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


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


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    k = INT()
    q = Queue()
    for i in range(1, k+10):
        
        if i < 10:
            q.put(i)
        else:
            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(x)


if __name__ == '__main__':
    main()

Solution (Python):
K = int(input())
import heapq
que = [i for i in range(1,10)]
heapq.heapify(que)
for i in range(K):
    now = heapq.heappop(que)
    if now%10 == 0:
        heapq.heappush(que,10*now)
        heapq.heappush(que,10*now+1)
    elif now%10 == 9:
        heapq.heappush(que,10*now+8)
        heapq.heappush(que,10*now+9)
    else:
        heapq.heappush(que,10*now+(now%10))
        heapq.heappush(que,10*now+(now%10)-1)
        heapq.heappush(que,10*now+(now%10)+1)
print(now)

Solution (Python):
import queue

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

    numq = queue.Queue()
    for n in range(1, 9+1):
        numq.put(n)

    ans = None
    for _ in range(K):
        n = numq.get()
        
        
        base = n*10
        if base//10%10 >= 1:
            numq.put(base + (base//10%10-1))
        numq.put(base + (base//10%10))
        if base//10%10 <= 8:
            numq.put(base + (base//10%10+1))
        ans = n

    print(ans)
        

if __name__=='__main__':
    main()

Solution (Python):
from collections import deque

K = int(input())
l = [9,8,7,6,5,4,3,2,1]
lunlun = deque(l)
ans = l
for _ in range(K - 9):
    x = lunlun.pop()
    tmp = 10 * x + (x % 10)
    if x % 10 != 0:
        lunlun.appendleft(tmp - 1)
        ans.append(tmp - 1)
    lunlun.appendleft(tmp)
    ans.append(tmp)
    if x % 10 != 9:
        lunlun.appendleft(tmp + 1)
        ans.append(tmp + 1)
ans.sort()
print(ans[K - 1])

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

K = int(read().rstrip())

runrun = [None for _ in range(1, 20)] 
runrun[1] = (1, 2, 3, 4, 5, 6, 7, 8, 9)

def gen_runrun(keta):
    for x in runrun[keta-1]:
        r = x % 10

        if r > 0:
            yield x * 10 + r - 1
        yield x * 10 + r
        if r < 9: 
            yield x * 10 + r + 1


for keta in range(2, 11):
    runrun[keta] = tuple(gen_runrun(keta))

for keta in range(1, 11):
    if K < len(runrun[keta]):
        answer = runrun[keta][K-1]
        break
    K -= len(runrun[keta])

print(answer)

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

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

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

while 1:
    for new_lunlun in lunlun_generator(lunlun[p]):
       lunlun.append(new_lunlun)

    p += 1
    if p == K:
        break

print(lunlun[p-1])

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

Solution (Python):
k = int(input())
lunlun = [1,2,3,4,5,6,7,8,9]
i = 0
while len(lunlun) < k:
  p = lunlun[i]
  if str(p)[-1] == '0':
    lunlun.append(p*10)
    lunlun.append(p*10+1)
  elif str(p)[-1] == '9':
    lunlun.append(p*10+8)
    lunlun.append(p*10+9)
  else:
    lunlun.append(p*10+p%10-1)
    lunlun.append(p*10+p%10)
    lunlun.append(p*10+p%10+1)
  i += 1

print(lunlun[k-1])

Solution (Python):
import numpy as np
K = int(input())
lunlun_number = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
for _ in range(9):
    tmp = []
    for n in lunlun_number[-1]:
        if n % 10 != 0:  
            tmp.append(n * 10 + (n % 10 - 1))
        tmp.append(n * 10 + (n % 10))
        if n % 10 != 9:  
            tmp.append(n * 10 + (n % 10 + 1))
    lunlun_number.append(tmp)
lunlun_number = [flatten for inner in lunlun_number for flatten in inner]
print(lunlun_number[K - 1])

Solution (Python):



import sys
input = sys.stdin.readline
from collections import deque

def main():

    K = int(input())

    q = deque([])   
    for i in range(1,10):
        q.append(i)
    k=0
    while k<K:
        p = q.popleft()     
        k+=1
        x=p%10
        if x-1>=0:
            q.append(p*10+x-1)
        q.append(p*10+x)
        if x+1<=9:
            q.append(p*10+x+1)
    print(p)

if __name__ == '__main__':
    main()

Solution (Python):
import queue

K = int(input())

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

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

print(q_K)

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

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


def get_lunlun(K):
    for num in queue:
        if len(queue) >= K:
            return queue[K - 1]
        for i in range(-1, 2):
            last = num % 10 + i
            if last < 0 or last > 9:
                continue
            queue.append(num * 10 + last)


print(get_lunlun(K))

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


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

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

Solution (Python):
import sys

MAX = 1000000
Q = [0] * MAX
head = 0
tail = 0

def isEmpty():
    return head == tail

def isFull():
    return head == (tail + 1) % MAX

def enqueue(x):
    global tail
    if isFull():
        print("オーバーフロー")
        sys.exit()
    Q[tail] = x
    if tail + 1 == MAX:
        tail = 0
    else:
        tail += 1

def dequeue():
    global head
    if isEmpty():
        print("アンダーフロー")
        sys.exit()
    x = Q[head]
    if head + 1 == MAX:
        head = 0
    else:
        head += 1
    return x

k = int(input())

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

for i in range(k):
    x = dequeue()
    b = x % 10
    if b != 0:
        enqueue(10 * x + b - 1)
    enqueue(10 * x + b)
    if b != 9:
        enqueue(10 * x + b + 1)
print(x)

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


def dfs(x):
    if x > 10**10:
        return 0
    else:
        ans.append(x)
        y = x % 10
        for i in range(10):
            if abs(y-i) <= 1:
                dfs(10*x+i)
                
for i in range(1, 10):
    dfs(i)
ans.sort()
print(ans[k-1])

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

Solution (Python):
import queue

k = int(input())
q = queue.Queue()
x = -1
for i in range(1,10):
    q.put(i)
for i in range(1,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(x)

Solution (Python):
k = int(input())
ans = [i for i in range(1,10)]

i = 0

for i in range(k):
    now = ans[i]
    if str(now)[-1] == '0':
        ans.append(now*10)
        ans.append(now*10+1)
    elif str(now)[-1] == '9':
        ans.append(now*10+8)
        ans.append(now*10+9)
    else:
        ans.append(now*10+now%10-1)
        ans.append(now*10+now%10)
        ans.append(now*10+now%10+1)
    if len(ans) > k:
        break

print(ans[k-1])

Solution (Python):

from collections import deque
k = int(input())

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

for _ in range(9):
    tmp = []
    
    for i in lunlun[-1]:
        if i % 10 != 0:
            tmp.append(i*10 + (i%10 - 1))
        
        tmp.append(i*10 + (i%10))
        
        if i % 10 != 9:
            tmp.append(i*10 + (i%10 + 1))
        
    lunlun.append(tmp)



q = deque()
for i in range(len(lunlun)):
    for j in lunlun[i]:
        q.append(j)
        
print(q[k-1])

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

count=0
while True:
    count += 1
    check = d.popleft()
    mod = check % 10
    if check % 10 == 0:
        d.append(check*10)
        d.append(check*10+1)
    elif check % 10 == 9:
        d.append(check*10+8)
        d.append(check*10+9)
    else:
        d.append(check*10+mod-1)
        d.append(check*10+mod)
        d.append(check*10+mod+1)
    if count == K:
        break
print(check)

Solution (Python):
import sys

def main(n):
    ans = []
    ans.append(list(range(1,10)))
    count = len(ans[0])

    if n < 10:
        return n

    while True:
        ans.append([])
        for i in ans[-2]:
            if int(str(i)[-1]) != 0:
                ans[-1].append(int(str(i) + str(int(str(i)[-1])-1)))
                count += 1
                if count == n:
                    return ans[-1][-1]
            ans[-1].append(int(str(i) + str(i)[-1]))
            count += 1
            if count == n:
                return ans[-1][-1]
            if int(str(i)[-1]) != 9:
                ans[-1].append(int(str(i) + str(int(str(i)[-1])+1)))
                count += 1
                if count == n:
                    return ans[-1][-1]

K = int(input())
print(main(K))

Solution (Python):


k = int(input())
ans = [i for i in range(1,10)]

i = 0



for i in range(k):
    now = ans[i]
    if str(now)[-1] == '0':
        ans.append(now*10)
        ans.append(now*10+1)
    elif str(now)[-1] == '9':
        ans.append(now*10+8)
        ans.append(now*10+9)
    else:
        ans.append(now*10+now%10-1)
        ans.append(now*10+now%10)
        ans.append(now*10+now%10+1)
    if len(ans) > k:
        break

print(ans[k-1])

Solution (Python):
import sys
from collections import deque

K = int(sys.stdin.readline().rstrip())

deq = deque(range(9, 0, -1))
enqueue = deq.appendleft
dequeue = deq.pop

for _ in range(K):
	x = dequeue()
	y = x % 10
	if y != 0:
		enqueue(x * 10 + y - 1)
	enqueue(x * 10 + y)
	if y != 9:
		enqueue(x * 10 + y + 1)
print(x)

Solution (Python):
def gen_lunlun(stop, base=[1, 2, 3, 4, 5, 6, 7, 8, 9]):
    if stop <= 0:
        return base
    
    new_lunlun = []
    for x in base:
        lank1 = x%10
        b = x*10+lank1
        if lank1 == 0:
            tmp = [b, b+1]
        elif lank1 == 9:
            tmp = [b-1, b]
        else:
            tmp = [b-1, b, b+1]
        new_lunlun.extend(tmp)
        if len(new_lunlun) >= stop:
            break
    base.extend(gen_lunlun(stop-len(new_lunlun), new_lunlun))
    return base

k = int(input())
print(gen_lunlun(k-9)[k-1])

Solution (Python):
import heapq
lunlun = [i for i in range(1, 10)]
heapq.heapify(lunlun)
K = int(input())
ans = 0

while K > 0:
    ans = heapq.heappop(lunlun)
    K -= 1
    last_digit = int(str(ans)[-1])
    up, down = last_digit + 1, last_digit - 1
    heapq.heappush(lunlun, ans * 10 + last_digit)
    if up < 10:
        heapq.heappush(lunlun, ans * 10 + up)
    if down >= 0:
        heapq.heappush(lunlun, ans * 10 + down)

print(ans)

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

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