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 math
import queue

def readInt():
	return int(input())

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

def readChars():
	return input().split()


q = queue.Queue()

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

n = readInt()

for i in range(1,100001):
	a = str(q.get())
	b = int(a[-1])
	if b!=0:
		q.put(int(a+str(b-1)))
	q.put(int(a+str(b)))
	if b!=9:
		q.put(int(a+str(b+1)))	
	if i==n:
		print(int(a))
		break

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

Solution (Python):
from collections import deque
import sys

k = int(input())

q = deque([i for i in range(1, 10)])
if k <= 9:
    print(q[k-1])
    sys.exit()

cnt = 0
while True:
    if cnt == k:
        print(x)
        break
    x = q.popleft()
    m = x % 10
    if m == 0:
        q.extend([10*x + m, 10*x + (m+1)])
    elif m == 9:
        q.extend([10*x + (m-1), 10*x + m])
    else:
        q.extend([10*x + (m-1), 10*x + m, 10*x + (m+1)])
    cnt += 1

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

INF = float('inf')


if __name__ == '__main__':
    K = int(input())
    q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

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

    counter = 0
    while True:
        counter += 1
        x = q.popleft()
        amari = x % 10
        if counter != K:
            if amari > 0:
                q.append(x * 10 + (amari - 1))
            q.append(x * 10 + amari)
            if amari < 9:
                q.append(x * 10 + (amari + 1))
        else:
            print(x)
            exit()

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

Solution (Python):
k=int(input())
q=[i for i in range(1,10)]
ans=0
c=0
for i in range(k):
    ans=q.pop(0)
    p=10*ans+int(str(ans)[-1])
    if(p%10!=0):q.append(p-1)
    q.append(p)
    if(p%10!=9):q.append(p+1)
    if(i+len(q)>k):break
    c+=1
for i in range(k-c-1):
    ans=q.pop(0)

print(ans)

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

a = list(range(1, 10))
i = 0
while len(a) < K:
  A = []
  for j in range(3):
    n = str(a[i])
    if j == 0 and int(n[-1]) - 1 >= 0:
      A.append(int(n + str(int(n[-1]) - 1)))
    elif j == 1:
      A.append(int(n + n[-1]))
    elif j == 2 and int(n[-1]) + 1 < 10:
      A.append(int(n + str(int(n[-1]) + 1)))
  a += A
  i += 1
print(a[K-1])

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

INF = float('inf')


if __name__ == '__main__':
    K = int(input())
    q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

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

    counter = 0
    while True:
        counter += 1
        x = q.popleft()
        amari = x % 10
        if counter != K:
            if amari == 0:
                q.append(x * 10 + amari)
                q.append(x * 10 + (amari + 1))
            elif amari == 9:
                q.append(x * 10 + (amari - 1))
                q.append(x * 10 + amari)
            else:
                q.append(x * 10 + (amari - 1))
                q.append(x * 10 + amari)
                q.append(x * 10 + (amari + 1))
        else:
            print(x)
            exit()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

x = int(input())

def Add(count, list, change, check):
    
    if count <= 0:
        print(''.join(map(str, list)))
        return

    
    if all(item == 9 for item in list):
        list = [0 for y in range(0, len(list) + 1)]
        list[0] = 1
        Add(count - 1, list, len(list) - 1, max(0, len(list) - 2))
        return

    
    if list[change] <= list[check] and list[change] < 9:
        list[change] += 1
        Clean(list, change + 1)
        Add(count - 1, list, len(list) - 1, max(0, len(list) - 2))
        return

    
    else:
        Add(count, list, change - 1, max(0, change - 2))
        return


def Clean(list, change):
    if change >= len(list):
        return
    for x in range(change, len(list)):
        list[x] = max(0, list[max(0, x - 1)] - 1)


Add(x, [0], 0, 0)

Solution (Python):
k = int(input())
dp = [[] for _ in range(k)]
dp[0] = [1,2,3,4,5,6,7,8,9]

if k <= 9:
    print(k)
else:
    total = 0
    i = 0
    while total + len(dp[i]) < k:
        total += len(dp[i])
        for j in dp[i]:
            x = j%10
            if x == 0:
                dp[i+1].append(j*10)
                dp[i+1].append(j*10+1)
            elif x == 9:
                dp[i+1].append(j*10+8)
                dp[i+1].append(j*10+9)
            else:
                dp[i+1].append(j*10+x-1)
                dp[i+1].append(j*10+x)
                dp[i+1].append(j*10+x+1)
        i += 1
    print(dp[i][k-total-1])

Solution (Python):


'''
100000
99990
90000
'''

K = int(input())




c = 1

for i in range(K -1):
    str_c = list(str(c))
    str_c = [int(i) for i in str_c][::-1]

    keta = len(str_c)
    
    

    if set(str_c) == set([9]):
        c = c + 1
        continue

    for ket in range(keta):
        
        if ket == keta - 1:
            str_c[ket] += 1

            for j in range(ket):
                
                if str_c[ket - j] == 0:
                    str_c[ket - j - 1] = 0
                else:
                    str_c[ket - j - 1] = str_c[ket - j] - 1

            str_c = [str(i) for i in str_c][::-1]
            c = int(''.join(str_c))
            break

        if str_c[ket] == str_c[ket + 1] + 1:
            continue

        
        if abs(str_c[ket] - str_c[ket + 1]) <= 1:
            if str_c[ket] < 9:
                str_c[ket] += 1
                for j in range(ket):
                    if str_c[ket - j] == 0:
                        str_c[ket - j - 1] = 0
                    else:
                        str_c[ket - j - 1] = str_c[ket - j] - 1
                str_c = [str(i) for i in str_c][::-1]
                c = int(''.join(str_c))
                break


print(c)

Solution (Python):



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



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

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

    if K <= 10:
        print(K)
        sys.exit()

    count = 9

    for i in range(2,11):
        for j in pre:
            for k in range(-1,2):
                d = j % 10 + k
                if (d < 0) | (d > 9):
                    continue
                temp = j * 10 + d
                now.append(temp)
                count += 1
                if count == K:
                    print(temp)
                    sys.exit()
        pre = now



main()

Solution (Python):
from collections import deque

k = int(input())

q = deque(range(1, 10))

for i in range(k):
    t = q.popleft()

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

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

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

Solution (Python):
import sys
input=sys.stdin.readline
K = int(input())
LEN = 32345666







def enqueue(Q,x,tail):
    Q[tail] = x       
    if tail+1 == LEN: 
        tail = 0
    else:
        tail += 1
    return tail
def dequeue(Q,head):
    x = Q[head]
    if head+1 == LEN:
        head = 0
    else:
        head += 1
    return x,head
Q = [1,2,3,4,5,6,7,8,9]+[0]*(LEN-9)
head = 0
tail = 9

i = 0
while i < K:
    x,head = dequeue(Q,head)
    if x % 10 == 0:
        tail = enqueue(Q,10*x,tail)
        tail = enqueue(Q,10*x+1,tail)
    elif x % 10 == 9:
        tail = enqueue(Q,10*x+8,tail)
        tail = enqueue(Q,10*x+9,tail)
    else:
        y = x%10
        tail = enqueue(Q,10*x+y-1,tail)
        tail = enqueue(Q,10*x+y,tail)
        tail = enqueue(Q,10*x+y+1,tail)
    i += 1
print(x)

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

a = list(range(1,10))

while True:
    if(k<=len(a)):
        print(a[k-1])
        exit()
    k-=len(a)
    old = a
    a = []
    for x in old:
        for i in range(-1,2):
            d = x%10+i
            if d<0 or d>9:
                continue
            nx = x*10+d
            a.append(nx)

Solution (Python):
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)


inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""


from collections import deque, defaultdict, Counter


def main():
    """
    N = int(input())
    Nr = math.sqrt(N)
    Nr = int(Nr)+1
    count = 0
    for i in range(2, Nr):

        if N % i == 0:
            M = N
            while M % i != 0:
                M = M // i

            if M < i:
                break
            else:
                ans = M % i
                if ans == 1:
                    count += 1
        else:
            ans = N % i
            if ans == 1:
                count += 1
    print(count+2)

    """
    K = int(input())
    count = 0
    q = deque()
    for i in range(1, 10):
        q.append(i)
    while q:
        num = q.popleft()
        count += 1
        if count == K:
            ans = num
            break
        mod10 = num % 10
        if mod10 != 0:
            q.append(10*num + mod10 - 1)
        q.append(10*num + mod10)
        if mod10 != 9:
            q.append(10*num + mod10 + 1)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



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



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

    queue = deque()

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

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

    print(x)



main()

Solution (Python):
k=int(input())
a=[0,0,0,0,0,0,0,0,0,0]
keta=1
for i in range(k):
  unta=-1
  a[0]+=1
  for j in range(keta):
    if (j+1<keta and a[j]>a[j+1]+1) or a[j]>=10:
      a[j+1]+=1
      unta=j
  if unta>-1:
    if unta==keta-1:
      keta+=1
    for j in range(unta+1):
      a[unta-j]=max(a[unta-j+1]-1,0)

ans=0
for i in range(10):
  ans+=a[i]*(10**i)
print(str(ans))

Solution (Python):
K=int(input())
if K<10:
  print(K);exit()
def dfs(v,n):
  u=[]
  for x in v:
    for d in [-1,0,1]:
      if(0<=x%10+d<=9):
        u.append(x*10+x%10+d)
  if(n+len(u)>=K):
    u.sort()
    print(u[K-n-1])
  else:
    dfs(u,n+len(u))
dfs(range(1,10),9);

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):
                    if i == len_ans - 1 :
                        if chenged_top_num == -1:
                            chenged_top_num = int(str_ans[0])
                            low_digit_num = len_ans - 1
                    elif str_ans[-1 * (i + 1)] == "9":
                        continue
                    else:
                        compare_high_num = int(str_ans[-1 * (i + 2)])
                        compare_low_num = int(str_ans[-1 * (i + 1)])
                        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
    
                        else:
                            chenged_top_num = compare_low_num
                            low_digit_num = i
    
                            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):
from collections import deque
from copy import copy,deepcopy
from itertools import permutations,combinations
from pprint import pprint

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

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)

k = int(input())

def bfs(k):
    ls = []
    q = deque()
    for i in range(1,10):
        q.append(str(i))
    while q:
        tmp = q.popleft()
        ls.append(tmp)
        if len(ls)==k:
            break
        n = int(tmp[-1])
        if n==0:
            tmp_new = tmp + "0"
            q.append(tmp_new)
            tmp_new = tmp + "1"
            q.append(tmp_new)
        elif 0<n<9:
            tmp_new = tmp + str(n-1)
            q.append(tmp_new)
            tmp_new = tmp + str(n)
            q.append(tmp_new)
            tmp_new = tmp + str(n+1)
            q.append(tmp_new)
        elif n==9:
            tmp_new = tmp + "8"
            q.append(tmp_new)
            tmp_new = tmp + "9"
            q.append(tmp_new)
        else:
            print("Error")
    return ls

ls = bfs(k)

print(ls[k-1])

Solution (Python):
import queue

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

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

    count = 0
    while True:
        count = count+1
        a = q.get()

        if count == K:
            break

        tail = int(str(a)[-1])
        for i in range(10):
            if abs(tail-i) > 1:
                continue
            q.put(int(str(a)+str(i)))

    print(a)

if __name__ == "__main__":
    main()

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

Solution (Python):
k=int(input())
A=[1,2,3,4,5,6,7,8,9]
head=0
tail=len(A)
for z in range(10):
    for i in range(head,tail):
        now=A[i]%10
        ad=A[i]*10
        if now!=0:
            A.append(ad+now-1)
        if now!=9:
            A.append(ad+now+1)
        A.append(ad+now)
    head=tail
    tail=len(A)
A.sort()
print(A[k-1])

Solution (Python):
from collections import deque

def resolve():
    K = int(input())
    q = deque(range(1, 10))

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


if __name__ == "__main__":
    resolve()

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

INF = float('inf')


if __name__ == '__main__':
    K = int(input())
    q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

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

    counter = 0
    while True:
        counter += 1
        x = q.popleft()
        if counter != K:
            if x % 10 == 0:
                q.append(x * 10)
                q.append(x * 10 + 1)
            elif x % 10 == 9:
                q.append(x * 10 + 8)
                q.append(x * 10 + 9)
            else:
                q.append(x * 10 + (x % 10 - 1))
                q.append(x * 10 + (x % 10))
                q.append(x * 10 + (x % 10 + 1))
        else:
            print(x)
            exit()

Solution (Python):
from collections import deque
K = int(input())
q = deque(range(1, 10))
for _ 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)
ans = q.popleft()
print(ans)

Solution (Python):
import sys
from collections import deque

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

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



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

Solution (Python):
k=int(input())
lunlun=[None for _ in range(100)]
lunlun[0]=(1,2,3,4,5,6,7,8,9)
for i in range(0,10):
  tmp=[]
  for j in lunlun[i]:
    s=j%10
    if s==0:
      tmp+=j*10+0,
      tmp+=j*10+1,
    elif s==9:
      tmp+=j*10+8,
      tmp+=j*10+9,
    else:
      tmp+=j*10+s-1,
      tmp+=j*10+s,
      tmp+=j*10+s+1,
  lunlun[i+1]=tuple(tmp)
L=[]
for i in range(0,10):
  for j in lunlun[i]:
    L+=j,
print(L[k-1])

Solution (Python):
from collections import deque


def calc_next_ones_places(last_ones_place):
    """次の Lunlun数 の一の位の数を返す"""
    if last_ones_place == 0:
        return [last_ones_place, last_ones_place+1]
    elif last_ones_place == 9:
        return [last_ones_place-1, last_ones_place]
    else:
        return [last_ones_place-1, last_ones_place, last_ones_place+1]


def calc_k_th_lunlun_num(k):
    """
    Kが10以上の時、K番目のLunlun数を計算する
    """
    lunlun_num_queue = deque()

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

    iterate_num = 9
    while True:
        last_lunlun_num = lunlun_num_queue.popleft()
        last_ones_place = str(last_lunlun_num)[-1]
        next_ones_places_list = calc_next_ones_places(int(last_ones_place))
        for next_ones_place in next_ones_places_list:
            lunlun_num = 10*last_lunlun_num + next_ones_place
            lunlun_num_queue.append(lunlun_num)

            iterate_num += 1
            if iterate_num == k:
                return lunlun_num


def main():
    K = int(input())
    if K <= 9:
        print(K)
    else:
        k_th_lunlun_num = calc_k_th_lunlun_num(K)
        print(k_th_lunlun_num)


main()

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

que = deque([i for i in range(1, 10)])
for _ in range(k - 1):
    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)
ans = que.popleft()
print(ans)

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

dig = 10

dp = [[0 for _ in range(10)] for _ in range(dig + 1)]


for j in range(0, 10):
    dp[1][j] = 1 


for i in range(2, dig + 1): 
    dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
    for j in range(1, 9):
        
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1]
    dp[i][9] = dp[i - 1][8] + dp[i - 1][9]



ac = 0
for i in range(1, dig + 1):
    for j in range(1, 10):
        ac += dp[i][j]
        if ac >= K:
            ans = j * (10 ** (i - 1))
            break
    else:
        continue
    break


rem = K - ac + dp[i][j]
while i > 1:
    if j == 0: 
        jlist = [0, 1]
    elif j == 9: 
        jlist = [8, 9]
    else:  
        jlist = [j - 1, j, j + 1]

    for j in jlist:
        if dp[i - 1][j] < rem:
            rem -= dp[i - 1][j]
        else:
            break
    i -= 1
    ans += j * 10 ** (i - 1)

print(ans)

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

for i in range(M):
    X = []
    for n in L[-1]:
        t = n % 10
        if t == 0:
            X.append(n * 10 + t)
            X.append(n * 10 + t + 1)
        elif t == 9:
            X.append(n * 10 + t - 1)
            X.append(n * 10 + t)
        else:
            X.append(n * 10 + t- 1)
            X.append(n * 10 + t)
            X.append(n * 10 + t + 1)
    L.append(X)

L2 = []
for i in range(len(L)):
    L2 += L[i]

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

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

Solution (Python):
k=int(input())
ans=[i for i in range(1,10)]
def dfs(x):
    if x>=3234566667:
        return
    for i in range(max(0,x%10-1),min(10,x%10+2)):
        ans.append(10*x+i)
        dfs(10*x+i)
for i in range(1,10):
    dfs(i)
print(sorted(ans)[k-1])

Solution (Python):

import sys
global cnt1


def bts(A, cnt, max):
    
    if cnt == max:
        global cnt1
        cnt1 = cnt1+1
        if cnt1 == K:
            print(A)
            sys.exit()
        return
    cnt = cnt+1
    if A % 10 == 0:
        bts(A*10+(A % 10), cnt, max)
        bts(A*10+(A % 10)+1, cnt, max)
    elif A % 10 == 9:
        bts(A*10+(A % 10)-1, cnt, max)
        bts(A*10+(A % 10), cnt, max)
    else:
        bts(A*10+(A % 10)-1, cnt, max)
        bts(A*10+(A % 10), cnt, max)
        bts(A*10+(A % 10)+1, cnt, max)


K = int(input())

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

cnt1 = 0
for k in range(1, 11):
    for i in range(len(A)):
        bts(A[i], 1, k)

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

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

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 collections import deque

k = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]
queue = deque(queue)
cnt = 0
while cnt < k:
    cnt += 1
    a = queue.popleft()
    hitoketa = a % 10
    kouho = [hitoketa - 1, hitoketa, hitoketa + 1]
    for b in kouho:
        if b >= 0 and b <= 9:
            queue.append(10 * a + b)
print(a)

Solution (Python):
import queue

k = int(input())
a = queue.Queue()
for i in range(9):
    a.put(i + 1)
for i in range(k):
    test = a.get()
    temp = test % 10
    if temp == 0:
        a.put(test * 10)
        a.put(test * 10 + 1)
    elif temp == 9:
        a.put(test * 10 + 8)
        a.put(test * 10 + 9)
    else:
        a.put(test * 10 + temp - 1)
        a.put(test * 10 + temp)
        a.put(test * 10 + temp + 1)
print(test)

Solution (Python):
from collections import deque

k = int(input())

d = [-1,0,1]

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

cnt = 0
while que:
    p = que.popleft()
    cnt += 1
    if cnt == k:
        print(p)
        break
    for i in d:
        if 0 <= int(str(p)[-1]) + i <= 9:
            que.append(int(str(p) + str(int(str(p)[-1]) + i)))

Solution (Python):
import queue

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

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

for i in range(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)

print(x)

Solution (Python):
from collections import deque

K = int(input())

q = deque(range(1, 10))

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

print(x)

Solution (Python):
from queue import Queue

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

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

for i in ans:
    if len(ans) > K:
        break
    if i%10 == 0:
        ans.append(i*10+i%10)
        ans.append(i*10+i%10+1)
    elif i%10 == 9:
        ans.append(i*10+i%10-1)
        ans.append(i*10+i%10)
    else:
        ans.append(i*10+i%10-1)
        ans.append(i*10+i%10)
        ans.append(i*10+i%10+1)
    
print(ans[K-1])

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

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

for i in range(k):
    num = lst[count]
    if num%10!=0:
        lst.append(num*10+num%10-1)
    lst.append(num*10+num%10)
    if num%10!=9:
        lst.append(num*10+num%10+1)
    count += 1

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 not q.empty():
  c += 1
  x = q.get()
  if c == k:
    print(x)
    break
  y = x%10
  if y != 0:
    q.put(10*x+y-1)
  q.put(10*x+y)
  if y != 9:
    q.put(10*x+y+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):
    p = q.popleft()
    r = p % 10
    if r != 0:
        q.append(10 * p + r - 1)
    q.append(10 * p + r)
    if r != 9:
        q.append(10 * p + r + 1)
print(p)

Solution (Python):
from queue import Queue

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

Solution (Python):
from collections import deque

K=int(input())
q=deque()
for i in range(1,10):
    q.append(str(i))

while K>0:
    n=q.popleft()
    t=int(n[-1])
    K-=1

    for i in range(max(0,t-1),min(9,t+1)+1):
        q.append(n+str(i))

print(n)

Solution (Python):
k=int(input())
unta=[[],[],[],[],[],[],[],[],[],[],[],[]]
unta[1]=["1","2","3","4","5","6","7","8","9"]
for keta in range(2,12):
	for i in range(len(unta[keta-1])):
		if unta[keta-1][i][keta-2]=="0":
			unta[keta].append(unta[keta-1][i]+"0")
			unta[keta].append(unta[keta-1][i]+"1")
		elif unta[keta-1][i][keta-2]=="9":
			unta[keta].append(unta[keta-1][i]+"8")
			unta[keta].append(unta[keta-1][i]+"9")
		else:
			unta[keta].append(unta[keta-1][i]+str(int(unta[keta-1][i][keta-2])-1))
			unta[keta].append(unta[keta-1][i]+unta[keta-1][i][keta-2])
			unta[keta].append(unta[keta-1][i]+str(int(unta[keta-1][i][keta-2])+1))
unchi=[]
for i in range(11):
	unchi+=unta[i]
print(unchi[k-1])

Solution (Python):
k=int(input())
t=[2]+[3]*8+[2]
g=[[1]+[0for i in range(100000)]for j in range(10)]
def f(x,y):
    if g[x][y]!=0:
        return g[x][y]
    else:
        p=0
        for i in range(x-1,x+2):
            if 0<=i<10:
                p+=f(i,y-1)
        g[x][y]=p
        return p
c=0
for i in range(100000):
    for j in range(1,10):
        if c+f(j,i)>=k:
            p=str(j)
            po=j
            for h in range(i-1,-1,-1):
                for w in range(po-1,po+2):
                    if 0<=w<10:
                        if c+f(w,h)>=k:
                            p+=str(w)
                            po=w
                            break
                        c+=f(w,h)
            print(p)
            exit()
        c+=f(j,i)

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

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

while num<k:
    i = q.get()
    l = i%10
    if l!=0:
        q.put(i*10+l-1)
    q.put(i*10+l)
    if l!=9:
        q.put(i*10+l+1)
    num += 1

print(i)

Solution (Python):
from collections import deque

k = int(input())
count = 0
q = deque(range(1,10))

while count < k:
    l = q.popleft()
    resid = l % 10
    if resid != 0: q.append(l*10 + resid - 1)

    q.append(l*10 + resid)
    
    if resid != 9: q.append(l*10 + resid + 1)
    
    count += 1

print(l)

Solution (Python):
from collections import deque
import sys

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))

K = read_int()[0]

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

def solve():
    for _ 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))
    return q.popleft()

if __name__ == "__main__":
    print(solve())

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

def dfs(n):
    if n > 3234566667:
        return
    ans.append(n)
    if n % 10 != 0:
        dfs(n * 10 + (n % 10) - 1)
    dfs(n * 10 + (n % 10))
    if n % 10 != 9:
        dfs(n * 10 + (n % 10) + 1)

N = int(input())
ans = []
for i in range(1, 10):
    dfs(i)
ans.sort()
print(ans[N - 1])

Solution (Python):

K = int(input())
st_lib = '0123456789'

memory = []
def search(s):
    if len(s) == 11:
        memory.append(int(s))
        return
    last_s = int(s[-1])
    if s == '0' * len(s):
        patterns = st_lib
    else:
        patterns = st_lib[max([last_s-1, 0]):last_s+2]
    for next in patterns:
        search(s+next)

if __name__ == '__main__':
    search('0')
    memory = sorted(memory)
    print(memory[K])

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

k = ni()

def bfs():
    q = deque()
    for n in range(1, 10):
        q.append(n)
    i = 1
    while len(q):
        p = q.popleft()
        if i == k:
            return p
        i += 1
        if p % 10 != 0:
            q.append(p * 10 + (p % 10 - 1))
        q.append(p * 10 + p % 10)
        if p % 10 != 9:
            q.append(p * 10 + (p % 10 + 1))

print(bfs())