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 copy
def lunlun_check(i,j):
    if abs(i-j) > 1:
        return False
    return True

k = int(input())
ret_list = []
lunlun_list = []
cnt = 0
cnt_pre = 0
digit = 1
while k > (cnt-1):
    cnt_pre = cnt
    tmp_list = []
    ret_list.clear()
    if not lunlun_list:
        for i in range(10):
            tmp_list.append(str(i))
            ret_list.append(i)
    else:
        for i in range(10):
            for data in lunlun_list:
                if lunlun_check(i, int(data[0])):
                    tmp_list.append(str(i)+data)
                    if len(str(int(str(i)+data))) == digit:
                        ret_list.append(int(str(i)+data))
    lunlun_list = tmp_list.copy()
    cnt += len(ret_list)
    digit += 1
print(int( ret_list[k- cnt_pre] ))

Solution (Python):
K=int(input())
lists=[]
for i in range(1,10):
    lists.append(i)
if K<=9:
    print (K)
else:
    for i in range(K):
        if lists[i]%10==0:
            lists.append(lists[i]*10+lists[i]%10)
            lists.append(lists[i]*10+lists[i]%10+1)
        elif lists[i]%10==9:
            lists.append(lists[i]*10+lists[i]%10-1)
            lists.append(lists[i]*10+lists[i]%10)
        else:
            lists.append(lists[i]*10+lists[i]%10-1)
            lists.append(lists[i]*10+lists[i]%10)
            lists.append(lists[i]*10+lists[i]%10+1)
    print (lists[K-1])

Solution (Python):
from collections import deque
a=int(input())
list1=deque([1,2,3,4,5,6,7,8,9])
i=1
while(i<=a) :
  
  if i!=a :
    k=list1.popleft()
    k=str(k)
    if int(k[-1])==0 :
      list1.append(int(str(k)+'0'))
      list1.append(int(str(k)+'1'))
      i+=1
    elif int(k[-1])==9 :
      list1.append(int(str(k)+'8'))
      list1.append(int(str(k)+'9'))
      i+=1
    else :
      list1.append(int(str(k)+str(int(k[-1])-1)))
      list1.append(int(str(k)+str(int(k[-1]))))
      list1.append(int(str(k)+str(int(k[-1])+1)))
      i+=1
  else :
    print(list1[0])
    break

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  q=collections.deque()
  for i in range(1,10):
    q.append(i)

  while q:
    a=q.popleft()
    n-=1

    if n==0:
      return a

    _a=a%10
    for i in range(max(0,_a-1),min(10,_a+2)):
      b=int(str(a)+str(i))
      q.append(b)


print(main())

Solution (Python):
from collections import deque


def main():
    k = int(input())
    queue = deque([i for i in range(1, 10)])
    pop_time = 0
    now = 1
    while pop_time < k:
        now = queue.popleft()
        if now % 10 != 0:
            queue.append(10 * now + now % 10 - 1)
        queue.append(10 * now + now % 10)
        if now % 10 != 9:
            queue.append(10 * now + now % 10 + 1)
        pop_time += 1
    print(now)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
K=int(input())
cnt=0
dp=[0]*(10**6)
piv=0
dig=[0]*10000
d=0
cnt=float("inf")
zure=0
befnum=0
i=0
buf=""
cntall=0
ans=[]
"""なんだこの
while i<2*(10**5):
    if i+1<10:
        dp[i]=i+1
        dig[d]=dig[d]+1
    else:
        if cnt>=dig[d-1]:
            i=i+zure
            zure=0
            cnt=0
            befnum=dig[d]
            d=d+1
        
        buf=str(dp[i-befnum])
        piv=buf[len(buf)-1]
        
        
        if int(piv)==0:
            dp[i+zure]=dp[i-befnum]*10
            dp[i+1+zure]=dp[i - befnum] * 10+1
            dig[d]=dig[d]+2
            zure=zure+1
        elif int(piv)==9:
            dp[i + zure] = dp[i - befnum] * 10+8
            dp[i + 1 + zure] = dp[i - befnum] * 10+9
            dig[d] = dig[d] + 2
            zure = zure + 1
        else:
            dp[i+zure]=dp[i-befnum]*10+int(piv)-1
            dp[i+1+zure]=dp[i - befnum] * 10+int(piv)
            dp[i+2+zure] = dp[i - befnum] * 10 + int(piv)+1
            dig[d] = dig[d] + 3
            zure=zure+2
        cnt=cnt+1
    i=i+1
    
        
    
    
print(dp[K-1])
"""

d=deque()
piv=0
num=0
for i in range(9):
    d.append(i+1)

i=0
while i<K:
    num=d.popleft()
    ans.append(num)
    piv=str(num)
    if piv[len(piv)-1]=="0":
        d.append(num*10)
        d.append(num*10+1)
    elif piv[len(piv)-1]=="9":
        d.append(num*10+8)
        d.append(num * 10 + 9)
    else:
        d.append(num*10+int(piv[len(piv)-1])-1)
        d.append(num*10+int(piv[len(piv)-1]))
        d.append(num * 10 + int(piv[len(piv) - 1])+1)
    i=i+1
    
    
print(ans[K-1])

Solution (Python):
K=int(input())
A=[1,2,3,4,5,6,7,8,9]+[0]*K
i=9
j=0
while i<K:
    if A[j]%10!=0 and A[j]%10!=9:
        A[i]=10*A[j]+A[j]%10-1;i+=1
        A[i]=10*A[j]+A[j]%10;i+=1
        A[i]=10*A[j]+A[j]%10+1;i+=1
    elif A[j]%10==0:
        A[i]=10*A[j]+A[j]%10;i+=1
        A[i]=10*A[j]+A[j]%10+1;i+=1
    else:
        A[i]=10*A[j]+A[j]%10-1;i+=1
        A[i]=10*A[j]+A[j]%10;i+=1
    j+=1
print(A[K-1])

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

q=[1,2,3,4,5,6,7,8,9]
c=0
for i in range(k):
    num=q[c]
    if num%10>0:
        q.append(num*10+num%10-1)
    q.append(num*10+num%10)
    if num%10<9:
        q.append(num*10+num%10+1)
    c+=1
print(q[k-1])

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

k = int(input())

cnt = 0
while k > cnt:
  x = d.popleft()
  cnt += 1  
  if x%10 != 0:
  	d.append(x*10+x%10-1)
  d.append(x*10+x%10)
  if x%10 != 9:
    d.append(x*10+x%10+1)
print(x)

Solution (Python):
import queue

k = 0

def format_input(filename = None):
	global k
	if filename == None:
		k = int(input())

	elif filename == '__random__':
		from random import randint as rng
		k = rng(1, 10**5)
		print(k)

def get_answer():
	q = queue.Queue()
	[q.put(i) for i in range(1, 10)]
	i = 0
	while i < k:
		answer = q.get()
		child = answer * 10 + answer % 10
		if child % 10 != 0:
			q.put(child - 1)
		q.put(child)
		if child % 10 != 9:
			q.put(child + 1)
		i += 1
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Solution (Python):
def solve(n):
	if n<=9:
		return n
	q = [0]
	for i in range(1,10):
		q.append(i)
	now = 1
	cnt = 9
	while 1:
		u = q[now]
		now += 1
		if u%10!=0:
			t = u*10 + u%10 - 1
			cnt += 1
			if cnt==n:
				return t
			q.append(t)
		t = u*10 + u%10
		cnt += 1
		if cnt==n:
			return t
		q.append(t)
		if u%10 !=9:
			t = u*10 + u%10 + 1
			cnt += 1
			if cnt==n:
				return t
			q.append(t)

print(solve(int(input())))

Solution (Python):
from collections import deque

q=deque()

N=int(input())

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

for _ in range(N-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):
K=int(input())
num1=[[1,2,3,4,5,6,7,8,9]]
num2=[]
sm=0
for j in range(10):
    li=[]
    for k in range(len(num1[j])):
        if num1[j][k]%10!=0:
            li.append(num1[j][k]*10+num1[j][k]%10-1)
        li.append(num1[j][k]*10+num1[j][k]%10)
        if num1[j][k]%10!=9:
            li.append(num1[j][k]*10+num1[j][k]%10+1)
    li.sort()
    num1.append(li)
for j in range(len(num1)):
    sm+=len(num1[j])
    num2+=num1[j]
print(num2[K-1])

Solution (Python):
import math
from collections import defaultdict
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:input()

"""========main code==============="""

x=ii()
lol=[1,2,3,4,5,6,7,8,9]
ans=9
if(x>9):
    for i in lol:
        k=str(i)
        a=int(k[len(k)-1])
        if(a-1>=0):
            lol.append(k+str(a-1))
            ans+=1
            if(ans==x):
                print(lol[x-1])
                break
        lol.append(k+str(a))
        ans+=1
        if(ans==x):
            print(lol[x-1])
            break
        if(a+1<=9):
            lol.append(k+str(a+1))
            ans+=1    
            if(ans==x):
                print(lol[x-1])
                break
else:
    print(lol[x-1])

Solution (Python):
import queue
K=int(input())
q = queue.Queue()

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

for j in range(0,K-1):
    x=q.get()
    
    xtail=x%10
    if xtail!=0:
        q.put(x*10+xtail-1)
    q.put(x*10+xtail)
    if xtail!=9:
        q.put(x*10+xtail+1)

print(q.get())

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

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    K = int(input())
    q = deque()
    for i in range(1, 10):
        if K == 1:
            print(i)
            exit()
        K -= 1
        q.append(i)
    while q:
        v = q.popleft()
        sv = int(str(v)[-1])
        for i in (-1, 0, 1):
            if 0 <= sv + i < 10:
                if K == 1:
                    print(v * 10 + sv + i)
                    exit()
                K -= 1
                q.append(v * 10 + sv + i)

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
K = int(input())
l = [i + 1 for i in range(0, 9)]
heapq.heapify(l)
count = 1
ans = 0
while count < K:
    x = heapq.heappop(l)
    l_digit = x % 10
    if l_digit != 0:
        heapq.heappush(l, 10 * x + l_digit - 1)
    heapq.heappush(l, 10 * x + l_digit)
    if l_digit != 9:
        heapq.heappush(l, 10 * x + l_digit + 1)
    count += 1
print(heapq.heappop(l))

Solution (Python):
from collections import deque

K = int(input())

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

for _ in range(K):
    v = q.popleft()

    if v % 10 != 0:
        q.append(10 * v + v % 10 - 1)

    q.append(10 * v + v % 10)

    if v % 10 != 9:
        q.append(10 * v + v % 10 + 1)

print(v)

Solution (Python):
from collections import deque


K = int(input())

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

for _ 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)

ans = d.popleft()
print(ans)

Solution (Python):
from collections import deque

K=int(input())

def bfs(k):
    queue = deque()
    for i in range(1, 10):
        queue.append(i)
    cnt = 1
    
    while queue:
        x = queue.popleft()
        if cnt == k:
            return x
        cnt += 1 
        last = x%10 
        if last > 0:
            queue.append(x*10+last-1)
        queue.append(x*10+last)
        if last < 9:
            queue.append(x*10+last+1)
            
print(bfs(K))

Solution (Python):
maxn = 100005

def solve(n):
	if n<=9:
		return n
	q = [0 for i in range(maxn)]
	front = 1
	rear = 0
	for i in range(1,10):
		rear += 1
		q[rear] = i
	cnt = 9
	while 1:
		u = q[front]
		front += 1
		if u%10 != 0:
			t = u*10 + u%10 -1
			rear += 1
			q[rear] = t
			cnt += 1
			if cnt==n:
				return t
		t = u*10 + u%10
		rear += 1
		q[rear] = t
		cnt += 1
		if cnt==n:
			return t;
		if u%10 != 9:
			t = u*10 + u%10 + 1
			rear += 1
			q[rear] = t
			cnt += 1
			if cnt==n:
				return t

print(solve(int(input())))

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

q = queue.Queue()

ret = K
number_of_operations = 9
for i in range( 1, number_of_operations + 1 ):
  q.put( i )

while number_of_operations < K:
  i = q.get()
  k = i % 10 
  if k != 0:
    ret = 10 * i + k - 1
    q.put( ret )
    number_of_operations += 1
    if number_of_operations == K:
      break
  ret = 10 * i + k
  q.put( ret )
  number_of_operations += 1
  if number_of_operations == K:
    break

  if k != 9:
    ret = 10 * i + k + 1
    q.put( ret )
    number_of_operations += 1

print( ret )

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

K = int(input())

for i in range(1,10):
    q.put(i)
    
for i in range(K):
    x = q.get()
    m = x % 10
    if not m == 0:
        q.put(x * 10 + (m-1))
    q.put(x * 10 + m)
    if not m == 9:
        q.put(x * 10 + (m+1))

print(x)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K = INT()

q = list(range(1, 10))
q = deque(q)

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

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

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

Solution (Python):
maxn = 100005

def solve(n):
	if n<=9:
		return n
	q = [0 for i in range(maxn)]
	front = 1
	rear = 0
	for i in range(1,10):
		rear += 1
		q[rear] = i
	cnt = 9
	while 1:
		u = q[front]
		front += 1
		if u%10 != 0:
			t = u*10 + u%10 -1
			rear += 1
			q[rear] = t
			cnt += 1
			if cnt==n:
				return t
		t = u*10 + u%10
		rear += 1
		q[rear] = t
		cnt += 1
		if cnt==n:
			return t;
		if u%10 != 9:
			t = u*10 + u%10 + 1
			rear += 1
			q[rear] = t
			cnt += 1
			if cnt==n:
				return t

print(solve(int(input())))

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

K = int(input())

d = []
d.append([1] * 10)

for i in range(1, 10):
    m = []
    if i != 9:
        for j in range(10):
            if not j:
                m.append(d[i - 1][j] + d[i - 1][j + 1])
            elif j == 9:
                m.append(d[i - 1][j - 1] + d[i - 1][j])
            else:
                m.append(d[i - 1][j - 1] + d[i - 1][j] + d[i - 1][j + 1])
    else:
        for j in range(4):
            if not j:
                m.append(d[i - 1][j] + d[i - 1][j + 1])
            elif j == 9:
                m.append(d[i - 1][j - 1] + d[i - 1][j])
            else:
                m.append(d[i - 1][j - 1] + d[i - 1][j] + d[i - 1][j + 1])
    d.append(m)

n = 0
for i, x in enumerate(d):
    for j, y in enumerate(x):
        if not j:
            continue
        else:
            if n + y >= K:
                break
            else:
                n += y
    else:
        continue
    break

ans = []
am = K - n
ans = str(j)
for x in reversed(range(i)):
    if j != 0 and j != 9:
        if am <= d[x][j - 1]:
            ans += str(j - 1)
            j -= 1
        elif am <= d[x][j - 1] + d[x][j]:
            ans += str(j)
            am -= d[x][j-1]
        else:
            ans += str(j + 1)
            am -= d[x][j-1] + d[x][j]
            j += 1
    elif j == 9:
        if am <= d[x][j - 1]:
            ans += str(j - 1)
            j -= 1
        else:
            ans += str(j)
            am -= d[x][j-1]
    else:
        if am <= d[x][j]:
            ans += str(j)
        else:
            ans += str(j + 1)
            am -= d[x][j]
            j += 1

print(ans)

Solution (Python):
import queue

K = int(input())

q = queue.Queue()

q.put(1)
q.put(2)
q.put(3)
q.put(4)
q.put(5)
q.put(6)
q.put(7)
q.put(8)
q.put(9)
x=0
while K>0:
    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)
    K-=1

print(x)

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

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

for i in range(K - 1):
    N = queue.pop(0)
    if i < K // 2.5:
        if N % 10 == 0:
            queue.append(N * 10)
            queue.append(N * 10 + 1)
        elif N % 10 == 9:
            queue.append(N * 10 + 8)
            queue.append(N * 10 + 9)
        else:
            queue.append(N * 10 + (N % 10 - 1))
            queue.append(N * 10 + N % 10)
            queue.append(N * 10 + (N % 10 + 1))

print(queue.pop(0))

Solution (Python):
k=int(input())
queue=[i for i in range(1,10)]
if k <10:
    print(k)
else:
    l=0
    while l+9 < k:
        x=queue.pop(0)
        if x%10 != 0:
            queue.append(10*x+x%10-1)
            l+=1
        if l+9==k:
            break
        queue.append(10*x+x%10)
        l+=1
        if l+9==k:
            break
        if x%10 != 9:
            queue.append(10*x+x%10+1)
            l+=1
    print(queue[-1])

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

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

for i in range(K - 1):
    N = queue.pop(0)
    if i < K // 2:
        if N % 10 == 0:
            queue.append(N * 10)
            queue.append(N * 10 + 1)
        elif N % 10 == 9:
            queue.append(N * 10 + 8)
            queue.append(N * 10 + 9)
        else:
            queue.append(N * 10 + (N % 10 - 1))
            queue.append(N * 10 + N % 10)
            queue.append(N * 10 + (N % 10 + 1))

print(queue.pop(0))

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

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

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

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

def FindOtvet(i, j, otv):
    if i == 0:
        return ''
    if j == 0:
        if (otv + D[i - 1][j]) < n:
            otv += D[i - 1][j]
            return str(j + 1) + FindOtvet(i - 1, j + 1, otv)
        else:
            return str(j) + FindOtvet(i - 1, j, otv)
    elif j == 9:
        if (otv + D[i - 1][j - 1]) < n:
            otv += D[i - 1][j - 1]
            return str(j) + FindOtvet(i - 1, j, otv)
        else:
            return str(j - 1) + FindOtvet(i - 1, j - 1, otv)
    else:
        if (otv + D[i - 1][j - 1]) < n:
            otv += D[i - 1][j - 1]
            if (otv + D[i - 1][j]) < n:
                otv += D[i - 1][j]
                return str(j + 1) + FindOtvet(i - 1, j + 1, otv)
            else:
                return str(j) + FindOtvet(i - 1, j, otv)
        else:
            return str(j - 1) + FindOtvet(i - 1, j - 1, otv)

arr = []
if n < 10:
    print(n)
    exit()
for i in range(10):
    arr.append(1)
D.append(arr)
totalSum = 9
i = 1
respI = 0
respJ = 0
while respI == 0 and respJ == 0:
    arr = []
    for j in range(10):
        if j == 0:
            arr.append(D[i - 1][j] + D[i - 1][j + 1])
        elif j < 9:
            arr.append(D[i - 1][j - 1] + D[i - 1][j] + D[i - 1][j + 1])
        else:
            arr.append(D[i - 1][j - 1] + D[i - 1][j])
        if j > 0:
            if (totalSum + arr[j]) >= n:
                respI = i
                respJ = j
                break
            totalSum += arr[j]
    D.append(arr)
    i += 1
respStr = str(respJ)
print(respStr + FindOtvet(respI, respJ, totalSum))

Solution (Python):
from collections import deque
K = int(input())
q = deque([[1],[2],[3],[4],[5],[6],[7],[8],[9]])
cnt = 0
while cnt != K:
    nums = q.popleft()
    last = nums[-1]
    if last == 9:
        tmp = nums.copy()
        tmp.append(8)
        q.append(tmp)

        tmp = nums.copy()
        tmp.append(9)
        q.append(tmp)
    elif last == 0:
        tmp = nums.copy()
        tmp.append(0)
        q.append(tmp)

        tmp = nums.copy()
        tmp.append(1)
        q.append(tmp)
    else:
        tmp = nums.copy()
        tmp.append(last-1)
        q.append(tmp)

        tmp = nums.copy()
        tmp.append(last)
        q.append(tmp)

        tmp = nums.copy()
        tmp.append(last+1)
        q.append(tmp)

    cnt += 1
ans = 0
l = len(nums)
for i in range(l):
    ans += nums[i]*10**(l-i-1)
print(ans)

Solution (Python):
K=int(input())
A=[1,2,3,4,5,6,7,8,9]+[0]*10*K
i=9
j=0
while i<K:
    if A[j]%10!=0 and A[j]%10!=9:
        A[i]=10*A[j]+A[j]%10-1;i+=1
        A[i]=10*A[j]+A[j]%10;i+=1
        A[i]=10*A[j]+A[j]%10+1;i+=1
    elif A[j]%10==0:
        A[i]=10*A[j]+A[j]%10;i+=1
        A[i]=10*A[j]+A[j]%10+1;i+=1
    else:
        A[i]=10*A[j]+A[j]%10-1;i+=1
        A[i]=10*A[j]+A[j]%10;i+=1
    j+=1
print(A[K-1])

Solution (Python):




from collections import deque
k = int(input())
arr = set()
for i in range(1, 10):
    arr.add(i)

for i in range(1, 10):
    tmp_arr = deque()
    tmp_arr.append(str(i))
    while len(tmp_arr) > 0:
        cur = tmp_arr.popleft()
        arr.add(int(cur))
        if len(cur) == len("3234566667"):
            next
        target = int(cur[-1])
        for i in range(0, 10):
            if abs(target - i) <= 1:
                next_num = cur + str(i)
                if int(next_num) > 3234566667:
                    continue
                tmp_arr.append(next_num)
arr = sorted(arr)
print(arr[k - 1])

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

K = I()
que = deque([1,2,3,4,5,6,7,8,9])
lst = [1,2,3,4,5,6,7,8,9]
cnt = 9
while cnt < K:
    s = que.popleft()
    t = int(str(s)[-1])
    for i in range(max(0,t-1),min(10,t+2)):
        cnt += 1
        lst.append(int(str(s)+str(i)))
        que.append(int(str(s)+str(i)))
print(lst[K-1])

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

Solution (Python):
from collections import deque

K=int(input())

todo=deque(list(map(str,range(1,10))))

count=0

while todo:
    num=todo.popleft()
    count+=1

    if count==K:
        print(num)
        exit()
    
    base=int(num[-1])
    n1=base-1
    if n1!=-1:
        todo.append(num+str(n1))
    
    n2=base
    todo.append(num+str(n2))

    n3=base+1

    if n3!=10:
        todo.append(num+str(n3))

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

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

Solution (Python):
from collections import deque
k = int(input())
q = deque(list(range(1, 10)))

for _ in range(k-1):
    d = q.popleft()

    if d%10 > 0:
        q.append(d*10 + d%10 - 1)

    q.append(d*10 + d%10)
    
    if d%10 < 9:
        q.append(d*10 + d%10 + 1)

print(q.popleft())

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

Solution (Python):
import sys

def main(argv):
    k = int(sys.stdin.readline().rstrip("\n"))
    if k < 10:
        return print(k)
    d = {i: [i] for i in range(10)}

    counter = 9
    n = 1
    while counter < k:
        next_d = {}
        candidates = d[0]
        candidates.extend(d[1])
        next_d[0] = sorted([c for c in set(candidates)])
        for i in range(1, 10):
            candidates = d[i - 1]
            candidates.extend(d[i])
            candidates.extend(d.get(i + 1, []))
            next_d[i] = sorted([i * (10 ** n) + c for c in set(candidates)])
            n_candidates = len(next_d[i])
            if (counter + n_candidates) >= k:
                print(next_d[i][k - counter - 1])
                counter += n_candidates
                break
            counter += n_candidates
        d = next_d
        n += 1
    return 0


if __name__ == "__main__":
    sys.exit(main(sys.argv))

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

Solution (Python):
K=int(input())
from collections import deque
def bfs(k):
    queue = deque()
    for i in range(1, 10):
        queue.append(i)
    cnt = 1
    while queue:
        x = queue.popleft()
        if cnt == k:
            return x
        cnt += 1
        last = x%10
        if last > 0:
            queue.append(x*10+last-1)
        queue.append(x*10+last)
        if last < 9:
            queue.append(x*10+last+1)
print(bfs(K))

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

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

Solution (Python):
from collections import deque

from collections import deque


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

    q = deque()

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

    while True:
        v = q.popleft()
        K -= 1
        if K == 0:
            print(v)
            exit()
        u = v % 10
        nv = v * 10 + u

        if u == 0:
            q.append(nv)
            q.append(nv + 1)
        elif u == 9:
            q.append(nv - 1)
            q.append(nv)
        else:
            q.append(nv - 1)
            q.append(nv)
            q.append(nv + 1)


main()

Solution (Python):

def main():
    from collections import deque
    K = int(input())

    q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
    cnt = 0
    while q:
        x = q.popleft()
        cnt += 1
        if cnt == K:
            print(x)
            return

        y = x % 10
        z = 10*x + y
        if y != 0:
            q.append(z-1)
        q.append(z)
        if y != 9:
            q.append(z+1)


if __name__ == '__main__':
    main()

Solution (Python):
import queue

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

ans = 0
for i in range(N):
    ans = q.get()
    m = ans % 10
    if ans % 10 != 0:
        q.put(ans * 10 + m - 1)
    q.put(ans * 10 + m)
    if ans % 10 != 9:
        q.put(ans * 10 + m + 1)

print(ans)

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

from collections import deque
queue = deque(range(1,10))
count = 0

while count < k:
    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)
    count += 1
    
print(tmp)

Solution (Python):

N = int(input())

if N <= 12:
    print(N)
else:
    str_ans = "12"
    counter = 12
    while counter < N:
        len_ans = len(str_ans)
        low_nine_num = 0
        for i in range(len_ans):
            if str_ans[len_ans - i - 1] == "9":
                low_nine_num += 1
            else:
                break
        if low_nine_num == len_ans:
            str_ans = "1" + "0" * len_ans
        else:
            chenged_top_num = -1
            low_digit_num = -1
            if low_nine_num == len_ans - 1:
                chenged_top_num = int(str_ans[len_ans - low_nine_num - 1])
                low_digit_num = len_ans - 1
            else:
                for i in range(len_ans - low_nine_num):
                    if i == len_ans - low_nine_num - 1 :
                        if chenged_top_num == -1:
                            chenged_top_num = int(str_ans[0])
                            low_digit_num = len_ans - 1
                    else:
                        compare_high_num = int(str_ans[-1 * (i + 2 + low_nine_num)])
                        compare_low_num = int(str_ans[-1 * (i + 1 + low_nine_num)])
                        if compare_high_num - compare_low_num != 0 and compare_high_num - compare_low_num != 1:
                            chenged_top_num = compare_high_num
                            low_digit_num = i + 1 + low_nine_num
    
                        else:
                            chenged_top_num = compare_low_num
                            low_digit_num = i + low_nine_num
    
                            break

                            
            temp_str_ans = str_ans[:len_ans - low_digit_num - 1] 
            temp_str_ans += str(chenged_top_num + 1)
            for i in range(low_digit_num):
                temp_str_ans += str(max(chenged_top_num - i, 0))
            str_ans = temp_str_ans
        
        counter += 1

    
    print(int(str_ans))

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

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

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)