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

arr = ["1","2","3","4","5","6","7","8","9"]
bases = [0,1,2,3,4,5,6,7,8,9]
cnt = 9
q = deque(arr)

while cnt < K:
    num = q.popleft()
    idx = int(num[-1])
    for i in range(idx-1, idx+2):
        if i < 0 or i > 9:
            continue

        q.append(num + str(i))
        arr.append(num + str(i))
        cnt += 1

print(arr[K-1])

Solution (Python):

def get_runrun(runruns):
    newrunrun = []
    for runrun in runruns:
        last = runrun % 10
        if last != 0:
            newrunrun .append(runrun*10+last-1)
        if last != 9:
            newrunrun .append(runrun*10+last+1)
        newrunrun .append(runrun*10+last)
    return newrunrun




def resolve():
    K= int(input())
    runruns = list(range(1,10))

    if K < 10:
        print(K)
        return
    
    while True:
        if len(runruns) >= K:
            break
        K -= len(runruns)
        runruns= get_runrun(runruns)
        runruns.sort()

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



if __name__ == "__main__":

    resolve()

Solution (Python):
k=int(input())
ans=[1,2,3,4,5,6,7,8,9]
def r(a):
    if a%10==0:
        return a*10,a*10+1
    elif a%10==9:
        return a*10+8,a*10+9
    else:
        x=a*10+(a%10)
        return x-1,x,x+1
t=0
while len(ans)<k:
    ans.extend(r(ans[t]))
    t+=1
print(ans[k-1])

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

lunlun = [[] for _ in range(11)]
lunlun[1] = list(range(1, 10))

for i in range(2, 11):
    tmp = []
    for j in lunlun[i-1]:
        x = int(str(j)[-1])
        if 1 <= x <= 8:
            tmp.extend([int(str(j) + str(x-1)), int(str(j) + str(x)), int(str(j) + str(x+1))])
        elif int(str(j)[-1]) == 0:
            tmp.extend([int(str(j) + str(x)), int(str(j) + str(x+1))])
        else:
            tmp.extend([int(str(j) + str(x-1)), int(str(j) + str(x))])
    lunlun[i] = list(set(tmp))

lunlun_flat = []
for x in lunlun:
    for y in x:
        lunlun_flat.append(y)
lunlun_flat = list(set(lunlun_flat))
lunlun_flat.sort()

print(lunlun_flat[K-1])

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

sys.setrecursionlimit(10**7)

k = int(input())
data = [1,2,3,4,5,6,7,8,9]
def dfs(prenum,numberstr):
  if int(numberstr) > 3234566667:return
  if prenum - 1 >= 0:
    data.append(int(numberstr+str(prenum-1)))
    dfs(prenum-1,numberstr+str(prenum-1))
  data.append(int(numberstr+str(prenum)))
  dfs(prenum,numberstr+str(prenum))
  if prenum +1 <= 9:
    data.append(int(numberstr+str(prenum+1)))
    dfs(prenum+1,numberstr+str(prenum+1))
for i in range(1,10):
  dfs(i,str(i))
data.sort()
print(data[k-1])

Solution (Python):
k=int(input())
cand=[[1,2,3,4,5,6,7,8,9]]
for _ in range(9):
    tmp=[]
    for val in cand[-1]:
        s=str(val)
        if s[-1]=='0':
            tmp.append(val*10)
            tmp.append(val*10+1)
        elif s[-1]=='9':
            tmp.append(val*10+8)
            tmp.append(val*10+9)
        else:
            tmp.append(val*10+(int(s[-1])-1))
            tmp.append(val*10+(int(s[-1])))
            tmp.append(val*10+(int(s[-1])+1))
    cand.append(tmp)
ans=[]
for i in range(len(cand)):
    for val in cand[i]:
        ans.append(val)
ans=sorted(ans)
print(ans[k-1])

Solution (Python):

k = int(input())
data = [str(i) for i in range(1,10)]
ans = [i for i in range(1,10)]
for i in range(9):
    data2 = []
    for x in data:
        j = int(x[-1])
        if j-1>=0:
            y = x+str(j-1)
            data2.append(y)
            ans.append(int(y))
        y = x+str(j)
        data2.append(y)
        ans.append(int(y))
        if j+1<10:
            y = x + str(j+1)
            data2.append(y)
            ans.append(int(y))
    data = data2

print(ans[k-1])

Solution (Python):
n = int (input())
runrun = [i+1 for i in range(9)]
count = 9
if n < 10:
    print(runrun[n-1])
    exit(0)


def calc_next_runrun(runrun, count):
    new_runrun=[]
    for run in runrun:
        hitoketa = run % 10
        if hitoketa == 0:
            new_runrun.append(run*10 + 0)
            new_runrun.append(run*10 + 1)
        elif hitoketa == 9:
            new_runrun.append(run*10 + 8)
            new_runrun.append(run*10 + 9)
        else:
            new_runrun.append(run*10 + hitoketa -1)
            new_runrun.append(run*10 + hitoketa )
            new_runrun.append(run*10 + hitoketa +1)
    new_count = len(new_runrun)
    if new_count + count >= n:
        print(new_runrun[n-count-1])
    else:
        calc_next_runrun(new_runrun, new_count+count)

calc_next_runrun(runrun, count)

Solution (Python):
k=int(input())
l=[]
for i1 in range(10):
  l.append(i1)
  for i2 in range(max(i1-1,0),min(i1+2,10)):
    l.append(i1*(10**1)+i2)
    for i3 in range(max(i2-1,0),min(i2+2,10)):
      l.append(i1*(10**2)+i2*(10**1)+i3)
      for i4 in range(max(i3-1,0),min(i3+2,10)):
        l.append(i1*(10**3)+i2*(10**2)+i3*(10**1)+i4)
        for i5 in range(max(i4-1,0),min(i4+2,10)):
          l.append(i1*(10**4)+i2*(10**3)+i3*(10**2)+i4*(10**1)+i5)
          for i6 in range(max(i5-1,0),min(i5+2,10)):
            l.append(i1*(10**5)+i2*(10**4)+i3*(10**3)+i4*(10**2)+i5*(10**1)+i6)
            for i7 in range(max(i6-1,0),min(i6+2,10)):
              l.append(i1*(10**6)+i2*(10**5)+i3*(10**4)+i4*(10**3)+i5*(10**2)+i6*(10**1)+i7)
              for i8 in range(max(i7-1,0),min(i7+2,10)):
                l.append(i1*(10**7)+i2*(10**6)+i3*(10**5)+i4*(10**4)+i5*(10**3)+i6*(10**2)+i7*(10**1)+i8)
                for i9 in range(max(i8-1,0),min(i8+2,10)):
                  l.append(i1*(10**8)+i2*(10**7)+i3*(10**6)+i4*(10**5)+i5*(10**4)+i6*(10**3)+i7*(10**2)+i8*(10**1)+i9)
                  for i10 in range(max(i9-1,0),min(i9+2,10)):
                    l.append(i1*(10**9)+i2*(10**8)+i3*(10**7)+i4*(10**6)+i5*(10**5)+i6*(10**4)+i7*(10**3)+i8*(10**2)+i9*(10**1)+i10)

l=list(set(l))
l.sort()
print(l[k])

Solution (Python):
K = int(input())
A = "0123456789"
S = []
def f(n):
    global A,S
    if len(n)>10:return
    if n[-1]=="0":
        D=(n+"0",n+"1")
    elif n[-1]=="9":
        D=(n+"9",n+"8")
    else:
        a = A.index(n[-1])
        D=(n+A[a],n+A[a-1],n+A[a+1])
    for d in D:
        S.append(int(d))
        f(d)

for i in range(1,10):
    S.append(i)
    f(str(i))
S.sort()
print(S[K-1])

Solution (Python):
import sys

k = int(input())

count = 1
num = 1
l = [str(i+1) for i in range(9)]

if k < 10:
	print(l[k-1])
	sys.exit()

c = 0
while True:
	num = l[c]
	num = int(num[-1])
	if num != 0:
		l.append(l[c]+str(num-1))
	l.append(l[c]+str(num))
	if num != 9:
		l.append(l[c]+str(num+1))

	c += 1
	if len(l) >= k:
		break

print(l[k-1])

Solution (Python):
from collections import deque

n = int(input())
q = deque([str(i) for i in reversed(range(1,10,1))])

count = 0

while True:
    item = q.pop()
    last_int = int(item[-1])

    if last_int != 0:
        q.appendleft(item+str(last_int-1))
    q.appendleft(item+str(last_int))

    if last_int != 9:
        q.appendleft(item+str(last_int+1))

    count += 1
    if count == n:
        break

print(item)

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

runrun = []
run = list(range(0,10))
runrun.extend(run)

for i in range(10):
    k = 10**i
    trun = []
    for r in run:
        t = r//k
        trun.append(t*10*k + r)
        if t > 0:
            trun.append((t-1)*10*k + r)
        if t < 9:
            trun.append((t+1)*10*k + r)
    runrun.extend(trun)
    run = trun

runrun = list(set(runrun))
runrun.sort()
print(runrun[K])

Solution (Python):
from copy import deepcopy
def main():
    K = int( input())
    T = [[1,2,3,4,5,6,7,8,9]]
    for i in range(10):
        S = T[i]
        R = []
        for s in S:
            t = s%10
            if t == 0:
                R.append(s*10)
                R.append(s*10+1)
            elif t%10 == 9:
                R.append(s*10+9)
                R.append(s*10+8)
            else:
                R.append(s*10+t)
                R.append(s*10+t+1)
                R.append(s*10+t-1)
        T.append(R)
    ANS = []
    for t in T:
        ANS.extend(t)
    ANS.sort()
    print(ANS[K-1])
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
d = defaultdict(lambda:defaultdict(list))

def cal(s,k):
    if k == 0:
        d[0][s].append(str(s))
    else:
        m = max(0,s-1)
        M = min(9,s+1)
        for i in range(m,M+1):
            for j in d[k-1][i]:
                d[k][s].append(str(s)+j)

for k in range(10):
    for s in range(10):
        cal(s,k)

ans = []
for k in range(10):
    for s in range(10):
        for i in d[k][s]:
            ans.append(int(i))

ans = list(set(ans))
ans.sort()
ans = ans[1:]
k = int(input())
print(ans[k-1])

Solution (Python):

import sys

def solve(K: int):
    s = set(range(1, 10))
    while len(s) <= 10 ** 5:
        ss = set(s)
        for n in s:
            t = n % 10
            ss.add(n * 10 + t)
            if t != 0:
                ss.add(n * 10 + t - 1)
            if t != 9:
                ss.add(n * 10 + t + 1)
        s = ss
    s = sorted(s)
    print(s[K-1])



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):
def lunlun(head,keta,now):
    if keta==1:
        A.append(int(now))
        return 0
    else:
        for i in range(-1,2):
            if 0<=head+i<=9:
                lunlun(head+i,keta-1,now+str(head+i))
A = []
for i in range(1,10):
    for j in range(1,11):
        lunlun(i,j,str(i))


A.sort()
K = int(input())
print(A[K-1])

Solution (Python):

from queue import Queue
k = int(input()) + 1
q = Queue()
q.put(0)
while not q.empty():
    n = q.get()
    k -= 1
    if k == 0:
        print(n)
        exit()
    if n == 0:
        for i in range(9):
            q.put(i + 1)
    else:
        last = int(str(n)[-1])
        if last > 0:
            q.put(n * 10 + last - 1)
        q.put(n * 10 + last)
        if last < 9:
            q.put(n * 10 + last + 1)

Solution (Python):
import sys


from collections import Counter, deque, defaultdict











readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    run = [0] * 100000
    que = deque()

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

    cnt = 0
    while que:
        x = que.popleft()
        cnt += 1
        if cnt == k:
            print(int(x))
            sys.exit()

        xlast = x[-1]
        if xlast == "0":
            for i in ("0", "1"):
                nx = x + i
                que.append(nx)
        elif xlast == "9":
            for i in ("8", "9"):
                nx = x + i
                que.append(nx)
        else:
            for i in range(int(xlast) - 1, int(xlast) + 2):
                nx = x + str(i)
                que.append(nx)


if __name__ == '__main__':
    main()

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


def make_runrun(n, depth):
    r = [n]
    if depth == 0:
        return r
    x = n % 10

    if x >= 1:
        r.extend(make_runrun(n * 10 + x - 1, depth - 1))
    r.extend(make_runrun(n * 10 + x, depth - 1))
    if x < 9:
        r.extend(make_runrun(n * 10 + x + 1, depth - 1))
    
    return r

r = []
for i in range(1, 10):
    r.extend(make_runrun(i, 10))
r = sorted(r)
print(r[k - 1])

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

cnt = 9
LIM = 10**5+5
gen = [ [1, 2, 3, 4, 5, 6, 7, 8, 9] ]
other = [1,2,3,4,5,6,7,8,9]

while cnt < LIM:
	nw = []
	i = gen[-1]
	for j in i:
		dig = j % 10
		if( dig > 0 ):
			num = j * 10 + (dig-1)
			nw.append(num)
			other.append(num)
			cnt += 1
		num = j * 10 + dig
		nw.append(num)
		other.append(num)
		cnt += 1
		if dig < 9:
			num = j * 10 + (dig + 1)
			nw.append(num)
			other.append(num)
			cnt += 1
	gen.append(nw)
other = sorted(other)
print(other[k-1])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
K = int(input())

res = [1, 2, 3, 4, 5, 6, 7, 8, 9]
def dfs(x, k):
  global res
  if k == 0:
    res.append(x)
    return
  for i in range(3):
    y = i - 1 + (x % 10)
    if y in range(10):
      dfs(x * 10 + y, k - 1)
for t in range(1, 11):
  for x in range(1, 10):
    dfs(x, t)
res.sort()
print(res[K - 1])

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    K = iip(False)

    rl = []
    rl_next = list(range(1, 10))
    while True:
        rl_current = [i for i in rl_next]
        rl_next = []
        if len(rl) > 10 ** 5 + 10000:
            break
        for i in rl_current:
            rl.append(i)
            i0 = i * 10
            i1 = i % 10

            if i1 != 0:
                rl_next.append(i0+i1-1)
            rl_next.append(i0+i1)
            if i1 != 9:
                rl_next.append(i0+i1+1)

    
    return rl[K-1]





def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    k=II()
    run=list(range(1,10))
    cur=list(range(1,10))
    while len(run)<k:
        nxt=[]
        for r in cur:
            e=r%10
            nxt.append(r*10+e)
            run.append(r*10+e)
            if e!=0:
                nxt.append(r*10+e-1)
                run.append(r*10+e-1)
            if e!=9:
                nxt.append(r*10+e+1)
                run.append(r*10+e+1)
        cur=nxt
    run.sort()
    print(run[k-1])

main()

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

one=['1','2','3','4','5','6','7','8','9']
for i in range(10**5+1):
    if one[i][-1]=='0':
        one.append(one[i]+'0')
        one.append(one[i]+'1')
    elif 1<=int(one[i][-1])<=8:
        one.append(one[i]+str(int(one[i][-1])-1))
        one.append(one[i]+str(int(one[i][-1])))
        one.append(one[i]+str(int(one[i][-1])+1))
    else:
        one.append(one[i]+'8')
        one.append(one[i]+'9')

print(one[K-1])

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

count = 0
i = 1
while True:
    s = str(i)
    for j in range(len(s) - 1):
        if abs(int(s[j]) - int(s[j+1])) > 1:
            i += 10 ** (len(s)-j-2)
            break
    else:
        count += 1
        if count == k:
            break
        i += 1

print(i)

Solution (Python):
from collections import deque
K = [int(i) for i in input().split()][0]

que = deque()
for i in range(1, 10):
  que.append(i)
k = 0
while k < K:
  k += 1
  p = que.popleft()
  i = p % 10
  if len(que) + k < K:
      if i > 0:
        que.append(p*10 + i -1)
      que.append(p*10 + i)
      if i < 9:
        que.append(p*10 + i + 1)
  
print(p)

Solution (Python):
import copy
K = int(input())
ans, nex = [i for i in range(1, 10)], [i for i in range(1, 10)]
for i in range(10):
    pre, nex = copy.deepcopy(nex), []
    for p in pre:
        if p % 10 != 0:
            ans.append(p * 10 + p % 10 - 1)
            nex.append(p * 10 + p % 10 - 1)
        ans.append(p * 10 + p % 10)
        nex.append(p * 10 + p % 10)
        if p % 10 != 9:
            ans.append(p * 10 + p % 10 + 1)
            nex.append(p * 10 + p % 10 + 1)

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

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

r = [[i,i] for i in range(1, 10)]
l = [0]
cnt = len(r)
if k <= cnt:
    print(k)
    exit()

k -= 1
k -= cnt
for _ in range(100):
    nr = []
    x = 10**(_+1)
    for i in l:
        nr.append([x+i, 1])
    for i, start in r:
        for j in range(start-1,start+2):
            if j == 0:
                l.append(i)
            elif 10 > j > 0:
                nr.append([j*x+i, j])

    if len(nr) > k:
        nr.sort()
        print(nr[k][0])
        exit()
    k -= len(nr)
    r = nr

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

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

count = 0
for _ in range(k):
    i = d.popleft()
    dd = [i * 10 + (i % 10) + j - 1 for j in range(3)]
    dd = dd[1:] if i % 10 == 0 else dd[:2] if i % 10 == 9 else dd
    for j in dd:
        d.append(j)

else:
    print(i)

Solution (Python):
K = int(input())
runrun = [[] for _ in range(11)]
runrun[1] = [i for i in range(1, 10)]
for i in range(1, 10):
    run = runrun[i]
    for r in run:
        t = r%10
        if t != 0:
            runrun[i+1].append(r*10+t-1)
        runrun[i+1].append(r*10+t)
        if t != 9:
            runrun[i+1].append(r*10+t+1)
for i in range(11):
    if len(runrun[i]) <= K:
        K -= len(runrun[i])
        continue
    print(runrun[i][K-1])
    break

Solution (Python):
def solve():
    K = int(input())
    cnt = 0
    n_digit = 1
    numbers = []
    while cnt < K:
        numbers = []
        dfs("", numbers, n_digit)
        cnt += len(numbers)
        n_digit += 1
    
    print(numbers[-(cnt - K + 1)])
    
def dfs(now, numbers, n_digit):
    if len(now) == n_digit:
        numbers.append(now)
        return
    
    if now == "":
        for i in range(1,10):
            dfs(now+str(i), numbers, n_digit)
    else:
        last_num = int(now[-1])
        if last_num - 1 >= 0:
            dfs(now+str(last_num-1), numbers, n_digit)

        dfs(now+str(last_num), numbers, n_digit)

        if last_num + 1 <= 9:
            dfs(now+str(last_num+1), numbers, n_digit)

if __name__ == '__main__':
    solve()

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

N = [0]

for _ in range(K):
    i = 0
    while i < len(N) and N[i] == 9:
        i += 1
    while i+1 < len(N) and N[i] == N[i+1]+1:
        i += 1
    if i == len(N):
        N = [0]*len(N) + [1]
    else:
        N[i] += 1
        i -= 1
        while i >= 0:
            N[i] = max(N[i+1]-1,0)
            i -= 1

print(*reversed(N),sep='')

Solution (Python):

import sys
from queue import Queue

K = int(input())

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

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

idx = 9

while idx<=K and not(q.empty()):
    cur = q.get()
    num = cur%10
    if num==0:
        for i in range(2):
            nxt = cur*10 + (num+i)
            if idx+1==K:
                ans = nxt
                break
            idx += 1
            q.put(nxt)
        else:
            continue
        break

    elif num==9:
        for i in range(2):
            nxt = cur*10 + (num+i-1)
            if idx+1==K:
                ans = nxt
                break
            idx += 1
            q.put(nxt)
        else:
            continue
        break
        
    else:
        for i in range(3):
            nxt = cur*10 + (num+i-1)
            if idx+1==K:
                ans = nxt
                break
            idx += 1
            q.put(nxt)
        else:
            continue
        break

print(ans)

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())
k-=1
z=[]
zz=[]
for i in range(1,10):
    z.append(str(i))
zz+=z
for i in range(9):
    tmp=[]
    for j in z:
        e=int(j[-1])
        for p in range(3):
            if 0<=e+(p-1)<=9:
                tmp.append(j+str(e+p-1))      
    z=tmp
    zz+=z
for i in range(len(zz)):
    zz[i]=int(zz[i])
zz.sort()

print(zz[k])

Solution (Python):
K = int(input())
W = 0
k = 0
while True:
    W += 1
    pool = [(i,0) for i in range(9,0,-1)]
    history = [None] * W
    while pool:
        n, w = pool.pop()
        history[w] = n
        if w == W-1:
            k += 1
            if k == K:
                for j in range(W):
                    print(history[j], end='')
                print()
                exit()
        else:
            if n < 9: pool.append((n+1,w+1))
            pool.append((n,w+1))
            if n > 0: pool.append((n-1,w+1))

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

k = 10**5
pp = [i+1 for i in range(9)]
kkk = [i+1 for i in range(9)]
while True:
    ad = []
    for i in pp:
        po = str(i)[-1]
        if po != "0":
            ad.append(i*10+int(po)-1)
            kkk.append(i*10+int(po)-1)
        if po != "9":
            ad.append(i*10+int(po)+1)
            kkk.append(i*10+int(po)+1)
        kkk.append(i*10+int(po))
        ad.append(i*10+int(po))
        pp = ad
        
    if len(kkk) >= 10**5:
        break
kkk.sort()
n = onem()
print(kkk[n-1])

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'

    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0



k=I()
c=0

m=list(range(1,10))
ans=[]
n=10
for i in range(n):
    nx=[]
    for j in m:
        d=j%10
        tmp=[j*10+d+x for x in range(-1,2)]
        if d==0:
            tmp=tmp[1:]
        elif d==9:
            tmp=tmp[:2]
        nx+=tmp
    ans+=m
    m=nx[:]
    
print(ans[k-1])

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

if K < 10:
    print(K)
    exit()
K -= 9

prev = list(range(1, 10))
while True:
    lunlun = []
    for p in prev:
        if p % 10 == 0:
            lunlun.append(p * 10 + 0)
            lunlun.append(p * 10 + 1)
        elif p % 10 == 9:
            lunlun.append(p * 10 + 8)
            lunlun.append(p * 10 + 9)
        else:
            for i in range(p % 10 - 1, p % 10 + 2):
                lunlun.append(p * 10 + i)
    if K <= len(lunlun):
        print(lunlun[K-1])
        break
    K -= len(lunlun)
    prev = lunlun

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

K = int(input())


dp = [[] for i in range(10)]
answer = []
for j in range(1, 10):
    dp[0].append(j)
    answer.append(j)

cnt = 10
for i in range(1, 100):
    for d in dp[i - 1]:
        dd = d % 10
        for j in range(10):
            if j == dd - 1 or j == dd or j == dd + 1:
                dp[i].append(d * 10 + j)
                answer.append(d * 10 + j)
    if len(answer) > 10 ** 5:
        break
answer.sort()
print(answer[K - 1])

Solution (Python):
from collections import deque
INF=3234566667
X=[]
q=deque([i for i in range(1,10)])
D=[[0,1],[0,1,2],[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9]]
while(len(q)>0):
    r=q.popleft()
    X.append(r)
    for m in D[r%10]:
        p=r*10+m
        if p<=INF:
            q.append(p)
X.sort()
K=int(input())
print(X[K-1])

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

maxK = 10**5


K = int(input())

As = []
def dfs(i, maxD, x):
    if i == maxD:
        As.append(x)
        if len(As) >= maxK:

            print(As[K-1])
            sys.exit()
    else:
        y = x%10
        x *= 10
        if y-1 >= 0:
            dfs(i+1, maxD, x+y-1)
        dfs(i+1, maxD, x+y)
        if y+1 <= 9:
            dfs(i+1, maxD, x+y+1)

for d in range(1, 11):
    for x in range(1, 10):
        dfs(1, d, x)

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

K = int(input())

d = {
    "0": [0, 1],
    "1": [0, 1, 2],
    "2": [1, 2, 3],
    "3": [2, 3, 4],
    "4": [3, 4, 5],
    "5": [4, 5, 6],
    "6": [5, 6, 7],
    "7": [6, 7, 8],
    "8": [7, 8, 9],
    "9": [8, 9],
}

cand = set(i for i in range(1, 10))
while True:
    if len(cand) >= K:
        ans = sorted(list(cand))[K - 1]
        break
    K -= len(cand)
    new = set()
    for s in cand:
        val = d[str(s)[-1]]
        for v in val:
            new.add(s * 10 + v)
    cand = new


print(ans)

Solution (Python):
k = int(input())
pre = [1,2,3,4,5,6,7,8,9]
if k <= 9:
    print(pre[k-1])
    exit()

count = 9
while True:
    cur = []
    for e in pre:
        last = e%10
        for i in [-1, 0, 1]:
            nxt = last+i
            if 0<=nxt<=9:
                count += 1
                value = 10*e + nxt
                if count == k:
                    print(value)
                    exit()
                cur.append(value)

    pre = cur

Solution (Python):
from collections import deque

K = int(input())
q = deque(tuple(range(1, 10)))
cnt = 0
while cnt < K:
    v = q.popleft()
    cnt += 1
    for i in [-1, 0, 1]:
        c = int(str(v)[-1]) + i
        if 0 <= c <= 9:
            q.append(v * 10 + c)

print(v)

Solution (Python):
from collections import deque

k = int(input())

dq = deque(range(1, 10))
cnt = 9
li = []
while cnt < 10 ** 5 + 10:
    num = dq.popleft()
    li.append(num)
    lst = num % 10
    if lst == 0:
        dq.append(num * 10)
        dq.append(num * 10 + 1)

    elif lst == 9:
        dq.append(num * 10 + 8)
        dq.append(num * 10 + 9)

    else:
        for i in range(lst - 1, lst + 2):
            dq.append(num * 10 + i)

    cnt += 1

ans = li[k-1]
print(ans)