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

Solution (Python):
from collections import deque
k = int(input())
stack = deque([x for x in range(1, 10)])
cnt = 9
flag = False
while len(stack) > 0:
    if k < 10:
        print(stack[k - 1])
        break
    now_num = stack.popleft()
    if now_num % 10 == 0:
        for x in [0, 1]:
            next_num = str(now_num) + str(x)
            next_num = int(next_num)
            stack.append(next_num)
            cnt += 1
            if cnt == k:
                print(stack.pop())
                flag = True
                break
    elif now_num % 10 == 9:
        for x in [8, 9]:
            next_num = str(now_num) + str(x)
            next_num = int(next_num)
            stack.append(next_num)
            cnt += 1
            if cnt == k:
                print(stack.pop())
                flag = True
                break
    else:
        for x in range(now_num % 10 - 1, now_num % 10 + 2):
            next_num = str(now_num) + str(x)
            next_num = int(next_num)
            stack.append(next_num)
            cnt += 1
            if cnt == k:
                print(stack.pop())
                flag = True
                break
    if flag:
        break

Solution (Python):


def is_valid(num):
    if 1 <= num < 10:
        return True
    ns = map(int, str(num))
    n = len(ns)
    for i in xrange(n - 1):
        if abs(ns[i] - ns[i + 1]) > 1:
            return False
    return True

lunluns = []
for i in xrange(1, 10):
    if is_valid(i):
        lunluns.append(i)

d = {}

def dfs2(rem, pre, lt):
    if rem == 0:
        return 1
    key = (rem, pre, lt)
    if key in d:
        return d[key]

    res = 0
    if lt:
        for i in xrange(10):
            res += dfs2(rem - 1, i, lt and i == 0)
    else:
        for i in xrange(10):
            if abs(i - pre) <= 1:
                res += dfs2(rem - 1, i, False)
    d[key] = res
    return res

assert dfs2(1, -1, True) == 10
assert dfs2(1, 1, False) == 3

def dfs(cur, n, k, pre, lt, buf):
    if cur == n:
        return k == 1

    for i in xrange(10):
        if lt or abs(i - pre) <= 1:
            u = dfs2(n - cur - 1, i, lt and i == 0)
            if u < k:
                k -= u
            else:
                buf.append(i)
                assert dfs(cur + 1, n, k, i, lt and i == 0, buf)
                break
    return True

def solve(k):
    N = 500
    res = []
    assert dfs(0, N, k, -1, True, res)
    res = res[::-1]
    while res and res[-1] == 0:
        res.pop()
    if not res:
        res = [0]
    return ''.join(map(str, res[::-1]))

assert solve(3) == '2'
assert solve(1) == '0'
assert solve(2) == '1'
assert solve(4) == '3'

for i, num in enumerate(lunluns):
    assert solve(i + 2) == str(num)

if __name__ == '__main__':
    k = int(raw_input())
    k += 1
    print solve(k)

Solution (Python):
def is_valid(num):
    if 1 <= num < 10:
        return True
    ns = map(int, str(num))
    n = len(ns)
    for i in xrange(n - 1):
        if abs(ns[i] - ns[i + 1]) > 1:
            return False
    return True

lunluns = []
for i in xrange(1, 100000):
    if is_valid(i):
        lunluns.append(i)

d = {}

def dfs2(rem, pre):
    if rem == 0:
        return 1
    key = (rem, pre)
    if key in d:
        return d[key]

    res = 0
    if pre == -1:
        for i in xrange(10):
            res += dfs2(rem - 1, -1 if i == 0 else i)
    else:
        for i in xrange(10):
            if abs(i - pre) <= 1:
                res += dfs2(rem - 1, i)
    d[key] = res
    return res

assert dfs2(1, -1) == 10
assert dfs2(1, 1) == 3

def dfs(cur, n, k, pre, buf):
    if cur == n:
        return k == 1

    for i in xrange(10):
        if pre == -1 or abs(i - pre) <= 1:
            u = dfs2(n - cur - 1, -1 if pre == -1 and i == 0 else i)
            if u < k:
                k -= u
            else:
                buf.append(i)
                assert dfs(cur + 1, n, k, -1 if pre == -1 and i == 0 else i, buf)
                break
    return True

def solve(k):
    N = 500
    res = []
    assert dfs(0, N, k, -1, res)
    res = res[::-1]
    while res and res[-1] == 0:
        res.pop()
    if not res:
        res = [0]
    return ''.join(map(str, res[::-1]))

assert solve(3) == '2'
assert solve(1) == '0'
assert solve(2) == '1'
assert solve(4) == '3'

for i, num in enumerate(lunluns):
    assert solve(i + 2) == str(num)

if __name__ == '__main__':
    k = int(raw_input())
    k += 1
    print solve(k)

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

from collections import deque
que = deque(r)

if k < 10:
    print(k)
    exit()
while len(r) <= k:
    ri = que.popleft()
    for j in range(max(0, ri[-1]-1), min(9, ri[-1]+1)+1):
        rj = ri.copy()
        rj.append(j)
        r.append(rj)
        que.append(rj)
        

print(''.join(map(str, r[k-1])))

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

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

c = 0
while k>len(l):
    f = str(l[c])

    if int(f[-1])!=0:
        l.append(int(f)*10 + int(f[-1])-1)

    l.append(int(f)*10 + int(f[-1]))

    if int(f[-1])!=9:
        l.append(int(f)*10 + int(f[-1])+1)

    c += 1

print(l[k-1])

Solution (Python):
from queue import Queue

def main():
	K = int(input())
	count = 0
	ans = 0

	q = Queue()
	q.put(-1)


	while(not q.empty()):
		next_loop = True
		v = q.get()

		if(v == -1):
			for i in range(1, 10):
				q.put(i)
				count += 1

				if(count == K):
					ans = i
					next_loop = False
				
		else:
		
			for i in range(0, 10):
				d1 = v%10
				
				if(not (d1-1 <= i <= d1+1)):
					continue

				count += 1

				if(count == K):
					ans = v * 10 + i
					next_loop = False
					break

				q.put(v * 10 + i)
		
		if(not next_loop):
			break

	print(ans)


if __name__ == "__main__":
	main()

Solution (Python):
K = 0
def recursive(d:int,value:int,lis:list):
    lis.append(value)
    if(d == 10):return
    for j in range(-1,2,1):
        add = value % 10 + j
        if(add >= 0 and add <= 9):
            recursive(d + 1,value * 10 + add,lis)
    

def main():
    global K
    K = int(input())
    lis = []
    for v in range(1,10):
        recursive(1,v,lis)
    lis.sort()
    print(lis[K - 1])


if __name__ == "__main__":
    main()

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

def calc_next(ar):
  res = []
  for val in ar:
    for j in range(-1, 2):
      add = (val % 10) + j
      if add >= 0 and add <= 9:
        res.append(val*10+add)
  return res

cur = []
all_ = []

for v in range(1, 10):
  cur.append(v)
  all_.append(v)
  

for d in range(1, 10):
  
  cur = calc_next(cur)
  
  
  for val in cur:
    all_.append(val)


print(all_[K-1])

Solution (Python):

import sys
input = sys.stdin.readline

k = int(input())

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

def generator_lunlun(n):
    final = n % 10
    if final > 0:
        yield n * 10 + final - 1
    yield n * 10 + final
    if final < 9:
        yield n * 10 + final + 1
        
     
p = 0
while len(lunlun) < k:
    for result in generator_lunlun(lunlun[p]):
        lunlun.append(result)
    p += 1

print(lunlun[k-1])

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

q = deque([i for i in range(1,10)])
for i in range(1,k+1):
  x = q.popleft()
  if i == k:
    print(x)
    exit()
  
  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)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

def DFS(N, string, val, L):
	L.append(int(string))
	if N == 11:
		return
	else:
		if val == 0:
			DFS(N + 1, string + "0", 0, L)
			DFS(N + 1, string + "1", 1, L)
		elif val == 9:
			DFS(N + 1, string + "9", 9, L)
			DFS(N + 1, string + "8", 8, L)
		else:
			DFS(N + 1, string + str(val + 1), val + 1, L)
			DFS(N + 1, string + str(val), val, L)
			DFS(N + 1, string + str(val - 1), val - 1, L)


def main():
	K = int(input())
	L = []
	for i in range(10):
		DFS(0, str(i), i, L)

	L = sorted(list(set(L)))

	print(L[K])


if __name__ == '__main__':
	main()

Solution (Python):
from collections import deque
k = int(input())
num = deque()
for i in range(1,10):
    num.append(i)
while True:
    l = len(num)
    if l >= k:
        print(num[k-1])
        exit()
    else:
        k -= l
        for i in range(l):
            left = num.popleft()
            last = left%10
            add1,add2,add3 = 10*left+last-1,10*left+last,10*left+last+1
            if 0 < last < 9:
                num.append(add1)
                num.append(add2)
                num.append(add3)
            elif last == 0:
                num.append(add2)
                num.append(add3)
            else:
                num.append(add1)
                num.append(add2)

Solution (Python):
K = int(input())
List = [[1,2,3,4,5,6,7,8,9]]
for i in range(10):
  for j in List[i]:
    List.append([])
    if int(j)%10==0:
      List[i+1].append(str(j)+"0")
      List[i+1].append(str(j)+"1")
    elif int(j)%10==9:
      List[i+1].append(str(j)+"8")
      List[i+1].append(str(j)+"9")
    else:
      k=int(j)%10
      List[i+1].append(str(j)+str(k-1))
      List[i+1].append(str(j)+str(k))
      List[i+1].append(str(j)+str(k+1))

Sum = 0      
for i in range(10):
  Sum += len(List[i])
  if K<=Sum:
    print(List[i][K-(Sum-len(List[i]))-1])
    break

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

from queue import Queue
q=Queue()

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

cnt=0

while 1:
  cnt+=1
  x=q.get()
  if cnt==k:
    print(x)
    exit()
  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)

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

K = int(input())

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

def dfs(i):
    n = int(str(i)[-1]) 
    a,b,c = n-1, n, n+1 
    if a != -1:
        ln.append(i*10+a)
    ln.append(i*10+b)
    if c != 10:
        ln.append(i*10+c)
    
    if len(str(i)) <= 10:
        if a != -1:
            dfs(i*10 + a)
        dfs(i*10 + b)
        
        if c != 10:
            dfs(i*10 + c)

for i in l: 
    dfs(i)

print(sorted(ln)[K-1])

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

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

Solution (Python):
K=int(input())
A=[1,2,3,4,5,6,7,8,9]
B=[]
C=[]
D=[]
E=[]
F=[]
G=[]
H=[]
I=[]
J=[]
def henkan(A):
    a=len(A)
    B=[]
    for i in range(a):
        if A[i]%10==0:
            B.append(10*A[i])
            B.append(10*A[i]+1)
        elif A[i]%10==9:
            B.append(10*A[i]+9)
            B.append(10*A[i]+8)
        else:
            x=A[i]%10
            B.append(10*A[i]+x)
            B.append(10*A[i]+x+1)
            B.append(10*A[i]+x-1)
    return B

B=henkan(A)
C=henkan(B)
D=henkan(C)
E=henkan(D)
F=henkan(E)
G=henkan(F)
H=henkan(G)
I=henkan(H)
J=henkan(I)
ans=A+B+C+D+E+F+G+H+I+J
ans=sorted(ans)

print(ans[K-1])

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

cnt = 9
while q:
  n = q.popleft()
  r = n % 10
  n *= 10;
  for i in range(10):
    if abs(r - i) <= 1:
        q.append(n + i)
        cnt += 1
        if cnt == K:
          print(n+i)
          exit()

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

cnt = 0
while q:
  n = q.popleft()
  r = n % 10; n *= 10;
  for i in range(10):
    if abs(r - i) <= 1 or n == 0:
      if n + i != 0:
        q.append(n + i)
        cnt += 1
        if cnt == K:
          print(n+i)
          exit()

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

cnt = 0
ans = []
while q:
  a = q.popleft()
  r = a % 10
  a *= 10
  for i in range(10):
    if abs(r - i) <= 1 or a == 0:
      if cnt < K and a + i != 0:
        q.append(a + i)
        ans.append(a + i)
        cnt += 1

print(ans[-1])

Solution (Python):
K = int(input())
l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 9
if K > 9:
    for i in l:
        r = i % 10
        if r == 0:
            l.append(10*i + r)
            l.append(10*i + r+1)
            count += 2
            if count > K:
                break
                
        elif r == 9:
            l.append(10*i + r-1)
            l.append(10*i + r)
            count += 2
            if count > K:
                break
                
        else:
            l.append(10*i + r-1)
            l.append(10*i + r)
            l.append(10*i + r+1)
            count += 3
            if count > K:
                break
print(l[K-1])

Solution (Python):
import queue

K = int(input())

q = queue.Queue()
ans = []
cnt = 0
for i in range(1,10):
    q.put(i)
    ans.append(i)
    cnt += 1

while cnt <= 10**5:
    n = q.get()
    m = n %10
    if m == 0:
        q.put(n*10+0)
        q.put(n*10+1)
        ans.append(n*10)
        ans.append(n*10+1)
        cnt += 1
    elif m == 9:
        q.put(n*10+8)
        q.put(n*10+9)
        ans.append(n*10+8)
        ans.append(n*10+9)
        cnt += 2
    else:
        q.put(n*10+m-1)
        q.put(n*10+m)
        q.put(n*10+m+1)
        ans.append(n*10+m-1)
        ans.append(n*10+m)
        ans.append(n*10+m+1)
        cnt += 3

print(ans[K-1])

Solution (Python):

def makeLunLun(num):
  lunlunNums = []
  m = num % 10 -1
  z = m + 1
  p = m + 2
  if m >= 0:
    lunlunNums.append(num * 10 + m)
  lunlunNums.append(num * 10 + z)
  if p <= 9:
    lunlunNums.append(num * 10 + p)
  return lunlunNums

K=int(input())

queue = [1,2,3,4,5,6,7,8,9]
i=0
while K > len(queue):
  lunluns = makeLunLun(queue[i])
  queue += lunluns
  i += 1
print(queue[K-1])

Solution (Python):
from collections import deque
K = int(input())
ans = 0
cnt = 9
start = 0
X = deque([[[9],[8],[7],[6],[5],[4],[3],[2],[1]]])
if K <= 9:
  print(K)
  exit()
for _ in range(10000):
    X.append(deque([]))
for i in range(1,10000):
    now_cnt = cnt
    for x in list(X[i-1]):
        for j in range(10,0,-1):
            if abs(x[len(x)-1]-j+1) <= 1:
                X[i].append(x+[j-1])
                cnt += 1
    if cnt >= K:
        X[i].reverse()
        lun = X[i][K-now_cnt-1]
        
        N = []
        
        for n in lun:
          N.append(str(n))
        
        print(''.join(N))
        exit()

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



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

for i in range(k):
    val=q.popleft()
    mod=val%10
    for add in range(max(mod-1,0),min(mod+1,9)+1):
        q.append(val*10+add)
print(val)

Solution (Python):

def p_num():
    global num
    ans = 0
    for i in range(12):
        ans += num[i] * (10 ** i)
    print(ans)


def fun(i, f):
    global k, num, n
    p = num[i + 1]
    for j in range(max(0, p - 1), ((f == 1) * 10) + ((f != 1) * min(10, p + 2))):
        num[i] = j
        if (i == 0):
            
            n += 1
            if (k == n):
                p_num()
                exit()
        else:
            fun(i - 1, f and j == 0)


k = int(input())
num = [0] * 15
n = -1

fun(11, 1)

Solution (Python):

def calc_next(arr):
	res = []
	for val in arr:
		for j in range(-1, 2):
			add = (val % 10) + j
			if add >= 0 and add <= 9:
				res.append(val * 10 + add)
	return res

k = int(input())
cur = []
A = []

for v in range(1, 10):
	cur.append(v)
	A.append(v)

for d in range(1, 10):
	cur = calc_next(cur)
	for val in cur:
		A.append(val)

print(A[k - 1])

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.append(i*10+j)
  if len(l)>k:
    break
print(l[k-1])

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

def dfs(d, val, A):
	A.append(val)

	if d == 10:
		return

	for i in range(-1, 2):
		add = (val % 10) + i
		if add >= 0 and add <= 9:
			dfs(d + 1, val * 10 + add, A)

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

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

runrun=[[1,2,3,4,5,6,7,8,9],[]]
count=9
keta=2
end=False
ans=-1

if x<=9:
    ans=x
    end=True

while True:
    if end:
        break

    for ini in runrun[keta-2]:

        if ini%10==0:
            runrun[keta-1].append(ini*10)
            count+=1
            if count==x:
                end=True
                ans=ini*10
                break
            runrun[keta-1].append(ini*10+1)
            count+=1
            if count==x:
                end=True
                ans=ini*10+1
                break

        elif ini%10==9:
            runrun[keta-1].append(ini*10+8)
            count+=1
            if count==x:
                end=True
                ans=ini*10+8
                break
            runrun[keta-1].append(ini*10+9)
            count+=1
            if count==x:
                end=True
                ans=ini*10+9
                break

        else:
            runrun[keta-1].append(ini*10+ini%10-1)
            count+=1
            if count==x:
                end=True
                ans=ini*10+ini%10-1
                break
            runrun[keta-1].append(ini*10+ini%10)
            count+=1
            if count==x:
                end=True
                ans=ini*10+ini%10
                break
            runrun[keta-1].append(ini*10+ini%10+1)
            count+=1
            if count==x:
                end=True
                ans=ini*10+ini%10+1
                break

    keta +=1
    runrun.append([])

print(ans)

Solution (Python):
from collections import deque

K = int(input())

q = deque(list(range(1, 10)))
ctr = 0
while ctr < K:
    val = q.popleft()
    ctr += 1
    for i in range(-1, 2):
        add = (val % 10) + i
        if 0 <= add <= 9:
            q.append(val * 10 + add)
            
print(val)

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

def dfs(d, val, x):
    x.append(val)
    
    if d == 10:
        return
    
    for i in range(-1, 2):
        add = (val % 10) + i
        if 0 <= add <= 9:
            dfs(d + 1, val * 10 + add, x)

x = []
for i in range(1, 10):
    dfs(0, i, x)
print(sorted(x)[K - 1])

Solution (Python):
import collections

k = int(input())
q = collections.deque(list(range(1, 10)))
i = 0

while i < k:
    i += 1

    org = q.popleft()
    x = org % 10

    if x != 0:
        q.append(10 * org + x - 1)

    q.append( 10 * org + x)

    if x != 9:
        q.append(10 * org + x + 1)
print(org)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import collections

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

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

K = int(input())

lunluns = collections.deque()
for i in range(1, 10):
    lunluns.append(str(i))


for i in range(K - 9):
    a = lunluns[i]
    if a[-1] == "9":
        for j in ["8", "9"]:
            lunluns.append(a + j)
    elif a[-1] == "0":
        for j in ["0", "1"]:
            lunluns.append(a + j)
    else:
        base = int(a[-1])
        for j in range(base - 1, base + 2):
            lunluns.append(a + str(j))

print(lunluns[K - 1])

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

c = []









def lunlun(d, num):
    if d > 10:
        return

    c.append(num)

    m = num % 10
    for i in range(-1, 2):
        if 0 <= m + i <= 9:
            lunlun(d + 1, num * 10 + m + i)


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

c.sort()
print(c[k - 1])

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

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


for k in range(k + 1):
    n = c[k]
    m = n % 10
    for i in range(-1, 2):
        if 0 <= m + i <= 9:
            c.append(n * 10 + m + i)


print(c[k - 1])

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

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)

Solution (Python):
def function(n):
  string = str(n)
  for i in range(len(string) - 1):
    error = int(string[i]) - int(string[i + 1])
    if error > 1:
      return i + 1, error
    elif error < -1:
      return i, abs(error)
  return -1, 0
 
k = int(input())
ans = []
n = 1
while len(ans) < k:
  m, error = function(n)
  if m == -1:
    ans.append(n)
    n += 1
  else:
    n = n + (error - 1) * (10 ** (len(str(n)) - m - 1)) - n % (10 ** (len(str(n)) - m - 1))
print(ans[-1])

Solution (Python):
def dfs(d, r):
    global l
    if d == 11:
        return
    l.append(int(r))
    for i in range(-1, 2):
        tmp = int(r[-1]) + i
        if 0 <= tmp <= 9:
            dfs(d + 1, r + str(tmp))


k = int(input())
l = []
for i in range(1, 10):
    dfs(1, str(i))
print(sorted(l)[k - 1])

Solution (Python):
def dfs(d, r):
    global l
    if d == 11:
        return
    l.append(int(r))
    for i in range(-1, 2):
        tmp = int(r[-1]) + i
        if 0 <= tmp <= 9:
            dfs(d + 1, r + str(tmp))


k = int(input())
l = []
for i in range(1, 10):
    dfs(0, str(i))
print(sorted(l)[k - 1])

Solution (Python):
cur = []

def recur(n):
    if n > 10 ** 10:
        return
    cur.append(n)
    for i in range(10):
        if abs(n % 10 - i) <= 1:
            recur(10 * n + i)

for i in range(1, 10):
    recur(i)
cur.sort()
n = int(input())
print((cur[n - 1]))

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


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





while total < K:
    lst.append([])
    for i in lst[-2]:
        strnum = str(i)
        last = int(strnum[-1])
        
        lst[-1].append(strnum + str(last))
        if last <= 8:
            lst[-1].append(strnum + str(last+1))
        if last >= 1:
            lst[-1].append(strnum + str(last-1))
            
    total += len(lst[-1])

lst[-1].sort()
print(lst[-1][K-total-1])

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

lunlun = set()

def dfs(A):
    
    if len(A) == 10:
        return
    for v in range(0, 10):
        if len(A) != 0:
            if abs(A[-1] - v) > 1:
                continue
        A.append(v)
        lunlun.add(int(''.join(list(map(str, A)))))
        dfs(A)
        A.pop() 

dfs([])

print(sorted(list(lunlun))[K])

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

lunlun = set()

def dfs(A):
    
    if len(A) == 10:
        return
    for v in range(0, 10):
        if len(A) != 0:
            if abs(A[-1] - v) > 1:
                continue
        A.append(v)
        lunlun.add(int(''.join(list(map(str, A)))))
        dfs(A)
        A.pop() 

dfs([])

print(sorted(list(lunlun))[K])

Solution (Python):
import sys
sys.setrecursionlimit(100000)

def dfs(A, i):
    A.append(i)
    if len(str(i)) == 10:
        return A
    x = int(list(str(i))[-1])-1 if int(list(str(i))[-1]) > 0 else 0
    y = int(list(str(i))[-1])+2 if int(list(str(i))[-1]) < 9 else 10
    for v in range(x, y):
        i = i * 10 + v
        dfs(A, i)
        i = int(str(i)[:len(str(i))-1])

K = int(input())
B = []
for i in range(1, 10):
    A = []
    dfs(A,i)
    B = B + A
B.sort()
print(B[K-1])

Solution (Python):
K = int(input())
r = [[] for _ in range(10)]
r[0] = list(range(1,10))

for i in range(9):
  for a in r[i]:
    s = str(a)
    d = a%10
    for j in range(d-1, d+2):
      if not 0 <= j <= 9: continue
      r[i+1].append(int(s+str(j)))

for i in range(10):
  if K >= len(r[i]):
    K -= len(r[i])
  else:
    print(r[i][K-1])
    break

Solution (Python):
K = int(input())
lunlun = []



def dfs(x):
    lunlun.append(x)

    if len(str(x)) == 11:
        return

    a = x % 10
    for v in [-1, 0, 1]:
        b = a + v
        if 0 <= b <= 9:
            y = x*10 + b
            dfs(y)


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

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

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
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))



def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  


def grid(n): return [s_list() for _ in range(n)]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def floor(a, b):
    """floor(a/b) 整数値を返す"""
    c = (a - a % b)/b
    return int(c)


def main():

    K = int(input())
    q = deque()
    for i in range(1, 10):
        q.append(i)
    cnt = 9
    if cnt >= K:
        print(q[K-1])
        sys.exit()
    while cnt < K:
        x = q.popleft()
        d = x % 10
        for v in [d-1, d, d+1]:
            if 0 <= v <= 9:
                y = x*10 + v
                q.append(y)
                cnt += 1
                if cnt == K:
                    break
    print(y)


if __name__ == '__main__':
    main()

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 defaultdict
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))



def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  


def grid(n): return [s_list() for _ in range(n)]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def floor(a, b):
    """floor(a/b) 整数値を返す"""
    c = (a - a % b)/b
    return int(c)


def main():

    def dfs(x):
        lunlun.append(x)
        d = x % 10
        if len(str(x)) == 11:
            return

        for v in [d+1, d, d-1]:
            if 0 <= v <= 9:
                dfs(x*10+v)

    K = int(input())
    cnt = 0
    lunlun = []

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

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


if __name__ == '__main__':
    main()

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 defaultdict
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))



def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  


def grid(n): return [s_list() for _ in range(n)]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def floor(a, b):
    """floor(a/b) 整数値を返す"""
    c = (a - a % b)/b
    return int(c)


def main():

    def dfs(x):
        lunlun.append(x)
        d = x % 10
        if len(str(x)) == 11:
            return

        for v in [d+1, d, d-1]:
            if 0 <= v <= 9:
                dfs(x*10+v)

    K = int(input())
    cnt = 0
    lunlun = []

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

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N = int(input())

A = deque(range(1,10))

count = 0
for _ in range(N):
    k = A.popleft()
    m = k % 10
    if m != 0:
        A.append(10 * k + m -1)
    A.append(10 * k + m)
    if m != 9:
        A.append(10 * k + m + 1)
print(k)