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):
import copy
K = int(input())

runrun = list(map(str, range(1, 10)))
start = 0
while(True):

    runrun_tmp = copy.deepcopy(runrun[start:])
    start = len(runrun)
    for r in runrun_tmp:
        last_int = int(r[-1])
        tmp = []
        if last_int != 0:
            tmp.append(r+str(last_int-1))
        tmp.append(r+str(last_int))
        if last_int != 9:
            tmp.append(r+str(last_int+1))
        runrun += tmp
    if len(runrun) > K:
        break

print(runrun[K-1])

Solution (Python):
if __name__ == '__main__':
	K = int(input())

	L = [['0'],['1'],['2'],['3'],['4'],['5'],['6'],['7'],['8'],['9']]

	ans = 0
	count = 9
	check = 0

	if K < 10:
		ans = L[K][0]
		check = 1

	while check == 0:
		newL = [['']] * 10
		for i in range(10):
			newls = []
			if i == 0:
				for s in L[0]:
					newls.append(str(i)+s)
				for s in L[1]:
					newls.append(str(i)+s)
			elif i == 9:
				for s in L[8]:
					newls.append(str(i)+s)
					count += 1
					if count == K:
						ans = newls[-1]
						check = 1
				for s in L[9]:
					newls.append(str(i)+s)
					count += 1
					if count == K:
						ans = newls[-1]
						check = 1
			else:
				for j in range(-1,2):
					for s in L[i+j]:
						newls.append(str(i)+s)
						count += 1
						if count == K:
							ans = newls[-1]
							check = 1

			newL[i] = newls[:]

		L = newL[:]


	print(int(ans))

Solution (Python):
def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)

if __name__ == "__main__":
    K = int(input())
    S = [1,2,3,4,5,6,7,8,9]
    for i in range(1,10):
        for k in range(3**i):
            a = base10to(k,3)
            a = "0"*(i-len(a))+a
            for j in range(1,10):
                s = str(j)
                state = 1
                j0 = j
                for l in a:
                    if int(l) == 0:
                        j0 -= 1
                        if j0<0:
                            state = 0
                            break
                        s = s + str(j0)
                    elif int(l) ==1 :
                        s = s+str(j0)
                    else:
                        j0 += 1
                        if j0 ==10:
                            state = 0
                            break
                        s = s + str(j0)
                if state:
                    S.append(int(s))
        S.sort()
    print(S[K-1])

Solution (Python):
import sys

K = int(input())


def hoge(Num, X, K):
    if Num == K:
        print(X)
        sys.exit()


if K < 10:
    print(K)
else:
    num1 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    num2 = []
    num = 9
    while (True):

        for i in range(len(num1)):  
            if num1[i] % 10 != 0:
                num2.append(num1[i] * 10 + ((num1[i] % 10) - 1))
                num += 1
                hoge(num, num1[i] * 10 + ((num1[i] % 10) - 1), K)

            num2.append(num1[i] * 10 + (num1[i] % 10))
            num += 1
            hoge(num, num1[i] * 10 + (num1[i] % 10), K)

            if num1[i] % 10 != 9:
                num2.append(num1[i] * 10 + ((num1[i] % 10) + 1))
                num += 1
                hoge(num, num1[i] * 10 + ((num1[i] % 10) + 1), K)

        num1 = num2[:]
        num2 = []

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

def ans(num):
    if num > 3234566667:
        return
    nums.append(num)
    if int(str(num)[-1]) + 1 <= 9:
        tmp = int(str(num) + str(int(str(num)[-1]) + 1))
        ans(tmp)
    if int(str(num)[-1]) - 1 >= 0:
        hoge = int(str(num) + str(int(str(num)[-1]) - 1))
        ans(hoge)
    hage = int(str(num) + str(int(str(num)[-1])))
    ans(hage)

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

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

Solution (Python):


def abc161d(k):
    lunArr = [[] for _ in range(10)]
    lunArr[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9,]

    for keta in range(1,10):
        for elem in lunArr[keta-1]:
            base = elem % 10
            if base == 0:
                lunArr[keta].append(elem * 10 + base)
                lunArr[keta].append(elem * 10 + base+1)
            elif base == 9:
                lunArr[keta].append(elem * 10 + base-1)
                lunArr[keta].append(elem * 10 + base)
            else:
                lunArr[keta].append(elem * 10 + base-1)
                lunArr[keta].append(elem * 10 + base)
                lunArr[keta].append(elem * 10 + base+1)

    target = k
    for keta in range(10):
        t_arr = lunArr[keta]
        if target < len(t_arr):
            return t_arr[target-1]
        else:
            target -= len(t_arr)
    else:
        print("k is too large")
        print(target)




if(__name__ == '__main__'):
    
    k = int(input())
    
    ans = abc161d(k)
    
    
    print(ans)

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

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

for i in lun_list:
    if str(i)[-1] == '0':
        for j in range(2):
            lun_list.append(int(str(i)+str(j)))
    elif str(i)[-1] == '9':
        for j in range(8,10):
            lun_list.append(int(str(i)+str(j)))
    else:
        for j in range(int(str(i)[-1])-1,int(str(i)[-1])+2):
            lun_list.append(int(str(i)+str(j)))
    if len(lun_list) > k:
        break

print(lun_list[k-1])

Solution (Python):

from collections import deque

k = int(input())
ln_list = []
dq = deque([])

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

while len(dq) > 0 and len(ln_list) < k:
    obj = dq.popleft()

    ln_list.append(obj)
    last_i = int(str(obj)[-1])

    for i in range(-1, 2):
        next_int = last_i + i
        if -1 < next_int < 10:
            tmp = int(str(obj) + str(next_int))

            dq.append(tmp)

print(ln_list[k-1])

Solution (Python):
k = int(input())
L = []
ans = 0
for i in range(1, 11):
    L.append([])
if k <= 9:
    print(k)
else:
    for i in range(1,10):
        L[0].append(str(i))
        ans = 9
    for i in range(1,10):
        for j in range(len(L[i-1])):
            if L[i-1][j][i-1] == '9':
                L[i].append(L[i-1][j]+'8')
                L[i].append(L[i-1][j]+'9')
            elif L[i-1][j][i-1] == '0':
                L[i].append(L[i-1][j]+'0')
                L[i].append(L[i-1][j]+'1')
            else:
                L[i].append(L[i-1][j]+str(int(L[i-1][j][i-1])-1))
                L[i].append(L[i-1][j]+str(int(L[i-1][j][i-1])))
                L[i].append(L[i-1][j]+str(int(L[i-1][j][i-1])+1))
    templist = []
    for i in range(10):
        templist = templist + L[i]
    print(templist[k-1])

Solution (Python):


def next(ll):
    n = len(ll)
    chk = False

    for i in range(n - 1, -1, -1):

        i_num = int(ll[i])

        if i_num == 9:
            continue

        if i > 0:
            
            if i_num <= int(ll[i - 1]):
                if i == n - 1:
                    return str(int(ll) + 1)
                else:
                    if i_num <= int(ll[i + 1]):
                        chk = True
                        break
                        
        else:
            if i < n - 1:
                if i_num <= int(ll[i + 1]):
                    chk = True
                        
            else:
                chk = True

    if not chk:
        st = '1' + '0' * n
        return st

    i_num = int(ll[i])
    st = ll[:i]

    

    for j in range(n - i):
        st += str(max(i_num + 1 - j, 0))

    return st



k = int(input())

num = '1'
c = 1

while c < k:
    c += 1
    num = next(num)

print (num)

Solution (Python):
from heapq import heapify, heappop, heappush, heappushpop

def next_int(n):
    nums = {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]}
    return nums[n]


K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]
heapify(queue)
for _ in range(K-1):
    now = heappop(queue)  
    for next_i in next_int(int(str(now)[-1])):
        heappush(queue, int(str(now)+str(next_i)))

print(heappop(queue))

Solution (Python):
from collections import deque

k = int(input())
ans = deque([str(i) for i in range(1, 10)])
que = deque(ans)
while que:
    num = que.popleft()
    if num[-1] == '0':
        que.append(num + '0')
        que.append(num + '1')
        ans.append(num + '0')
        ans.append(num + '1')
    elif num[-1] in [str(i) for i in range(1, 9)]:
        n_last = int(num[-1])
        que.append(num + str(n_last-1))
        que.append(num + str(n_last))
        que.append(num + str(n_last + 1))
        ans.append(num + str(n_last - 1))
        ans.append(num + str(n_last))
        ans.append(num + str(n_last + 1))
    else:
        que.append(num + '8')
        que.append(num + '9')
        ans.append(num + '8')
        ans.append(num + '9')
    if len(ans) >= k:
        print(ans[k-1])
        exit()

Solution (Python):


import sys
import math
import collections
import itertools
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def PL(L) : print(*L, sep="\n")

K = I()

stack = [[1],[2],[3],[4],[5],[6],[7],[8],[9]]
ok = [[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]]

i = 0
while len(stack) < K:
    p = stack[i]
    tm = ok[p[-1]]
    
    for t in tm:
        stack.append(p+[t])
    
    i += 1



for i in stack[K-1]:
    print(i, end="")
print()

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

k = int(input())

a = []

for i in range(10):
    a.append(str(i))

for i in range(9):
    b = []
    for e in a:
        if e[0] == "0":
            b.append("0"+e)
            b.append("1"+e)
        elif e[0] == "9":
            b.append("8"+e)
            b.append("9"+e)
        else:
            b.append(str(int(e[0])-1)+e)
            b.append(e[0]+e)
            b.append(str(int(e[0])+1)+e)
    for e in b:
        a.append(e)

res = []
for e in a:
    if e[0] != "0":
        res.append(int(e))
res = list(set(res))
res.sort()

print(res[k-1])

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


def construct(lunnum: str, depth: int, flag: bool):
    global l
    if depth == 0:
        l.add(int(lunnum))
        return
    m = int(lunnum[-1])
    if (flag):
        for i in range(0, 10):
            construct(lunnum+str(i), depth-1, i == 0)
    elif (m == 0):
        for i in sorted([m, (m + 1) % 10]):
            construct(lunnum + str(i), depth - 1, False)
    elif (m == 9):
        for i in sorted([(m - 1) % 10, m]):
            construct(lunnum + str(i), depth - 1, False)
    else:
        for i in sorted([(m - 1) % 10, m, (m + 1) % 10]):
            construct(lunnum + str(i), depth - 1, False)


construct("0", 10, True)
ls = list(l)
ls.sort()
print(ls[k])

Solution (Python):



import sys
sys.setrecursionlimit(10000000)


dxdy=((1,0),(0,1))

def pin(type=int):
    return map(type,input().rstrip().split())

def resolve():
    k,=pin()
    if k<10:
        print(k)
        return
    else:
        from collections import deque as D
        que=D((i,i) for i in range(1,10))
        num=10
        while(1):
            x,y=que.popleft()
            temp=x%10
            subq=[j for j in range(temp-1,temp+2) if j>=0 and j<10]
            
            for q in subq:
                que.append((x*10+q,num))
                if num == k:
                    print(x*10+q)
                    return
                num+=1
    
"""         


"""
"""
お前カッコ閉じ,るの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """15"""
        output = """23"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """1"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """13"""
        output = """21"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """100000"""
        output = """3234566667"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()

Solution (Python):
import queue

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

k = int(input())
cou = 0
while True:
    cou += 1
    t = q.get()
    if cou == k:
        print(t)
        exit()
    if t % 10 == 0:
        q.put(t*10)
        q.put(t*10 + 1)
    elif t % 10 == 9:
        q.put(t*10 + 8)
        q.put(t*10 + 9)
    else:
        s = t % 10
        q.put(t*10 + s -1)
        q.put(t*10 + s)
        q.put(t*10 + s + 1)

Solution (Python):
k = int(input())
if k <= 10:
    print(k)
    exit()


def f(c, l):
    ret = ''
    for i in range(l):
        a = max(0, int(c) - i)
        ret += str(a)
    return ret


k -= 11
s = '11'
while k > 0:
    if s[-2] >= s[-1] and s[-1] < '9':
        s = s[:-1] + str(int(s[-1]) + 1)
        k -= 1
        continue
    c = False
    for j in range(len(s) - 2, 0, -1):
        if s[j] <= s[j+1] and s[j] <= s[j-1] and s[j] < '9':
            s = s[:j] + str(int(s[j])+1) + f(s[j],len(s)-j-1)
            k -= 1
            c = True
            break
    if c:
        continue

    if s[0] < s[1]:
        s = str(int(s[0]) + 1) + f(s[0], len(s) - 1)
        k -= 1
        continue

    s = '1' + '0' * len(s)
    k -= 1

print(s)

Solution (Python):
import sys

K=int(input())

if K<=9:
    print(K)
    sys.exit(0)

LS=[0]*11
LS[1]=[1,1,1,1,1,1,1,1,1,1]
LS2=[]
for i in range(2,11):
    LS[i]=[0]*10
    for j in range(0,10):
        for k in range(max(j-1,0),min(j+2,10)):
            LS[i][j]+=LS[i-1][k]
for i in range(1,11):
    for j in range(1,10):
        LS2+=[LS[i][j]]


ans=""
total=0
keta=0
first=0
bktotal=0
for i in range(90):
    bktotal=total
    total+=LS2[i]
    if K<=total:
        ans+=str((i%9)+1)
        keta=(i//9)+1
        first=(i%9)+1
        K-=bktotal
        break



while keta>1:
    backtotal=0
    total=0
    for i in range(max(0,first-1),min(10,first+2)):
        backtotal=total
        total+=LS[keta-1][i]
        if total>=K:
            ans+=str(i)
            first=i
            K-=backtotal
            break
    keta-=1
print(ans)

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

if k <= 9:
    print(k)
    exit()
    
l = list(map(str, list(range(1,10))))
x = 0
for i in range(k):
    for j in (-1, 0, 1):
        if int(l[x][-1]) + j in (-1, 10):
            continue
        l.append(l[x] + str(int(l[x][-1]) + j))
    x += 1

print(l[k-1])

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

lunlun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for li in lunlun:
     if 10**10 < li:
         break
     lunlun.append(li * 10 + li % 10)
     if 0 <= li % 10 < 9:
         lunlun.append(li * 10 + li % 10 + 1)
     if 0 < li % 10 <= 9:
         lunlun.append(li * 10 + li % 10 - 1)
lunlun.sort()
print(lunlun[k - 1])

Solution (Python):
k = int(input())
st = [[0 for _ in range(10)] for _ in range(11)]
for j in range(1, 10):
	st[1][j] = 1
for i in range(2, 11):
	st[i][1] = sum(st[j][1] for j in range(1, i)) + 1 + st[i-1][2]
	for j in range(2, 9):
		st[i][j] = st[i-1][j-1] + st[i-1][j] + st[i-1][j+1]
	st[i][9] = st[i-1][8] + st[i-1][9]

zero = [0 for _ in range(11)]
zero[1] = 1
for i in range(2, 11):
	zero[i] = sum(st[j][1] for j in range(1, i)) + 1


cum = [0 for _ in range(11)]
cum[1] = 9
for i in range(2, 11):
	cum[i] = cum[i-1] + sum(st[i])


cnt = 0
ans = ""

flg = False
for i in range(1, 11):
	for j in range(1, 10):
		if cnt < k <= cnt+st[i][j]:
			x, y = i, j
			ans += str(y)
			k -= cnt
			flg = True
			break
		else:
			cnt += st[i][j]
	if flg:
		break
x -= 1


while x > 0:
	if 2 <= y:
		cnt = 0
		for j in range(y-1, min(y+2, 10)):
			if cnt < k <= cnt + st[x][j]:
				y = j
				x -= 1
				ans += str(y)
				k -= cnt
				break
			else:
				cnt += st[x][j]
	else:
		if k <= zero[x]:
			y = 0
			x -= 1
			ans += str(y)
		else:
			cnt = zero[x]
			for j in range(1, y+2):
				if cnt < k <= cnt + st[x][j]:
					y = j
					x -= 1
					ans += str(y)
					k -= cnt
					break
				else:
					cnt += st[x][j]

print(ans)

Solution (Python):
def f(t,i,j,ans):
  
  ft=0
  
  if j>0:
    ft+=a[i-1][j-1]
    
    if ft>=t:
      ans+=str(j-1)
      if i-1==0:
        return ans
      return f(t-(ft-a[i-1][j-1]),i-1,j-1,ans)
    
  ft+=a[i-1][j]
  
  if ft>=t:
    ans+=str(j)
    if i-1==0:
      return ans
    return f(t-(ft-a[i-1][j]),i-1,j,ans)
  
  if j<9:
    ft+=a[i-1][j+1]
    
    if ft>=t:
      ans+=str(j+1)
      if i-1==0:
        return ans
      return f(t-(ft-a[i-1][j+1]),i-1,j+1,ans)
  
      


k=int(input())

a=[[1,1,1,1,1,1,1,1,1,1]]
t=9
i=0
while 1:
  i+=1
  a+=[[0,0,0,0,0,0,0,0,0,0]]
  for j in range(10):
    if j==0:
      a[i][0]=a[i-1][0]+a[i-1][1]
    elif j==9:
      a[i][9]=a[i-1][8]+a[i-1][9]
      t+=a[i][9]
    else:
      a[i][j]=a[i-1][j-1]+a[i-1][j]+a[i-1][j+1]
      t+=a[i][j]
    if t>=k:
      ai=i
      aj=j
      break
  if t>=k:
    break
if k>9:
  ans=""
  ans+=str(j)
    
  ans=f(k-(t-a[ai][aj]),ai,aj,ans)
  print(ans)
else:
  print(k)

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

dp = [[[] for j in range(11)] for i in range(11)]


for i in range(10):
    dp[1][i].append(i)
    dp[0][i].append(0)


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

k-=9

for i in range(2, 11):
    for j in range(1, 10):
        if j==1:
            for z in range(i):
                for x in dp[z][j]:
                    dp[i][j].append(j*10**(i-1)+x)
                    k-=1
                    if k==0:
                        print(dp[i][j][-1])
                        exit()
            for x in dp[i - 1][j + 1]:
                dp[i][j].append(j * 10 ** (i-1) + x)
                k-=1
                if k==0:
                    print(dp[i][j][-1])
                    exit()
        else:
            for x in dp[i-1][j-1]:
                dp[i][j].append(j*10**(i-1)+x)
                k-=1
                if k==0:
                    print(dp[i][j][-1])
                    exit()
            for x in dp[i - 1][j]:
                dp[i][j].append(j * 10 ** (i-1) + x)
                k-=1
                if k==0:
                    print(dp[i][j][-1])
                    exit()
            for x in dp[i - 1][j + 1]:
                dp[i][j].append(j * 10 ** (i-1) + x)
                k-=1
                if k==0:
                    print(dp[i][j][-1])
                    exit()

Solution (Python):
def main():
    k = int(input())
    l = []
    for i in range(1,10):
        l.extend(dfs(i))
    l.sort()
    print(l[k-1])
    
def dfs(n,limit = 10**9):
    l = [n]
    if n>limit:
        return l
    i = n%10
    n *=10

    if i==0:
        l.extend(dfs(n+i))
        l.extend(dfs(n+i+1))
        return l
    elif i==9:
        l.extend(dfs(n+i-1))
        l.extend(dfs(n+i))
        return l
    
    else:
        l.extend(dfs(n+i-1))
        l.extend(dfs(n+i))
        l.extend(dfs(n+i+1))
        return l

if __name__ == "__main__":
    main()

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

k = ii()
l = deque()
run = [1,2,3,4,5,6,7,8,9]
ans = [1,2,3,4,5,6,7,8,9]

for i in range(2,100):
    ll=deque(run)
    keta = 10**(i-1)
    while len(ll)>0:
        v = ll.popleft()
        if(v>=keta):
            ans.append(v)
        else:
            p = v%10
            if p == 0:
                ll.append(v*10+0)
                ll.append(v*10+1)
            elif p==9:
                ll.append(v*10+8)
                ll.append(v*10+9)
            else:
                ll.append(v*10+p-1)
                ll.append(v*10+p)
                ll.append(v*10+p+1)
    if len(ans)>10**5:
        break
ans.sort()

print(ans[k-1])

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

total_n = 9
n = K
A = list(range(1,10))

for i in range(1000):
    if total_n >= K:
        break

    else:
        n -= len(A)
        temp = []
        for num in A:
            amari = int(str(num)[-1])
            moto = num * 10
            if amari !=0 and amari % 10 != 9:
                temp.extend([moto + amari - 1, moto+amari, moto + amari + 1]) 
                total_n += 3
            elif amari == 0:
                temp.extend([moto+amari, moto + amari + 1])
                total_n += 2
            else:
                temp.extend([moto + amari - 1, moto+amari])
                total_n += 2
        A = temp

print(A[n-1])

Solution (Python):
K = int(input())
if K < 9:
  print(K)
else:
  K -= 9
  i = 0
  L = [1,2,3,4,5,6,7,8,9]
  M = []
  while K > 0:
    x = L[i]
    if  0 < x%10 < 9:
      if K > 3:
        L.append(x*10+ x%10 - 1)
        L.append(x*10 + x%10)
        L.append(x*10 + x%10 + 1)
        K -= 3
      elif K == 3:
        ans = x*10 + x%10 + 1
        K = 0
      elif K == 2:
        ans = x*10 + x%10
        K = 0
      elif K == 1:
        ans = x*10 + x%10 - 1
        K = 0
    elif x%10 == 0:
      if K > 2:
        L.append(x*10 + x%10)
        L.append(x*10 + x%10 + 1)
        K -= 2
      elif K == 2:
        ans = x*10 + x%10 + 1
        K = 0
      elif K == 1:
        ans = x*10 + x%10
        K = 0
    else:
      if K > 2:
        L.append(x*10+ x%10 - 1)
        L.append(x*10 + x%10)
        K -= 2
      elif K == 2:
        ans = x*10 + x%10
        K = 0
      elif K == 1:
        ans = x*10 + x%10 - 1
        K = 0
    i += 1
  print(ans)

Solution (Python):
import sys

input = sys.stdin.readline

K = int(input())

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

for i in range(100001):
    one = arr[i]%10
    if one == 0:
        arr.append(arr[i]*10 + 0)
        arr.append(arr[i]*10 + 1)
    elif one == 9:
        arr.append(arr[i]*10 + 8)
        arr.append(arr[i]*10 + 9)
    else:
        arr.append(arr[i]*10 + one - 1)
        arr.append(arr[i]*10 + one)
        arr.append(arr[i]*10 + one + 1)

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

Solution (Python):
def saiki(s):
  if len(s) > 10:
    return
  
  if s[-1] == '0':
    tmp1 = s+'1'
    tmp2 = s+'0'
    ans.append(int(tmp1))
    ans.append(int(tmp2))
    saiki(tmp1)
    saiki(tmp2)
    
  elif s[-1] == '9':
    tmp1 = s+'8'
    tmp2 = s+'9'
    ans.append(int(tmp1))
    ans.append(int(tmp2))
    saiki(tmp1)
    saiki(tmp2)
    
  else:
    last = int(s[-1])
    tmp1 = s + str(last+1)
    tmp2 = s + str(last-1)
    tmp3 = s + str(last)
    ans.append(int(tmp1))
    ans.append(int(tmp2))
    ans.append(int(tmp3))
    saiki(tmp1)
    saiki(tmp2)
    saiki(tmp3)

k = int(input())

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

for i in range(1,10):
  saiki(str(i))
  
ans = sorted(ans)

print(ans[k-1])

Solution (Python):

from collections import deque
a=[1,2,3,4,5,6,7,8,9]
q=deque(a)
while(1):
    x=q.popleft()
    s=str(x)
    n=len(s)
    n1=int(s[n-1])
    c1=str(int(s[n-1])-1)
    c2=str(int(s[n-1])+1)
    a.append(int(s+s[n-1]))
    q.append(int(s+s[n-1]))
    if(n1>0):
        a.append(int(s+c1))
        q.append(int(s+c1))
    if(n1<9):
        a.append(int(s+c2))
        q.append(int(s+c2))
    if(len(a)>200005):
        break
a.sort()
k=int(input())
print(a[k-1])

Solution (Python):
import sys

input = sys.stdin.readline

K = int(input())

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

for i in range(100001):
    one = arr[i]%10
    if one == 0:
        arr.append(arr[i]*10 + 0)
        arr.append(arr[i]*10 + 1)
    elif one == 9:
        arr.append(arr[i]*10 + 8)
        arr.append(arr[i]*10 + 9)
    else:
        arr.append(arr[i]*10 + one - 1)
        arr.append(arr[i]*10 + one)
        arr.append(arr[i]*10 + one + 1)

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

Solution (Python):
k = int(input()) - 1
def onesearch(last):
    if last < 0:
        return [9, 1]
    elif last == 0:
        return [2, 0]
    elif last == 9:
        return [2, 8]
    else:
        return [3, last - 1]
memo = {}
def search(i, last, rest):
    
    if i == 0:
        n, base = onesearch(last)
        if rest < n:
            return (n, base + rest)
        else:
            return (n, -1)
    if (i, last) in memo:
        n, ret = memo[(i, last)]
        if ret >= 0:
            return (n, ret)
    n = 0
    if last < 0:
        for j in range(1, 10):
            n1, ret = search(i - 1, j, rest)
            if ret >= 0:
                return (n1, j * 10 ** i + ret)
            n += n1
            rest -= n1
        memo[(i, last)] = (n, -1)
        return (n, -1)
    for j in range(max(0, last - 1), min(10, last + 2)):
        n1, ret = search(i - 1, j, rest)
        if ret >= 0:
            return (n1, j * 10 ** i + ret)
        n += n1
        rest -= n1
    memo[(i, last)] = (n, -1)
    return (n, -1)
def sub(k):
    for i in range(20):
        n, ret = search(i, -1, k)
        if ret >= 0:
            return ret
        k -= n

print(sub(k))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K = INT()

def calc_next(n):  
	l = len(n)
	n = n[::-1]
	i = 0
	for i in range(l-1):
		if n[i] != 9 and abs(n[i+1]-(n[i]+1))<=1:  
			n[i] += 1
			break
	else:  
		if n[-1] == 9:  
			n = list(map(int, list("1"+"0"*l)))
			return n
		else:  
			i = l-1
			n[-1] += 1
	for j in range(i-1, -1, -1):  
		n[j] = max(0, n[j+1]-1)
	return n[::-1]

N = [1]
cnt = 1
while cnt != K:
	N = calc_next(N)
	cnt += 1
print("".join(list(map(str, N))))

Solution (Python):
from heapq import heappop, heappush

k = int(input())
ten = [[0,1]] + [[i-1, i, i+1] for i in range(1,9)] + [[8,9]]

cnt = 0
heap = []
for i in range(1, 10):
    heappush(heap, [i, i])

memo = set()
while heap or cnt < 20:
    num,pre = heappop(heap)
    if num in memo or num < 1:
        continue
    else:
        memo.add(num)
    cnt += 1
    
    if cnt >= k:
        print(num)
        break
    for i in ten[pre]:
        heappush(heap, [num*10+i, i])

Solution (Python):
from sys import stdin
K = int(stdin.readline().rstrip())
ans = list(range(1,11))
def f(n):
    if int(n) > 3234566667:
        return
    
    
    elif n[0] == "0":
        return

    for i in range(10):
        if abs(int(n[-1])-i) <= 1:
            if int(n+str(i)) > 3234566667:
                return
            ans.append(int(n+str(i)))
            
            f(n+str(i))
    
for i in range(1,10):
    f(str(i))
    
print(sorted(set(ans))[K-1])

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from itertools import product
from collections import defaultdict
from collections import deque
def resolve():
    K = ir()
    s = deque([[i+1, 1, i+1] for i in range(9)])
    cnt = 0
    while cnt < K:
        v, keta, tmp = s.popleft()
        cnt += 1
        min_d = max(0, v-1)
        max_d = min(9, v+1)
        for i in range(min_d, max_d+1):
            s.append([i, keta+1, int(str(tmp)+str(i))])
    print(tmp)
resolve()

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))



K = ir()
dp = [[0] * 10 for _ in range(11)]
dp[0] = [1] * 10 
for i in range(1, 11):
    dp[i] = dp[i-1].copy()
    for j in range(10):
        if j > 0:
            dp[i][j] += dp[i-1][j-1]
        if j < 9:
            dp[i][j] += dp[i-1][j+1]

count = 0
for i in range(11):
    bl = False
    for j in range(1, 10):
        prev = count
        count += dp[i][j]
        if count >= K:
            start = (j, i, K-prev)
            bl = True
            break
    if bl:
        break

def dfs(i, last, num):
    global count, answer
    if i == 1:
        count -= 1
        if count == 0:
            print(num); exit()
    else:
        num *= 10
        if last == 0:
            dfs(i-1, 0, num + 0)
            dfs(i-1, 1, num + 1)
        elif last < 9:
            dfs(i-1, last-1, num + last - 1)
            dfs(i-1, last, num + last)
            dfs(i-1, last+1, num + last + 1)
        else:
            dfs(i-1, 8, num + 8)
            dfs(i-1, 9, num + 9)

answer = 0
head, digit, c = start
count = c
dfs(digit+1, head, head)

Solution (Python):
k = int(input())
if k < 10:
    print(k)
else:
    cnt = 9
    prev_lun = [[i] for i in range(10)]
    new_lun = [[] for _ in range(10)]
    size = 1  
    continflag = True
    while True:
        new_lun[0] = prev_lun[0] + prev_lun[1]
        for i in range(1, 9):
            new_lun[i] = [i*10**size+x for x in (prev_lun[i - 1] + prev_lun[i] + prev_lun[i + 1])]
            cnt += len(new_lun[i])
            if cnt >= k:
                print(new_lun[i][k-cnt-1])
                continflag = False
                break
        if not continflag:
            break
        new_lun[9] = [9*10**size+x for x in (prev_lun[8] + prev_lun[9])]
        cnt += len(new_lun[9])
        if cnt >= k:
            print(new_lun[9][k-cnt-1])
            break
        size += 1
        prev_lun = new_lun
        new_lun = [[] for _ in range(10)]

Solution (Python):
k=int(input())
num=[]
for i in range(k):
    if (len(num)==0):
        num=[1]
    elif (len(num)==1):
        num[0]+=1
        if num[0]==10:
            num=[1, 0]
    else:
        saved=False
        ind=0
        j=len(num)-1
        while(not saved and j>0):
            if (num[j]-num[j-1])<=0:
                if not saved and num[j]!=9:
                    ind=j
                    saved=True
                
            j-=1
        if num[ind]!=9:
            num[ind]+=1
            for j in range(ind+1, len(num)):
                num[j]=max(num[j-1]-1, 0)
        else:
            l=len(num)
            num=[1]+[0]*l

            
for i in num:
    print(i, end='')
print()