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

Solution (Python):
K = int(input())
top = 1
cand = [i for i in range(1,10)]

def dfs(s, c):
    global cand
    if c==0:
        cand.append(int(s))
        return
    if s[-1]=='0':
        dfs(s+str(0), c-1)
        dfs(s+str(1), c-1)
    elif s[-1]=='9':
        dfs(s+str(8), c-1)
        dfs(s+str(9), c-1)
    else:
        dfs(s+str(int(s[-1])-1), c-1)
        dfs(s+str(int(s[-1])), c-1)
        dfs(s+str(int(s[-1])+1), c-1)
        
flag = False
while True:
    for i in range(1,10):
        if len(cand)>1e5:
            flag = True
            break
        dfs(str(i) ,top)
    if flag:
        break
    top+=1
print(cand[K-1])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
ans = []

def dfs(i):
    if 10 < len(i):
        return

    ans.append(int(i))
    if 0 < int(i[-1]):
        dfs(i + chr(ord(i[-1]) - 1))
    if int(i[-1]) < 9:
        dfs(i + chr(ord(i[-1]) + 1))
    dfs(i + i[-1])


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


print(ans[K-1])

Solution (Python):
import collections 
  
q = collections.deque([]) 
f=0
l = []
for i in range(1,10):
    q.append(str(i))
    

while f<100003:
    s = q[0]
    l.append(s)
    if int(s[-1])>0:
        q.append(s+str((int(s[-1])-1+10)%10))
    q.append(s+s[-1])
    if int(s[-1])<9:
        q.append(s+str((int(s[-1])+1)%10))
    q.popleft()
    f+=2

for i in q:
    l.append(i)


n = int(input())
print(l[n-1])

Solution (Python):


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

runrun_list = [n for n in range(10)]
idx = 1
cnt = 9

while True:
    prefix_str = str(runrun_list[idx])
    prefix = int(prefix_str) * 10
    add_idx = int(prefix_str[-1])

    if add_idx == 0:
        start = 0
        stop = 2
    elif add_idx == 9:
        start = 8
        stop = 10
    else:
        start = add_idx - 1
        stop = (add_idx - 1) + 3

    for n in range(start, stop):
        runrun_list.append(prefix + n)
        cnt += 1
        if cnt == K:
            print(runrun_list[-1])
            exit(0)
    idx += 1

Solution (Python):
k = int(input())
dp = [0] * 100000
count = 0
result = []

def u(n, r, now):
    global count
    if r < 0 or r > 9:
        return 0
    if n == 1 and r == 0:
        return 0
    if n == 1 and r >= 1 and r <= 9: 
        count += 1
        result.append(int(now))
        return 1
    return u(n - 1, r - 1, str(r - 1) + now) + u(n - 1, r, str(r) + now) + u(n - 1, r + 1, str(r + 1) + now)

def a(n):
    result = 0
    for i in range(10):
        result += u(n, i, str(i))
    return result

for i in range(1, 11):
    a(i)

result.sort()
print(result[k - 1])
'''
for i in range(1, 1000):
    print(result[i - 1])
'''

Solution (Python):
def givenewluns(string):
    if string[-1] == '0':
        return [string + '0', string + '1']
    elif string[-1] == '9':
        return [string + '8', string + '9']
    else:
        return [string + str(int(string[-1])-1), string + string[-1], string + str(int(string[-1])+1)]

luns = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
counter = 0

K = int(input())

while(counter + len(luns) < K):
    counter += len(luns)
    newluns = []
    for l in luns:
        newluns += givenewluns(l)
    luns = newluns

print(luns[K - counter - 1])

Solution (Python):
from collections import deque
k = int(input())
d = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
if k <= 9:
    print(k)
else:
    cnt = 9
    while cnt < k:
        p = d.popleft()
        pstr = str(p)
        pstr_last = int(pstr[-1])
        
        if pstr_last - 1 >= 0:
            ad = int(pstr + str(pstr_last - 1))
            d.append(ad)
            cnt += 1
        if cnt == k:
            break
            
        ad = int(pstr + str(pstr_last))
        d.append(ad)
        cnt += 1
        if cnt == k:
            break
            
        if pstr_last + 1 <= 9:
            ad = int(pstr + str(pstr_last + 1))
            d.append(ad)
            cnt += 1
        if cnt == k:
            break
            
    print(ad)

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


def f(n):
    global l
    if len(n) == 11:
        return 
    else:
        l.append(int(n))
        n_last = int(n[-1])
        n1, n2, n3 = n_last-1, n_last, n_last+1
        if n_last == 0:
            f(n+str(n2))
            f(n+str(n3))
        elif n_last == 9:
            f(n+str(n1))
            f(n+str(n2))
        else:
            f(n+str(n1))
            f(n+str(n2))
            f(n+str(n3))
            


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

for j in range(10):
    f(str(j))
ll = sorted(list(set(l)))
print(ll[K])

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

k = int(input())

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


def lunlun(s):
    a = int(s[-1])
    if a == 0:
        l = [0,1]
    
    elif a == 9:
        l = [8,9]
    
    else:
        l = [a-1,a,a+1]
    
    ret = []
    for i in l:
        ret.append(s+str(i))
        
    return ret

n_2 = []
for i in a:
    temp = lunlun(i)
    for i in temp:
        n_2.append(i)
 
n_3 = []
for i in n_2:
    temp = lunlun(i)
    for i in temp:
        n_3.append(i)

n_4 = []
for i in n_3:
    temp = lunlun(i)
    for i in temp:
        n_4.append(i)

n_5 = []
for i in n_4:
    temp = lunlun(i)
    for i in temp:
        n_5.append(i)

n_6 = []
for i in n_5:
    temp = lunlun(i)
    for i in temp:
        n_6.append(i)

n_7 = []
for i in n_6:
    temp = lunlun(i)
    for i in temp:
        n_7.append(i)

n_8 = []
for i in n_7:
    temp = lunlun(i)
    for i in temp:
        n_8.append(i)

n_9 = []
for i in n_8:
    temp = lunlun(i)
    for i in temp:
        n_9.append(i)

n_10 = []
for i in n_9:
    temp = lunlun(i)
    for i in temp:
        n_10.append(i)


a.extend(n_2)
a.extend(n_3)
a.extend(n_4)
a.extend(n_5)
a.extend(n_6)
a.extend(n_7)
a.extend(n_8)
a.extend(n_9)
a.extend(n_10)

print(str(a[k-1]))

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

k = int(input())

if k < 10:
    print(k)
    sys.exit()

k -= 9

a = [['00', '01'], ['10', '11', '12'], ['21', '22', '23'], ['32', '33', '34'], ['43', '44', '45'], ['54', '55', '56'], ['65', '66', '67'], ['76', '77', '78'], ['87', '88', '89'], ['98', '99']]

for i in range(1, 10):
    if k <= len(a[i]):
        print(a[i][k - 1])
        sys.exit()
    else:
        k -= len(a[i])

while True:
    a_ = [[] for _ in range(10)]
    for i in range(10):
        n = str(i)
        for j in range(i - 1, i + 2):
            if j < 0:
                continue
            if j > 9:
                continue
            for k_ in a[j]:
                a_[i].append(n + k_)
    a = a_
    
    for i in range(1, 10):
        if k <= len(a[i]):
            print(a[i][k - 1])
            sys.exit()
        else:
            k -= len(a[i])

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

def next(s):
	n = len(s)
	ind_to_check = n-1
	while ind_to_check != 0 and s[ind_to_check] == 9 or s[ind_to_check] - s[ind_to_check-1] == 1:
		ind_to_check -= 1

	if ind_to_check == 0 and s[ind_to_check] == 9:
		s = [1] + [0]*n
	else:
		s[ind_to_check] += 1
		for j in range(ind_to_check+1, n):
			s[j] = max(0, s[j-1] - 1)

	return s


s = [1]
for i in range(k-1):
	
	s = next(s)

print("".join([str(item) for item in s]))

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

dp = [[0]*11 for _ in [0]*11]
dp[1] = [1]*10 + [0]

for i in range(2,11):
    dp[i][0] = dp[i-1][1] + dp[i-1][0]
    for j in range(1,10):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]

S = 0
breakFlg = False
for d in range(1,11):
    for n in range(1,10):
        S += dp[d][n]
        if S>=K:
            breakFlg = True
            S -= dp[d][n]
            break
    if breakFlg: break

memo = dict()
def get(d,n):
    if (d,n) in memo:
        return memo[(d,n)]
    if d==1:
        memo[(d,n)] = [n]
        return [n]
    ret = []
    if n>0:
        for a in get(d-1,n-1):
            ret.append(a+n*(10**(d-1)))
    for a in get(d-1,n):
        ret.append(a+n*(10**(d-1)))
    if n<9:
        for a in get(d-1,n+1):
            ret.append(a+n*(10**(d-1)))
    memo[(d,n)] = ret
    return ret

ans = get(d,n)[K-S-1]
print(ans)

Solution (Python):
k=input()

ln=[1,2,3,4,5,6,7,8,9]
i=0
while len(ln)<100001:
    if ln[i]%10==0:
        ln.append(ln[i]*10)
        ln.append(ln[i]*10+1)
    elif ln[i]%10!=9:
        ln.append(ln[i]*10+ln[i]%10-1)
        ln.append(ln[i]*10+ln[i]%10)
        ln.append(ln[i]*10+ln[i]%10+1)
    else:
        ln.append(ln[i]*10+8)
        ln.append(ln[i]*10+9)
    i+=1



print ln[k-1]

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

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

n = 0
while n < k:
    i = queue.get()
    n += 1
    j = i % 10
    if j == 0:
        queue.put(i*10)
        queue.put(i*10+1)
    elif j == 9:
        queue.put(i*10+8)
        queue.put(i*10+9)
    else:
        queue.put(i*10+j-1)
        queue.put(i*10+j)
        queue.put(i*10+j+1)

print(i)

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

import collections

run_list = collections.defaultdict(list)
run_list[1] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range(2, 11):
    for j in run_list[i-1]:
        if 0 <= int(str(j)[0]) + 1 < 10:
            run_list[i].append(str(int(str(j)[0]) + 1)+str(j))
        if 0 <= int(str(j)[0]) - 1 < 10:
            run_list[i].append(str(int(str(j)[0]) - 1)+str(j))
        if 0 <= int(str(j)[0]) < 10:
            run_list[i].append(str(int(str(j)[0]))+str(j))

all_list = []
for v in run_list.values():
    for vv in v:
        all_list.append(int(vv))
print(sorted(list(set(all_list)))[K])

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

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

while K > len(res):
  newR = []
  for e in res:
    m = e % 10
    if m == 9:
      newR.extend([e * 10 + 8, e * 10 + 9])
    elif m == 0:
      newR.extend([e * 10, e * 10 + 1])
    else:
      newR.extend([e * 10 + m - 1, e * 10 + m, e * 10 + m + 1])
  K -= len(res)
  
  res = newR



print(res[K - 1])

Solution (Python):
import numpy as np
k = int(input()) - 1
if len(str(k)) == 1:
    print(k + 1)
else:

    jjj = 0
    ans = [0]

    num = 0
    dps = []
    dp = [1] * 10
    dp[0] = 0

    flag = False
    for i in range(len(dp)):
        num += dp[i]
        if num > k:
            flag = True
            break

    dp[0] = 1
    dps.append(dp)

    flag = False
    while True:
        dp = [0] * 10
        dp[0] = 0
        for i in range(1, 9):
            dp[i] = sum(dps[-1][i - 1 : i + 2])
        dp[9] = dps[-1][8] + dps[-1][9]


        for i in range(len(dp)):
            num += dp[i]
            if num > k:
                flag = True
            if flag:
                num -= dp[i]
                break
        if flag:
            break
        dp[0] = dps[-1][0] + dps[-1][1]
        dps.append(dp)

    ans = [i]
    k = k - num
    jjj += 1


    try:
        while True:

            num = 0
            ii = i
            for i in range(max([ii - 1, 0]), ii + 2):
            
                if num + dps[-1][i]> k:
                    break
                else:
                    num += dps[-1][i]

            ans.append(i)
            k -= num
            dps = dps[:-1]

            if k == 0 and len(dps) > 0:
                aaa = i - 1
                while True:    
                    if aaa < 0 :
                        aaa = 0
                    ans += [aaa]
                    aaa -= 1
                    dps = dps[:-1]
                    if len(dps) == 0:
                        break
                aaaaaa
    except:
        print("".join(map(str, ans)))

Solution (Python):



K = int(input())


def get_lunlun_number_list(ln_list:list) -> list:
    lunlun_number_list = []
    for ln in ln_list:
        one_place_value = ln % 10
        lunlun_number_list.append(int(str(ln) + str(one_place_value)))
        if one_place_value != 0:
            lunlun_number_list.append(int(str(ln) + str(one_place_value-1)))
        if one_place_value != 9:
            lunlun_number_list.append(int(str(ln) + str(one_place_value+1)))

    return lunlun_number_list

lunlun_number_list = []

lunlun_number_list1 = list(range(1, 10))
lunlun_number_list.extend(lunlun_number_list1)
lunlun_number_list2 = get_lunlun_number_list(lunlun_number_list1)
lunlun_number_list.extend(lunlun_number_list2)
lunlun_number_list3 = get_lunlun_number_list(lunlun_number_list2)
lunlun_number_list.extend(lunlun_number_list3)
lunlun_number_list4 = get_lunlun_number_list(lunlun_number_list3)
lunlun_number_list.extend(lunlun_number_list4)
lunlun_number_list5 = get_lunlun_number_list(lunlun_number_list4)
lunlun_number_list.extend(lunlun_number_list5)
lunlun_number_list6 = get_lunlun_number_list(lunlun_number_list5)
lunlun_number_list.extend(lunlun_number_list6)
lunlun_number_list7 = get_lunlun_number_list(lunlun_number_list6)
lunlun_number_list.extend(lunlun_number_list7)
lunlun_number_list8 = get_lunlun_number_list(lunlun_number_list7)
lunlun_number_list.extend(lunlun_number_list8)
lunlun_number_list9 = get_lunlun_number_list(lunlun_number_list8)
lunlun_number_list.extend(lunlun_number_list9)
lunlun_number_list10 = get_lunlun_number_list(lunlun_number_list9)
lunlun_number_list.extend(lunlun_number_list10)

lunlun_number_list = sorted(lunlun_number_list)


print(lunlun_number_list[K-1])

Solution (Python):
def func(S,x):
    for i in range(x,len(S)):
        if S[i-1] == "0":
            S[i] = "0"
        else:
            S[i] = chr(ord(S[i-1])-1)
    return S

K = int(input())
X = 0


for _ in range(K):
    X += 1
    S = list(str(X))

    i = len(S)-1
    while S[i] == '0':
        i -= 1
    S = func(S,i+1)
    d = len(S)
    for i in range(len(S)-1,0,-1):
        if ord(S[i]) - ord(S[i-1]) > 1:
            S[i-1] = chr(ord(S[i-1])+1)
            d = i
    X = int("".join(func(S,d)))

print(X)

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

dp = [[0]*10 for i in range(20)]
for i in range(10):
    dp[0][i] = 1
ans = 9
for i in range(1,18):
    for j in range(1,10):
        if j == 9:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
        else:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]+dp[i-1][j+1]
    ans += sum(dp[i])
    dp[i][0] = dp[i-1][0] + dp[i-1][1]
    if ans >= k:
        
        s = ""
        for m in range(i,-1,-1):
            if m == i:
                for j in range(9,0,-1):
                    if ans-dp[m][j] >= k:
                        ans -= dp[m][j]
                    else:
                        s += str(j)
                        nex = j
                        
                        break
            else:
                if nex == 9:
                    for j in range(9,7,-1):
                        if ans-dp[m][j] >= k:
                            ans -= dp[m][j]
                        else:
                            s += str(j)
                            nex = j
                            
                            break
                else:
                    for j in range(nex+1,nex-2,-1):
                        if ans-dp[m][j] >= k:
                            ans -= dp[m][j]
                        else:
                            s += str(j)
                            nex = j
                            
                            break



        print(s)
        
        exit()

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


def DFS(num):
    A.add(int(num))
    n=int(num[-1])
    for i in (max(n-1,0),n,min(n+1,9)):
        i=str(i)
        A.add(int(num+i))
        if len(num)<=8:DFS(num+i)


n=int(input())
A=set()
for i in range(1,10):
    DFS(str(i))
A=sorted(A)
print(A[n-1])

Solution (Python):
k = int(input())
ans = 1
n = 1
digits = [1]
ind = 1
while ind<k:
    ii = 0
    for i in range(n-1):
        if digits[i]<9 and abs(digits[i]+1-digits[i+1])<=1:
            ii = i
            break
    else:
        if digits[-1]==9:
            digits = [0]*n
            digits.append(1)
            n += 1
            ind += 1
            continue
        if n>1:
            ii = n-1
    digits[ii] += 1
    for j in range(ii-1, -1, -1):
        digits[j] = max(digits[j+1]-1, 0)
    ind += 1

for i in reversed(digits):
    print(i, end='')
print()

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


dnum2list = {}
dnum2list[1] = list(map(str, range(1, 10)))

for i in range(2, 11):
    dnum2list[i] = []
    for num in dnum2list[i - 1]:
        if num[-1] != '0':
            dnum2list[i].append(num + chr(ord(num[-1]) - 1))
        dnum2list[i].append(num + num[-1])
        if num[-1] != '9':
            dnum2list[i].append(num + chr(ord(num[-1]) + 1))

all_vals = []
for vals in dnum2list.values():
    all_vals += [int(v) for v in vals]

all_vals.sort()
print(sorted(all_vals)[k - 1])

Solution (Python):
k = int(input())
ans = 1
n = 1
digits = [1]
ind = 1
while ind<k:
    ii = 0
    for i in range(n-1):
        if digits[i]<9 and abs(digits[i]+1-digits[i+1])<=1:
            ii = i
            break
    else:
        if digits[-1]==9:
            digits = [0]*n
            digits.append(1)
            n += 1
            ind += 1
            continue
        if n>1:
            ii = n-1
    digits[ii] += 1
    for j in range(ii-1, -1, -1):
        digits[j] = max(digits[j+1]-1, 0)
    ind += 1

for i in reversed(digits):
    print(i, end='')
print()

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

from collections import deque

count = 0
q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)
q.append(5)
q.append(6)
q.append(7)
q.append(8)
q.append(9)
li = []
while q:
    p = q.popleft()
    li.append(p)
    p = str(p)
    count += 1
    if count==10**5:
        break
    if p[-1]!="9" and p[-1]!="0":
        p = str(p)
        z = p + str(int(p[-1])-1)
        za = p + str(int(p[-1]))
        zb = p + str(int(p[-1])+1)
        q.append(int(z))
        q.append(int(za))
        q.append(int(zb))
    elif p[-1]=="9":
        z = p + str(int(p[-1])-1)
        za = p + str(int(p[-1]))
        q.append(int(z))
        q.append(int(za))
    elif p[-1]=="0":
        z = p + str(int(p[-1])+1)
        za = p + str(int(p[-1]))
        q.append(int(z))
        q.append(int(za))
li.sort()
print(li[k-1])

Solution (Python):



def nextrun(x):
    sx = list(str(x))
    for i in reversed(range(len(sx))):
        isInc = True
        if i > 0:
            if int(sx[i]) == 9:
                continue
            if abs(int(sx[i])+1-int(sx[i-1])) <= 1:
                sx[i] = str(int(sx[i])+1)
                for j in range(len(sx)-i-1):
                    sx[i+j+1] = str(max(0,int(sx[i])-j-1))
                return int(''.join(sx))
    if sx[0] == '9':
        ret = ['0']*(len(sx)+1)
        ret[0] = '1'
        return int(''.join(ret))
    else:
        sx[0] = str(int(sx[0])+1)
        for i in range(len(sx)-1):
            sx[i+1] = str(max(0,int(sx[0])-i-1))
        return int(''.join(sx))
        

n = int(input())
a = 0
for i in range(n):
    a = nextrun(a)
print(a)

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

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

len_R_p,len_R_n,digit = 0,9,0
while len_R_n < K:
    for i in range(len_R_p,len_R_n):
        if R[i][digit] == "0":
            R.append(R[i]+"0")
            R.append(R[i]+"1")
        elif R[i][digit] == "9":
            R.append(R[i]+"8")
            R.append(R[i]+"9")
        else:
            R.append(R[i]+str(int(R[i][digit])-1))
            R.append(R[i]+str(int(R[i][digit])))
            R.append(R[i]+str(int(R[i][digit])+1))
    len_R_p = len_R_n
    len_R_n = len(R)
    digit += 1

print(R[K-1])

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

i=0
while i<=8:
    for num in run[i]:
        c=int(num[-1])
        if 1<=c<=8:
            run[i+1].append(num+str(c-1))
            run[i+1].append(num+str(c))
            run[i+1].append(num+str(c+1))
        if c==0:
            run[i+1].append(num+"0")
            run[i+1].append(num+"1")
        if c==9:
            run[i+1].append(num+"8")
            run[i+1].append(num+"9")
    
    i=i+1
total=[]
for r in run:
    for s in r:
        total.append(s)

print(total[k-1])

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

DP = [[1 for i in range(10)] for j in range(12)]


for j in range(1, 12):
    
    for i in range(10):
        DP[j][i] = DP[j-1][i]
        if i != 0:
            DP[j][i] += DP[j-1][i-1]
        if i != 9:
            DP[j][i] += DP[j-1][i+1]
s = 0

res = ""
for j in range(12):
    for i in range(1, 10):
        prev = s
        s += DP[j][i]
        if s >= K:
            res += str(i)
            
            break
    if s >= K:
        break

top = i
keta = j
sa = K - prev
for k in range(keta-1, -1, -1):
    t = 0
    for j in range(max(0, top-1), min(9, top+1)+1):
        
        t_prev = t
        t += DP[k][j]
        if t >= sa:
            res += str(j)
            sa -= t_prev
            top = j
            break
print(res)

Solution (Python):
k = int(input())
li = [str(i) for i in range(1, 10)]
n = 0
while n < 9:
  rep = li[:]
  for r in rep:
    if r[-1] == "0":
      li.append(r+"0")
      li.append(r+"1")
    elif r[-1] == "9":
      li.append(r+"8")
      li.append(r+"9")
    else:
      x = int(r[-1])
      li.append(r+str(x-1))
      li.append(r+str(x))
      li.append(r+str(x+1))
  n += 1

setli = set(li)
li = list(setli)

intli = [int(i) for i in li]
intli.sort()




print(intli[k-1])

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

def dp(k):
    if k<=9:
        return k
    else:
        prev_keta_nums=[1,2,3,4,5,6,7,8,9]
        count=9
        flag = False
        while True:
            next_keta_nums=[]
            for num in prev_keta_nums:
                num_last = int(str(num)[-1])
                if num_last == 9:
                    cands = [8,9]
                elif num_last == 0:
                    cands = [0,1]
                else:
                    cands = [num_last-1,num_last,num_last+1]
                for cand in cands:
                    new_num=int(str(num)+str(cand))
                    next_keta_nums.append(new_num)
                    count+=1
                    if count == k:
                        flag = True
                    if flag:
                        break
                if flag:
                    break
                else:
                    prev_keta_nums = next_keta_nums
            if flag:
                break
        return next_keta_nums[-1]
print(dp(k))

Solution (Python):
def main():
    K = int(input())
    def isr(x):
        a = x % 10
        x //= 10
        b = x % 10
        while x:
            if abs(a - b) > 1:
                return False
            x //= 10
            a, b = b, x % 10
        return True
    dp = [[0] * 11 for _ in range(15)]
    dp2 = [0] * 15
    dp[0][0] = 1
    t = 0

    def nxt(x):
        if x == 0:
            return [0, 1]
        if x == 9:
            return [8, 9]
        return [x - 1, x, x + 1]

    for j in range(1, 10):
        dp[0][j] = 1
        t += dp[0][j]
        if t == K:
            return j

    for i in range(1, 15):
        dp2[i] = t
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
        for j in range(1, 10):
            dp[i][j] = sum(dp[i - 1][j - 1:j + 2])
            if t + dp[i][j] >= K:
                r = j
                K -= t
                for p in reversed(range(i)):
                    t = 0
                    for q in nxt(j):
                        if t + dp[p][q] >= K:
                            K -= t
                            r = r * 10 + q
                            j = q
                            break
                        t += dp[p][q]
                return r
            t += dp[i][j]


print(main())

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

def make(n):
    if len(n) > 10:
        return 0
    if int(n) > 3234566667:
        return 0
    else:
        if n[0] == "0":
            p = ["0","1"]
        elif n[0] == "9":
            p = ["8","9"]
        else:
            p = [str(int(n[0])-1),n[0],str(int(n[0])+1)]

        lun.append(int(n))
        for i in p:
            lun.append(int(i+n))
            make(i+n)
        return 0
for i in range(10):
    make(str(i))

ans = list(set(lun))
ans.sort()

print(ans[K])

Solution (Python):

from collections import deque


def main():
    k = int(input())
    lun = deque(["1", "2", "3", "4", "5", "6", "7", "8", "9"])
    keta = 0
    while len(lun) <= k:
        keta += 1
        for i in range(1, 10):
            generate_lunlun(lun, "", i, keta)
    print(lun[k - 1])


def generate_lunlun(array, s, c, keta):
    if keta == 0:
        array.append(s + str(c))
        return
    if c > 0:
        generate_lunlun(array, s + str(c), c - 1, keta - 1)
    generate_lunlun(array, s + str(c), c, keta - 1)
    if c < 9:
        generate_lunlun(array, s + str(c), c + 1, keta - 1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

k = int(input())

cnt = 9
lnln = deque(range(1, 10))
lnln = list(map(str, lnln))


def f(n, dq):
    x = int(n[-1])
    if x == 0:
        dq.append(n + str(x))
        dq.append(n + str(x + 1))
        return 2
    elif x == 9:
        dq.append(n + str(x - 1))
        dq.append(n + str(x))
        return 2
    else:
        dq.append(n + str(x - 1))
        dq.append(n + str(x))
        dq.append(n + str(x + 1))
        return 3


for i in lnln:
    if cnt > k:
        break
    cnt += f(i, lnln)


print(lnln[k - 1])

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

K = int(input())
nums = []
def make_num(keta, str_num):
    if len(str_num) == keta:
        nums.append(str_num)
        return
    if str_num[-1] == '0':
        
        for i in [0,1]:
            make_num(keta, str_num + str(i))
    elif str_num[-1] == '9':
        
        for i in [8,9]:
            make_num(keta, str_num + str(i))
    else:
        for i in range(-1, 2):
            make_num(keta, str_num + str(int(str_num[-1])+i))

def enum(keta):
    for i in range(1,10):
        make_num(keta, str(i))

keta = 0
while len(nums) < K:
    keta += 1
    enum(keta)


print(nums[K-1])

Solution (Python):
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]
    }

def next_list(m):
    tail = int(str(m)[-1])
    return d[tail]

def lunlun(k):
    if k < 10:
        return k

    ans = [-1, [1,2,3,4,5,6,7,8,9]]
    cnt = 9
    for i in range(2,11):
        ans.append([])
        for pre in ans[i-1]:
            for n in next_list(pre):
                next = int( str(pre)+str(n) )
                ans[i].append(next)
                cnt += 1
                if cnt == K:
                    return next

K = int(input())
print(lunlun(K))

Solution (Python):
l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
l_temp = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def f(x):
    temp = list(str(x))
    t = int(temp[-1])
    if t == 0:
        return int(str(x) + str(t)), int(str(x) + str(t + 1))
    elif t == 9:
        return int(str(x) + str(t - 1)), int(str(x) + str(t))
    else:
        return int(str(x) + str(t - 1)), int(str(x) + str(t)), int(str(x) + str(t + 1))
       

while len(l) < 10 ** 5:
    temp = []
    for l_t in l_temp:
        tem = list(f(l_t))
        for t in tem:
            temp.append(t)
    for t in temp:
        l.append(t)
    l_temp = temp

K = int(input())
print(l[K-1])

Solution (Python):
K = int(input())
ans = [0]
count = 0
def f(n):
    tmp = str(n)
    if int(n) > 3234566667:
        return
    else:
        ans.append(int(n))
    f(str(tmp)+tmp[-1])
    if int(tmp[-1])-1 >= 0:
        f(str(tmp)+str(int(tmp[-1])-1))
    if int(tmp[-1])+1 <= 9:
        f(str(tmp)+str(int(tmp[-1])+1))
f(1)
f(2)
f(3)
f(4)
f(5)
f(6)
f(7)
f(8)
f(9)
ans.sort()
print(ans[K])

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

K = int(input())

cnt = 0
LUN = [[0] * 10 for _ in range(11)]
LUN_AC = [[0] * 10 for _ in range(11)]
LUN[0] = [1] * 10
LUN_AC[1] = [0] + [1] * 9

cnt = 0
for i in range(1, 11):
    
    for d in range(10):
        c = 0
        c += LUN[i-1][d - 1] if 1 <= d and i > 1 else 0
        c += LUN[i - 1][d]
        c += LUN[i - 1][d + 1] if d < 9 and i > 1 else 0

        if d != 0:
            cnt += c

        LUN[i][d] = c
        LUN_AC[i][d] = cnt

        

        if K <= cnt:
            break

    if K <= cnt:
        break



keta = i
rest = K - cnt + c

ans = []
ans.append(d)

for i in range(keta - 1, 0, -1):
    
    c1 = LUN[i][d - 1] if 1 <= d else 0
    if rest <= c1:
        ans.append(d - 1)
        d = d - 1
        continue
    else:
        rest -= c1

    c2 = LUN[i][d]

    if rest <= c2:
        ans.append(d)
        continue
    else:
        rest -= c2

    c3 = LUN[i][d + 1] if d < 9 else 0

    if rest <= c3:
        ans.append(d + 1)
        d = d + 1
        continue
    else:
        rest -= c3

    if rest >= 0:
        print(-1)
        exit()

print("".join(map(str, ans)))

Solution (Python):
from collections import deque

k = int(input())
ans = [i for i in range(1, 10)]
cal1 = [str(i) for i in range(1, 10)]
cal = deque(cal1)

cnt = 0
while (1):
    tmp = cal.popleft()
    last = tmp[-1]
    flag = False
    if last == '0':
        tmp1 = tmp + '0'
        tmp2 = tmp + '1'
    elif last == '9':
        tmp1 = tmp + '8'
        tmp2 = tmp + '9'
    else:
        flag = True
        down = tmp + str(int(last) - 1)
        middle = tmp + last
        up = tmp + str(int(last) + 1)

    if flag:
        ans.append(int(down))
        ans.append(int(up))
        ans.append(int(middle))
        cal.append(down)
        cal.append(up)
        cal.append(middle)
        cnt += 3
    else:
        ans.append(int(tmp1))
        ans.append(int(tmp2))
        cal.append(tmp1)
        cal.append(tmp2)
        cnt += 2

    if cnt > 10**6:
        break
ans.sort()

print(ans[k - 1])

Solution (Python):
from collections import deque
def lun(i,n,all): 
    if n >= num: 
        data.append(all)
    else:
        if i != 0: lun(i-1,n+1, all*10+i-1)
        lun(i,n+1,all*10+i)
        if i != 9:lun(i+1,n+1, all*10+i+1)
        

data = deque()
K = int(input())
for num in range(1,11):
    for i in range(1,10):
        lun(i,1,i)

print(data[K-1])