Problem:
 Score : 400 points    Problem Statement  A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:   In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1 .   For example, 1234 , 1 , and 334 are lunlun numbers, while none of 31415 , 119 , or 13579 is.  You are given a positive integer K . Find the K -th smallest lunlun number.      Constraints   1 \leq K \leq 10^5  All values in input are integers.         Input  Input is given from Standard Input in the following format:  K       Output  Print the answer.        Sample Input 1 15      Sample Output 1 23  We will list the 15 smallest lunlun numbers in ascending order:  1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 21 , 22 , 23 . Thus, the answer is 23 .       Sample Input 2 1      Sample Output 2 1       Sample Input 3 13      Sample Output 3 21       Sample Input 4 100000      Sample Output 4 3234566667  Note that the answer may not fit into the 32 -bit signed integer type.

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

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

for i in lunlun:
    stri = str(i)
    if stri[-1] == '0':
        tmp = stri + '0' 
        lunlun.append(int(tmp))
        tmp = stri + '1'
        lunlun.append(int(tmp))
        if len(lunlun) >= k:
            print(lunlun[k-1])
            exit()
    elif stri[-1] == '9':
        tmp = stri + '8'
        lunlun.append(int(tmp))
        tmp = stri + '9'
        lunlun.append(int(tmp))
        if len(lunlun) >= k:
            print(lunlun[k-1])
            exit()
    else:
        tmp = stri + str(int(stri[-1]) - 1)
        lunlun.append(tmp)
        tmp = stri + str(int(stri[-1]))
        lunlun.append(tmp)
        tmp = stri + str(int(stri[-1]) + 1)
        lunlun.append(tmp)
        if len(lunlun) >= k:
            print(lunlun[k-1])
            exit()

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

def generator(n):
    end = n % 10
    for i in range(-1,2):
        i += end
        if 0 <= i <= 9:
            yield l*10+i

ans = list(range(1,10))

while len(ans) < K:
    l = q.get()
    for i in generator(l):
        q.put(i)
        ans.append(i)

print(ans[K-1])

Solution (Python):

from collections import deque

K = int(input())
ans = 0
count = 0
queue = deque()
for i in range(1, 10):
    queue.append(i)

while True:
    count += 1
    a = queue.popleft()
    if count == K:
        print(a)
        exit(0)

    for i in range(-1, 2):
        d = a % 10 + i
        if d < 0 or d > 9:
            continue
        queue.append(a * 10 + d)

Solution (Python):
import collections
k=int(input())
if k<=9:
    print(k)
else:
    k-=9
    l =list(range(9,0,-1))
    
    q = collections.deque(l)
    counter=0
    while counter<k:
        x=q.pop()
        xrem=x%10
        if xrem!=0:
            q.appendleft(10*x+xrem-1)
            counter+=1
            if counter>=k:
                break
        q.appendleft(10*x+xrem)
        counter+=1
        if counter>=k:
                break
        if xrem!=9:
            q.appendleft(10*x+xrem+1)
            counter+=1
    print(q[0])

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

cnt = 9
ans = 0
while True:
    if K <= cnt:
        print(K)
        break
    l = q.get()
    end = l % 10
    for i in range(-1,2):
        i += end
        if 0 <= i <= 9:
            q.put(l*10+i)
            cnt += 1
            if cnt == K:
                ans = l*10+i

    if cnt >= K:
        print(ans)
        break

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

que = deque(map(str, range(1, 10)))
while K > 1:
    n = que.popleft()
    K -= 1
    R = int(n[-1])
    for r in (R - 1, R, R + 1):
        if 0 <= r <= 9:
            que.append(n + str(r))

print(que[0])

Solution (Python):
def main():
    k = int(input())
    lunluns = [i for i in range(1, 10)]
    if k <= len(lunluns):
        print(lunluns[k - 1])
        return

    while True:
        if k <= len(lunluns):
            print(lunluns[k - 1])
            return
        k -= len(lunluns)
        olds = lunluns
        lunluns = []
        for old in olds:
            for i in (-1, 0, 1):
                digit_next = old % 10 + i
                if digit_next < 0 or digit_next > 9:
                    continue
                new = old * 10 + digit_next
                lunluns.append(new)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


def solve():

    K = int(input())

    dq = deque()
    
    for i in range(9):
        dq.append(i+1)

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

    print(num)


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque

K = int(input())

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

while q:
  e = q.popleft()
  counter += 1 
  
  if counter >= K:
    print(e)
    break
  
  for i in [-1, 0, 1]:
    d = e % 10 + i
    if 0 <= d <= 9:
      q.append(e * 10 + d)

Solution (Python):



from collections import deque

def main():
    k = int(input())
    lst = []
    bfs("",k,lst)
    print(lst[k-1])


def bfs(s,k,lst=[]):
    d = deque()
    for c in "0123456789":
        d.append(c)
    while d:
        if len(lst) > k:
            return
        now = d.popleft()
        if now=="0":
            continue
        lst.append(now)
        for nxt in [int(now[-1])-1,int(now[-1]),int(now[-1])+1]:
            if nxt < 0 or nxt > 9:
                continue
            d.append(now+str(nxt))



if __name__ == '__main__':
    main()

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()
    right = x % 10
    for j in range(max(0, right-1), min(right+2, 10)):
        q.put(x*10 + j)

print(x)

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


def main():
    n = int(input())
    lunlun = [[] for i in range(11)]
    lunlun[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    cnt = 9
    if n < 10:
        print(n)
        exit()
    for j in range(0, 10):
        for a in lunlun[j]:
            for b in range(10):
                if abs((a % 10) - b) < 2:
                    lunlun[j + 1].append(10 * a + b)
                    cnt += 1
                    if cnt == n:
                        print(10 * a + b)
                        exit()

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
K=int(input())
d=deque([_ for _ in range(1,10)])
if K<=9:
  print(K)
  exit()
i=0
while True:
  a=d.popleft()
  i+=1
  if i==K:
    print(a)
    exit()
  if a%10!=0 and a%10!=9:
    d.extend([10*a+(a%10)+i for i in range(-1,2)])
  elif a%10==0:
     d.extend([10*a+i for i in range(2)])
  elif a%10==9:
     d.extend([10*a+i for i in range(8,10)])

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


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

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

print(lunlun)

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

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

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

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

print(lunlun[k-1])

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

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

Solution (Python):
import copy
k=int(input())
ans=[[str(i+1) for i in range(9)]]
l2=[]
for i in range(9):
  l=ans[-1]
  l2=[]
  for j in range(len(l)):
    if int(l[j][-1])!=0:
      l2.append(l[j]+str(int(l[j][-1])-1))
    l2.append(l[j]+str(int(l[j][-1])))
    if int(l[j][-1])!=9:
      l2.append(l[j]+str(int(l[j][-1])+1))
  ans.append(l2)
  l=copy.copy(l2)
a=[]
for i in range(10):
  a=a+ans[i]
print(a[k-1])

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

for i in range(12):
  if len(anss)>k:
    print(anss[k-1])
    break
  new_anss=[]
  for ans in anss:
    if ans%10 != 0:
      new_anss.append(ans*10+ans%10-1)
    new_anss.append(ans*10+ans%10)
    if ans%10 != 9:
      new_anss.append(ans*10+ans%10+1)
  k -= len(anss)
  anss = new_anss

Solution (Python):
from collections import deque

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

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

print(lst.popleft())

Solution (Python):
import queue

k = int(input())

q = queue.Queue()
for i in range(1, 10):
  q.put(i)
for i in range(k-1):
  a = q.get()
  b = a % 10  
  if b != 0:
    q.put(10*a + b - 1)
  q.put(10*a + b)
  if b != 9:
    q.put(10*a + b + 1)

print(q.get())

Solution (Python):
k = int(input())
anss = [1,2,3,4,5,6,7,8,9]
for i in range(12):
    if len(anss) > k:
        print(anss[k-1])
        break
    new_anss = []
    for ans in anss:
        if ans % 10 != 0:
            new_anss += [ans*10+ans%10-1]
        new_anss += [ans*10+ans%10]
        if ans % 10 != 9:
            new_anss += [ans*10+ans%10+1]
    k -= len(anss)
    anss = new_anss

Solution (Python):
from collections import deque

K = int(input())

d = [-1, 0, 1]

lun = deque([1,2,3,4,5,6,7,8,9])
cnt = 9
while cnt < K:
    a = lun.popleft()
    b = str(a)[-1]
    if b not in ('0', '9'):
        lun.append(int(str(a) + str(int(b) - 1)))
        lun.append(int(str(a) + b))
        lun.append(int(str(a) + str(int(b) + 1)))
        cnt += 3
    elif b == '0':
        lun.append(int(str(a) + b))
        lun.append(int(str(a) + str(int(b) + 1)))
        cnt += 2
    elif b == '9':
        lun.append(int(str(a) + str(int(b) - 1)))
        lun.append(int(str(a) + b))
        cnt += 2

print(lun[K-cnt-1])

Solution (Python):
from collections import deque
K = int(input()) - 1
todo = deque(range(1, 10))
ans = []
counter = 0
while counter <= K:
    seed = todo.popleft()
    ans.append(seed)
    counter += 1
    last_dig = int(str(seed)[-1])
    for i in range(max(0, last_dig-1), min(10, last_dig+2)):
        todo.append(int(str(seed) + str(i)))
print(ans[-1])

Solution (Python):
from collections import deque

K = int(input())

dq = deque()
for x in range(1, 10):
    dq.append(x)

idx = 1
while idx < K:
    x = dq.popleft()
    idx += 1

    r = x % 10

    if r > 0:
        nx = (x * 10) + (r - 1)
        dq.append(nx)

    nx = (x * 10) + (r)
    dq.append(nx)

    if r < 9:
        nx = (x * 10) + (r + 1)
        dq.append(nx)

ans = dq.popleft()
print(ans)

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

Solution (Python):


from collections import deque


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

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

    l = 0
    for _ in range(k):
        l = queue.popleft()
        r = l % 10
        if r != 0:
            queue.append(l * 10 + r - 1)
        queue.append(l * 10 + r)
        if r != 9:
            queue.append(l * 10 + r + 1)
    print(l)


if __name__ == "__main__":
    main()

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

Solution (Python):
import sys
k = int(input())
old = [1,2,3,4,5,6,7,8,9]
new = []
count = 9
if k <= count:
    print(old[k-1])
    sys.exit()
else:
    while count < k:
        if len(old) > 0:
            i = old.pop(0)
            last = i%10
            if last != 0:
                new.append(i*10 + (last-1))
                count += 1
                if count == k:
                    break
            new.append(i*10 + last)
            count += 1
            if count == k:
                break
            if last != 9:
                new.append(i*10 + (last+1))
                count += 1
                if count == k:
                    break
        else:
            old = new
            new = []
    print(new[-1])

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

from collections import deque
q = deque(range(1,10))

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

Solution (Python):
from collections import *
k=int(input());q=deque(range(1,10));c=0
while c<k:
  t=q.popleft()
  for j in range(max(t%10-1,0),min(t%10+2,10)): q+=[t*10+j]
  c+=1
print(t)

Solution (Python):
from collections import deque


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

while K > 0:
    p = q.popleft()
    K -= 1
    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 collections import deque

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

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

    count = 0
    while (True):
        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)
        if count == K-1:
            print(x)
            break
        count += 1

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):
    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):
k=int(input())
 
from collections import deque
q = deque(range(1, 10))

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

Solution (Python):
K = int(input())
 
from collections import deque
q = deque(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):
n=int(input());l=list(range(1,10));c=1
for i in l:
  c+=1
  if c>n: print(i); break
  for j in range(max(i%10-1,0),min(i%10+2,10)): l+=[i*10+j]

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def isOk(x):
    prev = x%10
    x = x//10
    while x > 0:
        y = x%10
        if abs(y - prev) > 1:
            return False
    
    return True


k = int(input())





count = 0

def dfs(X,n):
    global count

    

    if n == 0:
        count += 1
        if count == k:
            print("".join(map(str,X)))
            exit()
        
            
        return
    
    if len(X) == 0:
        for y in range(1,10):
            dfs([y], n-1)
        return

    last = X[-1]
    for y in range(max(0,last-1), min(9,last+1)+1):
        dfs(X + [y], n-1)


dfs([], 1)
dfs([], 2)
dfs([], 3)
dfs([], 4)
dfs([], 5)
dfs([], 6)
dfs([], 7)
dfs([], 8)
dfs([], 9)
dfs([], 10)

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

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

print(ans[K-1])

Solution (Python):
import sys
import collections
input = sys.stdin.readline
K = int(input())
 
queue = collections.deque()
 
for n in range(1, 10):
	queue.append(n)
 
n = 1
for k in range(K):
	n = queue.popleft()
	d = n % 10
	if d != 0:
		queue.append(n * 10 + d - 1)
	queue.append(n * 10 + d)
	if d != 9:
		queue.append(n * 10 + d + 1)
 
print(n)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

def resolve():
    k = int(input())

    def check(x):
        x = str(x)
        dp = [[0] * 2 for _ in range(10)]
        
        s = int(x[0])
        for i in range(1, s):
            dp[i][1] = 1
        dp[s][0] = 1

        x = x[1:]
        for s in x:
            s = int(s)
            ndp = [[0] * 2 for _ in range(10)]
            for d, lt in product(range(10), range(2)):
                for nd in [d-1, d, d+1]:
                    if not (0 <= nd <= 9):
                        continue
                    if lt == 0 and s < nd:
                        continue
                    nlt = max(lt, s > nd)
                    ndp[nd][nlt] += dp[d][lt]
            for d in range(1, 10):
                ndp[d][1] += 1
            dp = ndp
        return sum(dp[d][lt] for d, lt in product(range(10), range(2))) >= k

    print(bisection(1, 10**18+1, check, left=False))
resolve()

Solution (Python):
k = int(input())
a = list()
old = list()
for i in range(1,10):
    a.append(i)
while(True):
    if k <= len(a):
        print(a[k - 1])
        break
    k -= len(a)
    old.clear()
    a,old = old,a
    for i in old:
        for d in range(-1,2):
            last_num = i % 10 + d
            if (last_num >= 0) and (last_num <= 9):
                new = 10 * i + last_num
                a.append(new)

Solution (Python):
K = int(input())
lunlun = [n for n in range(10)]
if K < 10:
    print(K)
else:
    tmp = 9
    pre_top = 1
    pre_bottom = 9
    while(1):
        for j in range(pre_top, pre_bottom+1):
            for k in range(10):
                if abs(lunlun[j]%10 - k) < 2:
                    lunlun.append(lunlun[j]*10+k)
                    tmp += 1
                    if tmp == K:
                        break
            if tmp == K:
                break
        pre_top = pre_bottom + 1
        pre_bottom = tmp
        if tmp == K:
            break

    print(lunlun[-1])

Solution (Python):
def func(n):
    if (n==0):return [n,n+1]
    if (n==9):return [n-1,n]
    return [n-1,n,n+1]
k = int(input())
k_su = 0
lunlun_fl = [1,2,3,4,5,6,7,8,9]
while True:
    k_su += 1
    lunlun_fl_ = lunlun_fl
    
    for i in lunlun_fl_:
        if (len(str(i)) != k_su):
            continue
        lunlun_n = list(map(lambda x:int(str(i)+str(x)),func(int(str(i)[-1]))))
        lunlun_fl.extend(lunlun_n)
        if (len(lunlun_fl) >= k):break
    
    if (len(lunlun_fl) >= k):break
print(lunlun_fl[k-1])

Solution (Python):
nstr=["0","1","2","3","4","5","6","7","8","9"]

k=int(input())

k=k-1

kcnt=-1
m=[]
ms=[""]*100000

for ii in range(1,10):
    kcnt=kcnt+1
    ms[kcnt]=nstr[ii]


    if kcnt>=k:
        print(ms[k])
        break                

ked=-1
while kcnt<k:
    kst=ked+1
    ked=kcnt
    for i in range(kst,ked+1):
        i2=int(ms[i][-1])
        for ii in range(max(i2-1,0),min(i2+1,9)+1):
            kcnt=kcnt+1
            ms[kcnt]=ms[i]+nstr[ii]

            if kcnt>=k:
                print(ms[k])
                break                
        if kcnt>=k:

            break

Solution (Python):
lun_luns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
k = int(input())
index = 0
while True:
	if len(lun_luns) >= k:
		break
	num = lun_luns[index]
	mod = num % 10
	n = num * 10
	if mod == 9:
		lun_luns.extend([n+mod-1, n+mod])
	elif mod == 0:
		lun_luns.extend([n, n+1])
	else:
		lun_luns.extend([n+mod-1, n+mod, n+mod+1])
	index += 1
print(lun_luns[k-1])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

def resolve():
    k = int(input())

    def check(x):
        if 1 <= x <= 9:
            return x >= k
        x = str(x)
        dp = [[0] * 2 for _ in range(10)]
        s = int(x[0])
        for i in range(1, s):
            dp[i][1] = 1
        dp[s][0] = 1

        x = x[1:]
        for s in x:
            s = int(s)
            ndp = [[0] * 2 for _ in range(10)]
            for d, lt in product(range(10), range(2)):
                for nd in [d-1, d, d+1]:
                    if not (0 <= nd <= 9):
                        continue
                    if lt == 0 and s < nd:
                        continue
                    nlt = max(lt, s > nd)
                    ndp[nd][nlt] += dp[d][lt]
            for d in range(1, 10):
                ndp[d][1] += 1
            dp = ndp
        return sum(dp[d][lt] for d, lt in product(range(10), range(2))) >= k


    print(bisection(1, 10**18+1, check, left=False))
resolve()

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

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


for s in l0:
    temp=str(s)
    x=int(temp[-1])

    if x==0:
        l0.append(int(temp+"0"))
        l0.append(int(temp+"1"))
        
    if x>=1 and x<=8:
        l0.append(int(temp+str(x-1)))
        l0.append(int(temp+str(x)))
        l0.append(int(temp+str(x+1)))
    if x==9:
        
        l0.append(int(temp+"8"))
        l0.append(int(temp+"9"))
    
    if len(l0)>100002:
        break


print(l0[k-1])

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

from collections import deque
q = deque(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):
K = int(input())

from collections import deque
q = deque(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):
cands = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def add_v(v):
  global cands
  global K
  v0 = v % 10
  if v0 == 0:
    cands += [v*10, v*10+1]
    K -=2
  elif v0 == 9:
    cands += [v*10+8, v*10+9]
    K -= 2
  else:
    cands += [v*10+v0-1, v*10+v0, v*10+v0+1]
    K -= 3

K = int(input())
idk = K
K -= 9
idx = 0
while K >= 0:
  add_v(cands[idx])
  idx += 1

print(cands[idk-1])

Solution (Python):
from collections import deque

K = int(input())
que = deque()
for i in range(1, 10):
    que.append(i)
count = 0
while 1:
    count += 1
    x = que.popleft()
    for i in range(-1, 2):
        d = x % 10 + i
        if (d < 0 or 9 < d):
            continue
        que.append(x * 10 + d)
    if (count == K):
        print(x)
        break

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

    def make_lunlun(number):
        min = str(number)[-1]
        new_lunlun = number * 10 + int(min)
        if min == "0":
            return (new_lunlun, new_lunlun + 1)
        elif min == "9":
            return (new_lunlun - 1, new_lunlun)
        else:
            return (new_lunlun - 1, new_lunlun, new_lunlun + 1)

    index = 0
    while True:
        if len(lun_luns) >= k:
            break
        num = lun_luns[index]
        lun_luns.extend(make_lunlun(num))
        index += 1
    print(lun_luns[k - 1])

if __name__ == '__main__':
    main()

Solution (Python):



def main():
    K = int(input())
    queue = list(range(1, 10))
    i = 0
    while len(queue) < K:
        x = queue[i]
        remainder = x % 10
        if remainder:
            queue.append(10 * x + remainder - 1)
        queue.append(10 * x + remainder)
        if remainder != 9:
            queue.append(10 * x + remainder + 1)
        i += 1
    ans = queue[K - 1]
    print(ans)


if __name__ == "__main__":
    main()

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):
n = int(input())
count = 0
arr  = [1,2,3,4,5,6,7,8,9]

while len(arr)<n:
    lastnum = int(str(arr[count])[-1])
    if lastnum == 0:
        arr.append(int(str(arr[count])+'0'))
        arr.append(int(str(arr[count])+'1'))
    elif 1 <= lastnum <= 8:
        arr.append(int(str(arr[count])+str(lastnum-1)))
        arr.append(int(str(arr[count])+str(lastnum)))
        
        arr.append(int(str(arr[count])+str(lastnum+1)))
    else:
        arr.append(int(str(arr[count])+'8'))
        arr.append(int(str(arr[count])+'9'))
    count += 1

print(arr[n-1])

Solution (Python):
from collections import deque

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

ans = 0
while True:
    v = dque.popleft()
    ans += 1
    if ans == K:
        print(v)
        exit(0)

    strv = str(v)
    if strv[-1] == '0':
        dque.append(int(strv+'0'))
        dque.append(int(strv+'1'))
    elif strv[-1] == '9':
        dque.append(int(strv+'8'))
        dque.append(int(strv+'9'))
    else:
        endv = int(strv[-1])
        dque.append(int(strv+str(endv-1)))
        dque.append(int(strv+str(endv)))
        dque.append(int(strv+str(endv+1)))

Solution (Python):
from collections import deque


def D(K):
    d = deque()
    c = 0

    for i in range(1, 10):
        d.append(i)
        c += 1
        if c == K:
            return d

    while True:
        num = d.popleft()
        mod = num % 10
        
        if mod != 0:
            d.append(num * 10 + mod - 1)
            c += 1
            if c == K:
                return d
            
        d.append(num * 10 + mod)
        c += 1
        if c == K:
            return d
        
        if mod != 9:
            d.append(num * 10 + mod + 1)
            c += 1
            if c == K:
                return d
              
              
K = int(input())
print(D(K).pop())

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

cnt = 0
num = 1
while True:
    flag = True
    s_num = str(num)
    diff = 0
    pos = 0
    pos_value = 0
    for i in range(len(s_num)-1, 0, -1):
        diff = int(s_num[i]) - int(s_num[i-1])
        if abs(diff) > 1:
            flag = False
            pos = i
            pos_value = int(s_num[i])
            break
    if flag:
        cnt += 1
    
    if cnt == K:
        print(num)
        sys.exit()
    
    if pos == 0:

        num += 1
    elif diff < 0:

        num += (abs(diff) - 1) * (10**(len(s_num)-pos-1))
    else:
        if pos_value != 9:

            num += (10 - pos_value - 1) * (10**(len(s_num)-pos-1))
        else:

            num += (10 - pos_value ) * (10**(len(s_num)-pos-1))
            if pos != len(s_num) - 1:
                num -=  int(s_num[pos+1:])

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

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False


g = []


def rec(i, s, N):
    
    global g
    g.append(int(s))
    if len(s) > N:
        return

    if i - 1 >= 0:
        rec(i-1, s + str(i-1), N)
    rec(i, s + str(i), N)
    if i + 1 <= 9:
        rec(i+1, s + str(i+1), N)


def main():
    global g
    K = I()
    ans = []

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


if __name__ == '__main__':
    main()