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())

lun = list(range(0, 10)) + [0] * (K - 9 + 2) 

k = 9
i = 1
while k < K:
    next = lun[i]
    dig = next % 10
    if dig > 0:
        k += 1
        lun[k] = next * 10 + dig - 1
    k += 1
    lun[k] = next * 10 + dig
    if dig < 9:
        k += 1
        lun[k] = next * 10 + dig + 1
    i += 1

print(lun[K])

Solution (Python):
from collections import deque

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

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

print(lun.popleft())

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

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

res = []
q = list(range(1,10))
while len(q)>0:
    a = q.pop()
    res.append(a)
    if a<4*10**10:
        d = a%10
        if d>0:
            q.append(10*a+d-1)
        q.append(10*a+d)
        if d<9:
            q.append(10*a+d+1)

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

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

lun = list(range(0, 10)) + [0] * (K - 9 + 2) 
k = 10

for i in range(1, K):
    if k > K: break
    next = lun[i]
    dig = next % 10  
    if dig == 0: 
        lun[k] = next * 10
        lun[k + 1] = next * 10 + 1
        k += 2
    elif dig == 9: 
        lun[k] = next * 10 + 8
        lun[k + 1] = next * 10 + 9
        k += 2
    else:  
        lun[k] = next * 10 + dig - 1
        lun[k + 1] = next * 10 + dig
        lun[k + 2] = next * 10 + dig + 1
        k += 3

print(lun[K])

Solution (Python):
from collections import deque

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

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

Solution (Python):
from copy import deepcopy
k = int(input())

lun = []
for i in range(1,10):
    lun.append(i)

if k <= 9:
    print(lun[k-1])
    exit()

prev_lun = deepcopy(lun)

while True:
    size = len(lun)
    for pl in prev_lun:
        for i in [-1, 0, 1]:
            d = pl%10 + i
            if 0 <= d <= 9:
                lun.append(pl*10 + d)
            if len(lun) == k:
                
                print(lun[k-1])
                exit()
                
    prev_lun = deepcopy(lun[size:])

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') 
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(sys.stdin.readline()) 
def ifn(): return float(sys.stdin.readline()) 
def isn(): return sys.stdin.readline().split() 
def imn(): return map(int, sys.stdin.readline().split()) 
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) 
def fmn(): return map(float, sys.stdin.readline().split()) 
def iln(): return list(map(int, sys.stdin.readline().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, sys.stdin.readline().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

K = iin()

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

cnt = 0
D = [-1,0,1]
while True:
    cnt += 1
    a = A.popleft()
    if cnt == K: 
        print(a)
        break
    t = (a % 10)
    for d in D:
        n = t+d
        if 0 <= n <= 9:
            A.append(a*10+n)

Solution (Python):
k=int(input())
s=9
l=[1,2,3,4,5,6,7,8,9]
n=0
while s<10**5+1:
  t=l[n]
  z=int(str(t)[-1])
  if z>0:  
    l.append(t*10+z-1)
    s+=1
  l.append(t*10+z)
  s+=1
  if z<9:
    l.append(t*10+z+1)
    s+=1
  n+=1
l.sort()
print(l[k-1])

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

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

Solution (Python):
import queue

k = int(input())

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

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

Solution (Python):
import queue
k = int(input())
q = [1,2,3,4,5,6,7,8,9]
qq = queue.Queue()
for i in range(1,10):
	qq.put(i)

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

Solution (Python):
import queue
K = int(input())
q = queue.Queue()
count = 0
for i in range(1,10):
  q.put(str(i))
while count < K:
  tmp = q.get()
  count += 1
  if count == K:
    print(tmp)
    break
  if tmp[-1] == '0':
    for k in ['0', '1']:
      q.put(tmp + k)
  elif tmp[-1] == '9':
    for t in ['8', '9']:
      q.put(tmp + t)
  else:
    for c in [str(int(tmp[-1]) - 1),tmp[-1], str(int(tmp[-1]) + 1)]:
      q.put(tmp + c)

Solution (Python):
import queue
K = int(input())
q = queue.Queue()
count = 0
for i in range(1,10):
  q.put(str(i))
while count < K:
  tmp = q.get()
  count += 1
  if count == K:
    print(tmp)
    break
  if tmp[-1] == '0':
    for add in ['0', '1']:
      q.put(tmp + add)
  elif tmp[-1] == '9':
    for add in ['8', '9']:
      q.put(tmp + add)
  else:
    for add in [str(int(tmp[-1]) - 1),tmp[-1], str(int(tmp[-1]) + 1)]:
      q.put(tmp + add)

Solution (Python):
X = int(input())
A = []
Amod = 0
j = 0
for i in range(1,10):
    A.append(i)
k=8
if X > 9:
    while(1):
        Amod = A[j]%10
        if Amod == 0:
            A.append(A[j]*10+0)
            A.append(A[j]*10+1)
            k+=2
        elif Amod == 9:
            A.append(A[j]*10+8)
            A.append(A[j]*10+9)
            k+=2
        else:
            A.append(A[j]*10+Amod-1)
            A.append(A[j]*10+Amod)
            A.append(A[j]*10+Amod+1)
            k+=3
        if X <=k:
            break
        j+=1
print(A[X-1])

Solution (Python):
import queue

K = int(input())

q = queue.Queue()

counter = 0
for i in range(1, 10):
    q.put(str(i))
    counter += 1
    if counter == K:
        print(i)
        break

while counter < K:
    n = q.get()
    if n[-1] == '0':
        for add in ['0', '1']:
            n_add = n + add
            q.put(n_add)
            counter += 1
            if counter == K:
                print(int(n_add))
                break
    elif n[-1] == '9':
        for add in ['8', '9']:
            n_add = n + add
            q.put(n_add)
            counter += 1
            if counter == K:
                print(n_add)
                break
    else:
        for add in [str(int(n[-1])-1), str(int(n[-1])), str(int(n[-1])+1)]:
            n_add = n + add
            q.put(n_add)
            counter += 1
            if counter == K:
                print(n_add)
                break

Solution (Python):
from collections import deque

n = int(input())

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

k = 1
while c < n:
    k = q.popleft()
    
    if k%10:
        q.append(10*k + k%10 - 1)
    q.append(10 * k + k % 10)
    if k%10 != 9:
        q.append(10*k + (k%10) + 1)
    c += 1

print(k)

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

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

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

Solution (Python):
def main():
    K = int(input())
    from collections import deque
    A = deque([1,2,3,4,5,6,7,8,9])
    a = 0
    while True:
        x = A.popleft()
        xmod10 = x % 10
        if xmod10 != 0:
            A.append(10*x + xmod10 - 1)
        A.append(10*x + xmod10)
        if xmod10 != 9:
            A.append(10*x + xmod10 + 1)
        a += 1
        if a == K:
            print(x)
            break

if __name__ == "__main__":
    main()

Solution (Python):
def resolve():
    k = int(input())
    from collections import deque
    a = [1,2,3,4,5,6,7,8,9]
    b = [1,2,3,4,5,6,7,8,9]
    if k < 10:
        print(a[k-1])
    else:
        a = deque(a)
        b = deque(b)
        while len(b) <= k:
            test = a.popleft()
            mtest = test % 10
            if mtest == 0:
                a.append (test*10)
                a.append (test*10+mtest+1)
                b.append (test*10)
                b.append (test*10+mtest+1)
            elif mtest == 9:
                a.append (test*10 + mtest-1)
                a.append (test*10 + mtest)
                b.append (test*10 + mtest-1)
                b.append (test*10 + mtest)
            else:
                a.append (test*10 + mtest-1)
                a.append (test*10 + mtest)
                a.append (test*10 + mtest+1)
                b.append (test*10 + mtest-1)
                b.append (test*10 + mtest)
                b.append (test*10 + mtest+1)
        print(b[k-1])
resolve()

Solution (Python):
def resolve():
    k = int(input())
    from collections import deque
    a = [1,2,3,4,5,6,7,8,9]
    b = [1,2,3,4,5,6,7,8,9]
    if k < 10:
        print(a[k-1])
    else:
        a = deque(a)
        b = deque(b)
        while len(b) <= k:
            test = a.popleft()
            mtest = test % 10
            if mtest == 0:
                a.append (test*10)
                a.append (test*10+mtest+1)
                b.append (test*10)
                b.append (test*10+mtest+1)
            elif mtest == 9:
                a.append (test*10 + mtest-1)
                a.append (test*10 + mtest)
                b.append (test*10 + mtest-1)
                b.append (test*10 + mtest)
            else:
                a.append (test*10 + mtest-1)
                a.append (test*10 + mtest)
                a.append (test*10 + mtest+1)
                b.append (test*10 + mtest-1)
                b.append (test*10 + mtest)
                b.append (test*10 + mtest+1)
        print(b[k-1])
resolve()

Solution (Python):
def is_lunlun(n):
    m = str(n)
    for i in range(1,len(m)):
        if abs(int(m[i]) - int(m[i-1])) > 1:
            return False
    return True

def main():
    K = int(input())
    A = [format(str(i),"0>5") for i in range(100000) if is_lunlun(i)]
    B = [int(a1+a2) for a1 in A for a2 in A if int(a1+a2) < 3234566668 and is_lunlun(int(a1+a2))]
    B2 = sorted(set(B))
    print(B2[K])

if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
from collections import deque
k=deque([])
z=9
m=0
if n<10:
    print(n)
    exit()
for i in range(1,10):
    k.append(i)
while z!=n:
    m=k.popleft()
    if m%10!=0:
        ans=10*m+(m%10)-1
        k.append(ans)
        z+=1
        if z==n:
            print(ans)
            exit()
    ans=10*m+(m%10)    
    k.append(ans)
    z+=1
    if z==n:
        print(ans)
        exit()
    if m%10!=9:
        ans=10*m+(m%10)+1
        k.append(ans)
        z+=1
        if z==n:
            print(ans)
            exit()

Solution (Python):
ans = set()
def f(x):
    if len(x) <= 10:
        ans.add(int(x))
        if int(x[-1]) == 0:
            f(x + "1")
            f(x + x[-1])
        elif int(x[-1]) == 9:
            f(x + "8")
            f(x + x[-1])
        else:
            u = str(int(x[-1]) + 1)
            d = str(int(x[-1]) - 1)
            f(x + u)
            f(x + d)
            f(x + x[-1])
for i in range(1,10):
    f(str(i))
ans = list(ans)
ans.sort()

k = int(input())
print(ans[k-1])

Solution (Python):
from collections import deque

K = int(input())
q = deque([i for i in range(1, 10)])
for i in range(K):
    x = q.popleft()
    if x%10 != 0:
        q.append(x*10+x%10-1)
    q.append(x*10+x%10)
    if x%10 != 9:
        q.append(x*10+x%10+1)
    if i == K-1:
        print (x)

Solution (Python):
def create_mapper():
	
	
	
	
	
	
	
	
	res = [[]]*10
	for i in range(0, 10):
		if 1 <= i <= 8:
			res[i] = [i-1, i, i+1]
		elif i == 9:
			res[i] = [8, 9]
		elif i == 0:
			res[i] = [0, 1]
	return res
mapper = create_mapper()

def map_list(lst, level):
	res = lst[::1]
	while not all([len(elem) == level for elem in res]):
		new_res = []
		for elem in res:
			if len(elem) < level:
				tmp = []
				for digit in mapper[int(elem[-1])]:
					tmp.append(elem + str(digit))
				new_res += tmp
				
		res = new_res[::1]
		
		
	return res

def create_lun():
	res = [i for i in range(1, 10)]
	
	for depth in range(2, 11): 
		tmp = [str(i) for i in range(1, 10)] 
		tmp = map_list(tmp, depth)
		tmp = sorted(list(map(int, tmp)))
		res += tmp
		
	
	return res
table = create_lun()
k = int(input())
print(table[k-1])

Solution (Python):
from collections import deque

def make_lunlun():
    lst = []
    que = deque([1,2,3,4,5,6,7,8,9])
    for i in range(100000):
        str_num = str(que.popleft())
        str_one = str_num[-1]
        a = str(int(str_one) - 1)
        b = str(int(str_one) + 1)
        
        same = int(str_num + str_one)
        
        if 0 < int(str_one) < 9:
            minus = int(str_num + a)
            plus = int(str_num + b)
            que.extend([minus,same,plus])
            lst.extend([minus,same,plus])
        elif int(str_one) == 0:
            plus = int(str_num + b)
            que.extend([same,plus])
            lst.extend([same,plus])
        else:
            minus = int(str_num + a)
            que.extend([minus,same])
            lst.extend([minus,same])
    print(lst[K - 10])    

K = int(input())
if K <= 12:
    print(K)
else:
    make_lunlun()

Solution (Python):
k=int(input())
from collections import deque
lunlun=deque([i for i in range(1,10)])
for i in range(10**5):
  a=lunlun.popleft()
  if not a%10==0:
    lunlun.append(a*10+a%10-1)
  lunlun.append(a*10+a%10)
  if not a%10==9:
    lunlun.append(a*10+a%10+1)
  if i==k-1:
    break

print(a)

Solution (Python):
def last_number(n):
    if n == 0:
        return [0, 1]
    elif n == 9:
        return [8, 9]
    else:
        return [n-1, n, n+1]

k = int(input())
lun = {1, 2, 3, 4, 5, 6, 7, 8, 9}
temp = set()
while len(lun) < k:
    for i in lun:
        last = int(str(i)[-1])
        for j in last_number(last):
            temp.add(int(str(i) + str(j)))
    lun.update(temp)
    temp = set()
answer = sorted(list(lun))
print(answer[k - 1])

Solution (Python):
from collections import deque

k = int(input())
cand = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
temp = []
for i in range(k):
    t = cand.popleft()
    temp.append(t)
    if t % 10 != 0:
        cand.append(t*10+(t%10-1))
    cand.append(t*10+(t%10))
    if t % 10 != 9:
        cand.append(t*10+(t%10+1))
print(temp[k-1])

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

q = queue.Queue()
[q.put(i) for i in range(1, 10)]
for _ in range(K):
    num = q.get()
    mod = num % 10
    deca = num * 10 + mod 
    if mod != 0:
        q.put(deca - 1)
    q.put(deca)
    if mod != 9:
        q.put(deca + 1)
        
print(num)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
from heapq import heappush, heappop, heapify

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

  q = [i for i in range(1, 11)]
  heapify(q)
  used = set()

  while K:
      n = heappop(q)

      if n in used: continue
      used.add(n)
      K -= 1

      if K == 0:
          print(n)
          break

      last = n % 10

      if last == 0: 
          heappush(q, n*10)
          heappush(q, n*10+1)
      elif last == 9:
          heappush(q, n*10+last)
          heappush(q, n*10-1+last)
      else:
          heappush(q, n*10+last)
          heappush(q, n*10+1+last)
          heappush(q, n*10-1+last)
if __name__ == '__main__':
  	main()

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

Solution (Python):
import collections

k = int(input())

li = [str(i) for i in range(1,10)]
q = collections.deque(li)
count = 0
n = 10 ** 6

for i in range(1, n):
    a = q.popleft()
    count += 1
    if count == k:
        print(a)
        exit(0)
    num = int(a[-1])
    if num != 0:
        aa = a + str(num-1)
        q.append(aa)
    aa = a + str(num)
    q.append(aa)
    if num != 9:
        aa = a + str(num+1)
        q.append(aa)

Solution (Python):
import queue

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

n = 0
while True:
  val = q.get()
  n += 1
  if n == k:
    print(val)
    break

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

Solution (Python):
import queue

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

n = 0
while True:
  val = q.get()
  n += 1
  if n == k:
    print(val)
    break

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

Solution (Python):
ans = []
def dfs(i, pre, now):
    global ans
    ans.append(now)
    if i > 10:
        return
    dfs(i + 1, pre, now * 10 + pre)
    if pre + 1 < 10:
        dfs(i + 1, pre + 1, now * 10 + pre + 1)
    if pre - 1 > -1:
        dfs(i + 1, pre - 1, now * 10 + pre - 1)

k = int(input())
for i in range(1, 10):
    dfs(1, i, i)
ans.sort()

print(ans[k - 1])

Solution (Python):
from collections import deque

k = int(input())

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

if k <= 9:
    print(k)
    exit()

cnt = 9

while cnt <= 10**5:
    a = d.popleft()
    if a%10 != 0:
        num = 10*a + a%10 - 1
        d.append(num)
        cnt += 1
        if cnt == k:
            print(num)
            exit()

    num = 10*a + a%10
    d.append(num)
    cnt += 1
    if cnt == k:
        print(num)
        exit()
    
    if a%10 != 9:
        num = 10*a + a%10 +1
        d.append(num)
        cnt += 1
        if cnt == k:
            print(num)
            exit()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
K = int(input())
all = []
def dfs(number):
    all.append(number)
    if len(str(number)) == 10:
        return
    first_digit = int(str(number)[-1])
    for n_number in range(first_digit-1, first_digit+2):
        if n_number >= 0 and n_number <= 9:
            dfs(number*10+n_number)

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
K = int(input())
all = []
def dfs(number):
    all.append(number)
    if len(str(number)) == 10:
        return
    for i in range(-1, 2):
        n_number = number % 10 + i
        if n_number >= 0 and n_number <= 9:
            dfs(number*10+n_number)

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

Solution (Python):
from collections import deque


K = int(input())


dq = deque()
cnt = 0

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

if K > 9:
    cnt = 9
    while cnt < K:
        t = dq.popleft()
        t = t*10 + t%10
        if t%10 != 0:
            dq.append(t-1)
            cnt += 1
        dq.append(t)
        cnt += 1
        if t%10 != 9:
            dq.append(t+1)
            cnt += 1

print(dq[K-cnt-1])

Solution (Python):
'''987
988
989
998
999
899
elif lunlun[len(lunlun)-1:]=="99":
		num = nextLun(lunlun[:len(lunlun-1])
		return num+
'''
K = int(input())

def nextLun(lunlun):
	notAllowed = [1,2,3,4,5,6,7,8]
	if len(lunlun)==1:
		return str(int(lunlun)+1)
		
	elif int(lunlun[len(lunlun)-2])+1>=int(lunlun[len(lunlun)-1])+1 and len(str(int(lunlun[len(lunlun)-1])+1))==1:
		
		return str(int(lunlun)+1)
	else:
		num = nextLun(lunlun[:len(lunlun)-1])
		if num[len(num)-1]=="0":
			return num+"0"
		else:
			
			return num+str((int(num[len(num)-1])-1))
def getLun(K):
	lunlun = ["1","2","3","4","5","6","7","8","9"]
	while len(lunlun)<K:
		lunlun.append(nextLun(lunlun[len(lunlun)-1]))
	return lunlun[K-1]
print(getLun(K))

Solution (Python):
def lunlun(n):
	nums = set([1, 2, 3, 4, 5, 6, 7, 8, 9])
	while len(nums) < n:
		old_nums = list(nums)
		for num in old_nums:
			num = str(num)
			if num[-1] == '0':
				adds = num + '0'
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + '1'
				if int(adds) not in nums:
					nums.add(int(adds))
			elif num[-1] == '9':
				adds = num + '9'
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + '8'
				if int(adds) not in nums:
					nums.add(int(adds))
			else:
				adds = num + str(int(num[-1]) - 1)
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + str(int(num[-1]))
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + str(int(num[-1]) + 1)
				if int(adds) not in nums:
					nums.add(int(adds))
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			

	nums = list(nums)
	nums = sorted(nums)
	return nums[n - 1]

n = int(input())
print(lunlun(n))

Solution (Python):
def lunlun(n):
	nums = set([1, 2, 3, 4, 5, 6, 7, 8, 9])
	while len(nums) < n:
		old_nums = list(nums)
		for num in old_nums:
			num = str(num)
			if num[-1] == '0':
				adds = num + '0'
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + '1'
				if int(adds) not in nums:
					nums.add(int(adds))
			elif num[-1] == '9':
				adds = num + '9'
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + '8'
				if int(adds) not in nums:
					nums.add(int(adds))
			else:
				adds = num + str(int(num[-1]) - 1)
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + str(int(num[-1]))
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + str(int(num[-1]) + 1)
				if int(adds) not in nums:
					nums.add(int(adds))
			if num[0] == '1':
				adds = '1' + num
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = '2' + num
				if int(adds) not in nums:
					nums.add(int(adds))
			elif num[0] == '9':
				adds = '8' + num
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = '9' + num
				if int(adds) not in nums:
					nums.add(int(adds))
			else:
				adds = str(int(num[0]) - 1) + num
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = str(int(num[0])) + num
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = str(int(num[0]) + 1) + num
				if int(adds) not in nums:
					nums.add(int(adds))

	nums = list(nums)
	nums = sorted(nums)
	return nums[n - 1]

n = int(input())
print(lunlun(n))

Solution (Python):
from collections import deque
def main(k):
    q = deque([])
    for i in range(1, 10):
        q.append(i)
    
    count = 0
    top = -1
    
    while True:
        top = q.popleft()
 
        count += 1
        if count == k:
            return top
 
        if top%10 != 0:
            q.append(top*10 + top%10-1)
        q.append(top*10 + top%10)
        if top%10 != 9:
            q.append(top*10 + top%10 + 1)
 
    return top
k = int(input())
print(main(k))

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):
    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(q.get())

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

Solution (Python):
import queue

k = int(input())

q = queue.Queue()
x = 0

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

for j 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())
lunlun = [i+1 for i in range(9)]

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
        

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

Solution (Python):
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):
from queue import Queue

k=int(input())

q = Queue()
count = 0

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

for _ in range(k):
    count = q.get()

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

    if count%10 != 9:
        q.put(10*count + (count%10) + 1)

print(count)

Solution (Python):
import queue


def D():
    
    k=int(input())
    q = queue.Queue()
    for i in range(1,10): q.put(i)
    
    for i in range(k):
        valu=q.get()
        if i==k-1: print(valu)
        
        if valu%10 != 0: q.put((10*valu)+(valu%10)-1)
        q.put((10*valu)+(valu%10))
        if valu%10 !=9: q.put((10*valu)+(valu%10)+1)
        
        
        
if __name__=='__main__':
    D()

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

queue = list(range(1, 10))

if K < 10:
    print(K)
else:
    i = 0
    while K > len(queue):
        if queue[i] % 10 != 0:
            l = 10 * queue[i] + queue[i] % 10 - 1
            queue.append(l)
        
        l = 10 * queue[i] + queue[i] % 10
        queue.append(l)
        
        if queue[i] % 10 != 9:
            l = 10 * queue[i] + queue[i] % 10 + 1
            queue.append(l)
        
        i += 1

    print(queue[K - 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(1,k):
    l = q.popleft()
    if (len(q) < k):
        m = l % 10
        if (m != 0):
            q.append(l * 10 + m - 1)
        q.append(l * 10 + m)
        if (m != 9):
            q.append(l * 10 + m + 1)

print(q.popleft())

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

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



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

Solution (Python):
def main():
    K = int(input())
    ans = 0
    counter = 0
    while True:
        ans += 1
        s_ans = str(ans)
        c_flag = True
        l_ans = len(s_ans)
        skip = 0
        for j in range(1, l_ans):
            if abs(int(s_ans[j])-int(s_ans[j-1])) > 1:
                c_flag = False
                skip = 10**(l_ans-j-1)-1
                break
            if j < l_ans-1 and abs(int(s_ans[j])-int(s_ans[j+1])) > 1:
                c_flag = False
                skip = 10**(l_ans-j-2)-1
                break
        if c_flag == True:
            counter += 1
        else:
            ans += skip
        if counter == K:
            break
    
    print(ans)

main()

Solution (Python):
def dfs(c,l):
  n=list()
  for i in l:
    for j in range(max(0,i%10-1),min(i%10+2,10)):
      n.append(i*10+j)
      c-=1
      if c==0:
        return i*10+j
  else:
    return dfs(c,n)

K=int(input())
print(K if K<10 else dfs(K-9,[1,2,3,4,5,6,7,8,9]))

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

Solution (Python):
k=int(input())
ok=3234566667
ng=0
while ok-ng>1:
  mid=(ok+ng)//2
  s=str(mid)
  dp=[[[0]*2 for _ in range(10)] for _ in range(len(s))]
  for i in range(1,int(s[0])):
    dp[0][i][1]+=1
  dp[0][int(s[0])][0]+=1
  for i in range(1,len(s)):
    for j in range(10):
      if j!=0:
        dp[i][j][1]+=dp[i-1][j][1]+1
      else:
        dp[i][j][1]+=dp[i-1][j][1]
      if j>=1:
        dp[i][j-1][1]+=dp[i-1][j][1]
        if int(s[i])==j-1 and int(s[i-1])==j:
          dp[i][j-1][0]+=dp[i-1][j][0]
        if int(s[i])>j-1:
          dp[i][j-1][1]+=dp[i-1][j][0]
      if j<=8:
        dp[i][j+1][1]+=dp[i-1][j][1]
        if int(s[i])==j+1 and int(s[i-1])==j:
          dp[i][j+1][0]+=dp[i-1][j][0]
        if int(s[i])>j+1:
          dp[i][j+1][1]+=dp[i-1][j][0]
      if int(s[i])==j and int(s[i-1])==j:
        dp[i][j][0]+=dp[i-1][j][0]
      if int(s[i])>j:
        dp[i][j][1]+=dp[i-1][j][0]
  cnt=0
  for i in range(10):
    cnt+=sum(dp[len(s)-1][i])
  if cnt>=k:
    ok=mid
  else:
    ng=mid
print(ok)

Solution (Python):
import queue

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

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

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

print(q.get())

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

k = int(readline())
runrun = [i + 1 for i in range(9)]
ans = runrun
for n in range(11):
    check = runrun
    runrun = []
    for x in check:
        if x > 3234566667:
            break
        y = x % 10
        if y > 0:
            runrun.append(x * 10 + y - 1)
        runrun.append(x * 10 + y)
        if y < 9:
            runrun.append(x * 10 + y + 1)
    ans += runrun
print(ans[k - 1])