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):
def main():
    K = int(input())
    lunlun_cnt = 0
    x = 1
    answer = 0
    while lunlun_cnt < K:
        x_is_lunlun = True
        str_x = str(x)
        length = len(str_x)
        for d in range(2, length + 1):
            
            if abs(int(str_x[d - 2]) - int(str_x[d - 1])) > 1:
                x_is_lunlun = False
                x += 10**(length - d)
                break
        if x_is_lunlun:
            lunlun_cnt += 1
            answer = x
            x += 1
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
k=int(input())
x=[i for i in range(1,10)]
for i in range(k//2):
  if x[i]%10!=0:
    x.append(10*x[i]+x[i]%10-1)
  x.append(10*x[i]+x[i]%10)
  if x[i]%10!=9:
    x.append(10*x[i]+x[i]%10+1)
print(x[k-1])

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

present = [1,2,3,4,5,6,7,8,9]
while K >= len(present):
    K -= len(present)
    next = []
    for i in range(len(present)):
        tmp = present[i]
        r = tmp % 10
        if r != 0:
            next.append(tmp * 10 + r -1)
        next.append(tmp * 10 + r)
        if r != 9:
            next.append(tmp * 10 + r +1)
    present = next

print(present[K-1])

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def main():
    K = int(input())
    que = deque(["1", "2", "3", "4", "5", "6", "7", "8", "9"])
    if K <= 9:
        print(que[K-1])
    else:
        K -= 9
        while K >= 0:
            v = que.popleft()
            if v[-1] != "0":
                K -= 1
                v1 = v + str(int(v[-1])-1)
                if K == 0:
                    print(v1)
                    break
                que.append(v1)
            K -= 1
            v2 = v + v[-1]
            if K == 0:
                print(v2)
                break
            que.append(v2)
            if v[-1] != "9":
                K -= 1
                v3 = v + str(int(v[-1])+1)
                if K == 0:
                    print(v3)
                    break
                que.append(v3)
if __name__ == "__main__":
    main()

Solution (Python):
K = int(input())
a = [i+1 for i in range(9) ] 
old_a = []

while True:
    a = list(set(a))
    if K <= len(a):
        a = sorted(a)
        break
    
    old_a = a.copy()
    for x in old_a:
        for i in range(-1,2):
            d = int(x%10) + i
            if (d < 0) or (d > 9):
                continue
            nx = x*10 + d
            a.append(nx)

print(a[K-1])

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

Solution (Python):
from collections import deque
K=int(input())
d = deque([1,2,3,4,5,6,7,8,9])
i=0
while 1:
  i+=1
  a=d.popleft()
  if i==K:
    print(a);exit()
    
  b=a%10
  if b==0:
    d.append(int(str(a)+"0"))
    d.append(int(str(a)+"1"))
  elif b==9:
    d.append(int(str(a)+"8"))
    d.append(int(str(a)+"9"))
  else:
    d.append(int(str(a)+str(b-1)))
    d.append(int(str(a)+str(b)))
    d.append(int(str(a)+str(b+1)))

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

Solution (Python):

import sys
import queue

def solve(K: int):
    q = queue.Queue()
    
    for i in range(1, 10):
        q.put(i)
    
    for i in range(K):
        res = q.get()
        first = res % 10
        if first == 0:
            q.put(res * 10 + first)
            q.put(res * 10 + first + 1)
        elif first == 9:
            q.put(res * 10 + first - 1)
            q.put(res * 10 + first)
        else:
            q.put(res * 10 + first - 1)
            q.put(res * 10 + first)
            q.put(res * 10 + first + 1)

    print(res)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  
    solve(K)

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(1,K+1):
    deq=Q.get()
    mod=deq%10
    if mod!=0:
        Q.put(10*deq+mod-1)
    Q.put(10*deq+mod)
    if mod!=9:
        Q.put(10*deq+mod+1)
print(deq)

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

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

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

Solution (Python):
from queue import Queue
from sys import stdin, stdout

def check(arr):
    a = int(''.join(str(each) for each in arr))
    if a < 10:
        return True
    for i in range(1,len(arr)):
        if abs(arr[i] - arr[i - 1]) > 1:
            return False
    return True

arr = [0] * 10

arr[9] = 1
k = 0
limit = int(stdin.readline().strip())

for aa in range(0, 10):
    if aa == 0:
        brange = range(0, 10)
    else:
        brange = range(max(0, aa - 1), min(10, aa + 2))
    for bb in brange:
        if aa+bb == 0:
            crange = range(0, 10)
        else:
            crange = range(max(0, bb - 1), min(10, bb + 2))
        for cc in crange:
            if aa+bb+cc == 0:
                drange = range(0, 10)
            else:
                drange = range(max(0, cc - 1), min(10, cc + 2))
            for dd in drange:
                if aa+bb+cc+dd == 0:
                    erange = range(0, 10)
                else:
                    erange = range(max(0, dd - 1), min(10, dd + 2))
                for ee in erange:
                    if aa+bb+cc+dd+ee == 0:
                        frange = range(0, 10)
                    else:
                        frange = range(max(0, ee - 1), min(10, ee + 2))
                    for ff in frange:
                        if aa+bb+cc+dd+ee+ff == 0:
                            grange = range(0, 10)
                        else:
                            grange = range(max(0, ff - 1), min(10, ff + 2))
                        for gg in grange:
                            if aa+bb+cc+dd+ee+ff+gg == 0:
                                hrange = range(0, 10)
                            else:
                                hrange = range(max(0, gg - 1), min(10, gg + 2))
                            for hh in hrange:
                                if aa+bb+cc+dd+ee+ff+gg+hh == 0:
                                    irange = range(0, 10)
                                else:
                                    irange = range(max(0, hh - 1), min(10, hh + 2))
                                for ii in irange:
                                    if aa+bb+cc+dd+ee+ff+gg+hh+ii == 0:
                                        jrange = range(0, 10)
                                    else:
                                        jrange = range(max(0, ii - 1), min(10, ii + 2))
                                    for jj in jrange:
                                        k += 1
                                        
                                        
                                        
                                        if k > limit:
                                            arr = [aa, bb, cc, dd, ee, ff, gg, hh, ii, jj]
                                            num = int(''.join(str(each) for each in arr))
                                            stdout.writelines("%d\n" % num)
                                            exit(0)

Solution (Python):
"""
解説見た
"""
from queue import Queue

q = Queue()

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

k = int(input())

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

print(q.get())

Solution (Python):
def f(n, d, s, k):
    if d == 0:
        k -= 1
        if k == 0:
            print(s)
            exit(0)
        return k

    if n - 1 >= 0:
        k = f(n - 1, d - 1, s + (n - 1) * (10 ** (d - 1)), k)

    k = f(n, d - 1, s + (n) * (10 ** (d - 1)), k)

    if n + 1 <= 9:
        k = f(n + 1, d - 1, s + (n + 1) * (10 ** (d - 1)), k)
    return k


k = input()
k = int(k)

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

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

k = k - 9

for i in range(1, 100000):
    for j in l:
        k = f(j, i, j * (10 ** i), k)

Solution (Python):
import queue as qu

k = int(input())

q = qu.Queue()

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

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

print(q.get())

Solution (Python):
import heapq

k = int(input())
i=0
lunlun = [1,2,3,4,5,6,7,8,9]
heapq.heapify(lunlun)

while True:
    i += 1
    if i == k:
        break
    x = heapq.heappop(lunlun)
    if x % 10 != 0:
        heapq.heappush(lunlun,10 * x + (x % 10) -1)
    heapq.heappush(lunlun,10 * x + (x % 10))
    if x % 10 != 9:
        heapq.heappush(lunlun,10 * x + (x % 10) +1)

print(lunlun[0])

Solution (Python):
from collections import deque
k=int(input())
li=deque([i for i in range(1,10)])
cnt=9
if k<=cnt:print(k)
else:
    while cnt<k:
        v=li.popleft()
        if v%10==0:
            li.append(v*10)
            li.append(v*10+1)
            cnt+=2
        elif v%10==9:
            li.append(v*10+8)
            li.append(v*10+9)
            cnt+=2
        else:
            r=v%10
            li.append(v*10+r-1)
            li.append(v*10+r)
            li.append(v*10+r+1)
            cnt+=3
    print(li[k-cnt-1])

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

Solution (Python):
from collections import deque


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    K = read_int()
    if K < 10:
        return K
    Q = deque(range(1, 10))
    counter = 10
    while True:
        num = Q.popleft()
        digit = num%10
        for d in range(-1, 2):
            if 0 <= digit+d < 10:
                if counter == K:
                    return num*10+digit+d
                counter += 1
                Q.append(num*10+digit+d)


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

Solution (Python):
k = int(input())
l = [0 for x in range(100005)]
for i in range(10):
	l[i] = i+1
temp = 0
i = 9
while i < k:
	if l[temp] % 10 == 9:
		l[i] = l[temp] * 10 + 8
		l[i+1] = l[temp] * 10 + 9 
		i+=2
	elif l[temp] % 10 == 0:
		l[i] = l[temp] * 10
		l[i+1] = l[temp] * 10 + 1
		i+=2
	else:
		l[i] = l[temp] * 10 + l[temp] % 10 - 1
		l[i+1] = l[temp] * 10 + l[temp] % 10
		l[i+2] = l[temp] * 10 + l[temp] % 10 + 1
		i+=3
	temp+=1
print(l[k-1])

Solution (Python):
from collections import deque
 
K = int(input())
que = deque([i for i in range(1, 10)])
lunlun = []
 
while que:
    num = que.pop()
    lunlun.append(num)
    for i in range(10):
        if abs(int(str(num)[-1]) - i) <= 1:
            cand = int(str(num) + str(i))
            if cand < 10000000000:
                que.append(cand)
 
lunlun.sort()
print(sorted(lunlun)[K - 1])

Solution (Python):
import queue

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

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

count = 0
while count < k:
    num = q.get()
    num_1 = int((str(num))[-1])
    if num_1 ==0:
        q.put(num*10)
        q.put(num*10+1)
    elif num_1==9:
        q.put(num*10+num_1-1)
        q.put(num*10+num_1)
    else:
        q.put(num*10+num_1-1)
        q.put(num*10+num_1)
        q.put(num*10+num_1+1)
    count+=1
    if k==count:
        ans = num
print(ans)

Solution (Python):
from queue import deque



k = int(input())
q = deque()
for i in range(1,10):
    q.appendleft(i)
for _ in range(k):
    num = q.pop()
    n = num % 10
    if n!=0:
        q.appendleft(num*10+n-1)
    q.appendleft(num*10+n)
    if n!=9:
        q.appendleft(num*10+n+1)
print(num)

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


def main():
    K = int(input().strip())
    que = queue.Queue()
    [que.put(i) for i in range(1, 10)]
    for _ in range(K):
        answer = que.get()
        if answer % 10 != 0:
            que.put(10*answer + answer % 10 - 1)
        que.put(10 * answer + answer % 10)
        if answer % 10 != 9:
            que.put(10*answer + answer % 10 + 1)
    print(answer)


if __name__ == '__main__':
    main()

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

if k <= 9:
    print(k)
else:
    q = queue.Queue()
    for i in range(9):
        q.put(i+1)
    for i in range(k):
        s = q.get()
        if s  % 10 == 0:
            q.put(s * 10)
            q.put(s * 10 + 1)
        elif s  % 10 == 9:
            q.put(s * 10 + 8)
            q.put(s * 10 + 9)
        else:
            t = s  % 10
            q.put(s * 10 + t - 1)
            q.put(s * 10 + t)
            q.put(s * 10 + t + 1)
    print(s)

Solution (Python):
n = int(input())
l = [_ for _ in range(1,10)]

cnt = 9
d = [-1, 0, 1]
for i in range(10**5):
    if cnt >= n: break
    for j in d:
        if 0 <= int(str(l[i])[-1]) + j <= 9:
            l.append(l[i]*10 + int(str(l[i])[-1]) + j)
            cnt += 1

print(l[n-1])

Solution (Python):
n = int(input())
l = [_ for _ in range(1,10)]

cnt = 9
for i in range(10**5):
    if cnt >= n:
        break
    if str(l[i])[-1] == '0':
        l.append(l[i]*10 + int(str(l[i])[-1]))
        l.append(l[i]*10 + int(str(l[i])[-1]) + 1)
        cnt += 2

    elif str(l[i])[-1] == '9':
        l.append(l[i]*10 + int(str(l[i])[-1]) - 1)
        l.append(l[i]*10 + int(str(l[i])[-1]))
        cnt += 2

    else:
        l.append(l[i]*10 + int(str(l[i])[-1]) - 1)
        l.append(l[i]*10 + int(str(l[i])[-1]))
        l.append(l[i]*10 + int(str(l[i])[-1]) + 1)
        cnt += 3

print(l[n-1])

Solution (Python):
n = int(input())
l = [_ for _ in range(1,10)]

for i in range(10**5):
    if str(l[i])[-1] == '0':
        l.append(l[i]*10 + int(str(l[i])[-1]))
        l.append(l[i]*10 + int(str(l[i])[-1]) + 1)

    elif str(l[i])[-1] == '9':
        l.append(l[i]*10 + int(str(l[i])[-1]) - 1)
        l.append(l[i]*10 + int(str(l[i])[-1]))

    else:
        l.append(l[i]*10 + int(str(l[i])[-1]) - 1)
        l.append(l[i]*10 + int(str(l[i])[-1]))
        l.append(l[i]*10 + int(str(l[i])[-1]) + 1)

print(l[n-1])

Solution (Python):
from collections import deque

K = int(input())
LunLun = []
Q = deque()
dx = (-1, 0, 1)
for i in range(1, 10):
    LunLun.append(i)
    Q.append(i)

while len(LunLun) <= K:
    x = Q.popleft()
    y = x % 10
    for i in range(3):
        nx = y + dx[i]
        if (nx >= 0) and (nx <= 9):
            Q.append(10 * x + nx)
            LunLun.append(10 * x + nx)

print(LunLun[K-1])

Solution (Python):
import sys
from collections import deque
K = int(sys.stdin.readline().rstrip())
A = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
d = [-1, 0, 1]

for i in range(K):
    N = str(A.popleft())
    for i in d:
        if 0 <= int(N[-1]) + i <= 9:
            new = N + str(int(N[-1]) + i)
            A.append(int(new))
print(N)

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from collections import deque

def rec(n, k, ans):
    print(ans)
    ans.append(int(k))
    if len(k) >= n:
        return
    d = int(k[-1])
    if d > 0:
        rec(n, k + str(d-1), ans)
    rec(n, k + str(d), ans)
    if d < 9:
        rec(n, k + str(d+1), ans)

def main():
    n = int(input().strip())
    
    
    
    
    
    
    c = 0
    q = deque()
    for i in range(1, 10):
        q.append(str(i))
    while len(q) > 0:
        d = q.popleft()
        c += 1
        if c == n:
            print(d)
            return
        if int(d[-1]) > 0:
            q.append(d + str(int(d[-1])-1))
        q.append(d + d[-1])
        if int(d[-1]) < 9:
            q.append(d + str(int(d[-1])+1))
    
    


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
k = int(input())
d = deque([i for i in range(1,10)])

count = 0
while True:
    num = d.popleft()
    count += 1
    if count == k:
        break
    str_num = str(num)
    next_digit_ls = [int(str_num[-1]) - 1, int(str_num[-1]), int(str_num[-1]) + 1]
    for digit in next_digit_ls:
        if 0<= digit <= 9:
            d.append(int(str_num + str(digit)))
print(num)

Solution (Python):
k=int(input())
if k<=9:
    print(k)
    exit()
a=[1,2,3,4,5,6,7,8,9]
cnt=9
while True:
    q=[]
    for i in a:
       for j in range(10):
            if abs(int(str(i)[-1])-j)<=1:
                cnt+=1
                if cnt==k:
                    print(int(str(i)+str(j)))
                    exit()
                q.append(int(str(i)+str(j)))         
    a=list(sorted(set(q)))

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

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

def lunlun_maker( lun_num, lun_list ):
    if lun_num % 10 == 0:
        lun_list.append( lun_num * 10  )
        lun_list.append( lun_num * 10 + 1 )
    elif lun_num % 10 == 9:
        lun_list.append( lun_num * 10 + 8 )
        lun_list.append( lun_num * 10 + 9 )
    else:
        lun_list.append( lun_num * 10 + ( lun_num % 10 - 1 ) )
        lun_list.append( lun_num * 10 + ( lun_num % 10 ) )
        lun_list.append( lun_num * 10 + ( lun_num % 10 + 1 ) )

i = 0
while len( lunlun_numbers ) < 100000:
    lunlun_maker( lunlun_numbers[i], lunlun_numbers )
    i += 1

print( lunlun_numbers[ k - 1 ] )

Solution (Python):
def main():
    from collections import deque

    k = int(input())
    dq = deque()
    for i in range(1,10):
        dq.append(i)
    
    for i in range(k):
        lnln = dq.popleft()
        r = lnln%10
        if r not in (0,9):
            dq.extend([lnln*10+r-1,lnln*10+r,lnln*10+r+1])
        elif r == 9:
            dq.extend([lnln*10+r-1,lnln*10+r])
        else:
            dq.extend([lnln*10+r,lnln*10+r+1])

    print(lnln)
main()

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

def dfs(val, digit, all):

    all.append(val)

    if digit == 10:
        return

    for i in range(-1, 2):
        add = val % 10 + i
        if 0 <= add <= 9:
            dfs(val*10 + add, digit+1, all)

all = []

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

all.sort()

print(all[K-1])

Solution (Python):
from collections import deque

k = int(input())

q = deque([])

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

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

print(q.popleft())

Solution (Python):
n=int(input())
if 1<=n and n<=9:
    print(n)
else:
    import queue
    q=queue.Queue()
    for i in range(1,10):
        q.put(i)
    count=9
    while count<n:
        t=q.get()
        if t%10==0:
            q.put(10*t)
            q.put(10*t+1)
            count+=2
        elif t%10==9:
            q.put(10*t+8)
            q.put(10*t+9)
            count+=2
        else:
            q.put(10*t+t%10-1)
            q.put(10*t+t%10)
            q.put(10*t+t%10+1)
            count+=3
    if count-n==0:
        if t%10!=9:
            print(10*t+t%10+1)
        else:
            print(10*t+9)
    elif count-n==1:
        if t%10!=9:
            print(10*t+t%10)
        else:
            print(10*t+8)
    else:
        print(10*t+t%10-1)

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

q = Queue()

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

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; 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:"""
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 i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
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)]

k = i()
lunlun_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
tmp_list = lunlun_list
tmp_tmp_list = []
cnt = 9
def lunlun(y):
    x = y[-1]
    if x == "0":
        tmp_tmp_list.append(y + "0")
        tmp_tmp_list.append(y + "1")
        return 2
    elif x == "9":
        tmp_tmp_list.append(y + "8")
        tmp_tmp_list.append(y + "9")
        return 2
    else:
        x = int(x)
        tmp_tmp_list.append(y + str(x - 1))
        tmp_tmp_list.append(y + str(x))
        tmp_tmp_list.append(y + str(x + 1))
        return 3

while len(lunlun_list) < k:
    for tmp in tmp_list:
        cnt += lunlun(str(tmp))
        if cnt >= k:
            break
    tmp_list = tmp_tmp_list
    lunlun_list += tmp_list
    tmp_tmp_list = []

lunlun_list = [int(i) for i in lunlun_list]
lunlun_list.sort()

print(lunlun_list[k - 1])

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; 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:"""
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 i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
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)]

k = i()
lunlun_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
tmp_list = lunlun_list
tmp_tmp_list = []
cnt = 9
def lunlun(y):
    x = y[-1]
    if x == "0":
        tmp_tmp_list.append(y + "0")
        tmp_tmp_list.append(y + "1")
        return 2
    elif x == "9":
        tmp_tmp_list.append(y + "8")
        tmp_tmp_list.append(y + "9")
        return 2
    else:
        x = int(x)
        tmp_tmp_list.append(y + str(x - 1))
        tmp_tmp_list.append(y + str(x))
        tmp_tmp_list.append(y + str(x + 1))
        return 3

while len(lunlun_list) < k:
    for tmp in tmp_list:
        cnt += lunlun(str(tmp))
        if cnt >= k:
            break
    tmp_list = tmp_tmp_list
    lunlun_list += tmp_list
    tmp_tmp_list = []

lunlun_list = [int(i) for i in lunlun_list]
lunlun_list.sort()

print(lunlun_list[k - 1])

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 i == k-1:
        break
    else:
        if not x % 10 == 0:
            q.put(10*x + (x % 10) -1)
        q.put(10*x + (x % 10))
        if not x % 10 == 9:
            q.put(10*x + (x % 10) +1)

print(x)

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

def main():
    K = int(input())
    if K <= 10:
        print(K)
        exit()

    q = deque(range(1, 10))
    K -= 9
    while q:
        v = q.popleft()
        sv = v % 10
        for i in (-1, 0, 1):
            if 0 <= sv + i < 10:
                if K == 1:
                    print(v * 10 + sv + i)
                    exit()
                K -= 1
                q.append(v * 10 + sv + i)

if __name__ == '__main__':
    main()

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

def main():
    K = int(input())
    if K <= 10:
        print(K)
        exit()

    q = deque(range(1, 10))
    K -= 9
    while q:
        v = q.popleft()
        sv = v % 10
        for i in (-1, 0, 1):
            if 0 <= sv + i < 10:
                if K == 1:
                    print(v * 10 + sv + i)
                    exit()
                K -= 1
                q.append(v * 10 + sv + i)

if __name__ == '__main__':
    main()

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

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

p = 0

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

cnt = 1

while cnt < k:
    for i in generate_lunlun(lunlun.popleft()):
        lunlun.append(i)
    cnt += 1
print(lunlun[0])

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

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


h = {u:[u-1,u,u+1] for u in range(1,9)}
h[9] = [8,9]
h[0] = [0,1]

while(k):
	u = q.popleft()
	k -=1
	if k == 0: break
	ld = u % 10
	for delta in h[ld]: q.append(u*10 + delta)
print u

Solution (Python):
import queue

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

counter = 0
for i in range(9):
    q.put(i+1)
while counter < k:
    n = q.get()
    counter += 1
    mod = n % 10
    if mod != 0:
        q.put(10*n+mod-1)
    q.put(10*n+mod)
    if mod != 9:
        q.put(10*n+mod+1)
print(n)

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

Solution (Python):
def main():
    N = int(input())  

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


    for i in l:
        last_digit = i % 10
        num_str = str(i)
        if last_digit != 0: l.append(int(num_str + str((last_digit-1)%10)))
        l.append(int(num_str + str((last_digit)%10)))
        if last_digit != 9: l.append(int(num_str + str((last_digit+1)%10)))
        if len(l) > N: break

    print(l[N-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-1):
    x = Q.get()
    if x%10 != 0:
        Q.put(10*x+x%10-1)
    Q.put(10*x+x%10)
    if x%10 != 9:
        Q.put(10*x+x%10+1)
print(Q.get())

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(10*x+x%10-1)
    Q.put(10*x+x%10)
    if x%10 != 9:
        Q.put(10*x+x%10+1)
print(Q.get())

Solution (Python):
a=int(input())
l=[[0]*10 for _ in range(10)]
l[0]=[1]*10
for i in range(1,10):
    for j in range(10):
        if j!=9 and j!=0:
            l[i][j]=l[i-1][j-1]+l[i-1][j]+l[i-1][j+1]
        elif j==0:
            l[i][j]=l[i-1][j]+l[i-1][j+1]
        else:
            l[i][j]=l[i-1][j-1]+l[i-1][j]
count=0
i=0
while count<a:
    count+=sum(l[i])-l[i][0]
    i+=1
i-=1
count-=sum(l[i])-l[i][0]
j=1
while count<a:
    count+=l[i][j]
    j+=1
j-=1
count-=l[i][j]
k=a-count
ll=[j]
jj=j
for ii in range(i):
    if jj!=0:
        jj-=1
        while k>0:
            k-=l[i-ii-1][jj]
            jj+=1
        jj-=1
        k+=l[i-ii-1][jj]
        ll.append(jj)
    else:
        while k>0:
            k-=l[i-ii-1][jj]
            jj+=1
        jj-=1
        k+=l[i-ii-1][jj]
        ll.append(jj)
        
for jjj in ll:
    print(jjj,end='')

Solution (Python):
import sys
from collections import deque

if __name__ == "__main__":
    k = int(input())

    d = deque()

    for i in range(1, 10):
        d.appendleft(i)
    
    ans = 0

    for _ in range(k):
        ans = d.pop()

        if ans % 10 != 0:
            d.appendleft(10 * ans + ans % 10 - 1)
        d.appendleft(10 * ans + ans % 10)
        if ans % 10 != 9:
            d.appendleft(10 * ans + ans % 10 + 1)
    print(ans)

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

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

print(x)

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

import queue

q = queue.Queue()

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

while c < k:
    x = q.get()
    
    r = x%10
    
    if r!=0 and r!=9:
        q.put(10*x+r-1)
        q.put(10*x+r)
        q.put(10*x+r+1)
        c += 1
    elif r==0:
        q.put(10*x)
        q.put(10*x+1)
        c+=1
    elif r==9:
        q.put(10*x+r-1)
        q.put(10*x+r)
        c+=1
    if c==k:
        print(x)

Solution (Python):
import queue

k = int(input())

q = queue.Queue()

for i in range(1,10):
    q.put(i)
    
c = 0
while c<k:
    x = q.get()
    r = x%10
    if r != 0 and r != 9:
        q.put(10*x+r-1)
        q.put(10*x+r)
        q.put(10*x+r+1)
        c = c+1
    if r == 0:
        q.put(10*x)
        q.put(10*x+1)
        c = c+1
    if r == 9:
        q.put(10*x+r-1)
        q.put(10*x+r)
        c = c+1
    if c == k:
        print(x)