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

Solution (Python):



def is_runrun(n):
    str_n = str(n)
    for i, s in enumerate(str_n):
        if i < len(str_n) - 1:
            if abs(int(s) - int(str_n[i + 1])) > 1:
                return False

    return True


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

    i = 0
    keta = 1
    created = {}
    count = 0
    while True:
        before_runruns = created.get(keta - 1, [])
        now_runruns = created.get(keta, [])

        if keta == 1:
            now_runruns.append(str(i))

            if str(i) != "0":
                count += 1
                if count == k:
                    return str(i)

        for runrun in before_runruns:
            if abs(int(str(runrun)[0]) - i) <= 1:
                now_runruns.append(str(i) + str(runrun))

                if str(i) != "0":
                    count += 1
                    if count == k:
                        return str(i) + str(runrun)

        created[keta] = now_runruns

        if i == 9:
            keta += 1
            i = 0
        else:
            i += 1


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

Solution (Python):


def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return helper


@memoize
def f(d, k):
    if d == 1:
        return 1

    s = f(d-1, k)

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

    if k < 9:
        s += f(d-1, k+1)

    return s


def g1(K):
    d = 1
    cnt = 0

    while True:
        for i in range(1, 10):
            cnt2 = f(d, i)
            if (cnt + cnt2 >= K):
                return (cnt, d, i)

            cnt += cnt2

        d += 1


def g2(K, cnt, d, k):
    d -= 1
    X = [k]

    while d > 0:
        for j in range(-1, 2):
            if k+j < 0 or k+j > 9:
                continue

            cnt2 = f(d, k+j)

            if (cnt + cnt2 >= K):
                X.append(k+j)
                k = k+j
                break

            cnt += cnt2

        d -= 1

    return X

K = int(input())
cnt, d, k = g1(K)
print(''.join(map(str, g2(K, cnt , d, k))))

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

k = int(input())

ans = list(range(1, 10))
d = 10
prev = ['0'] + list(map(str, ans))
while len(ans) <= k:
    _next = []
    for v in prev:
        if v[0] == '0':
            _next.append('0' + v)
            _next.append('1' + v)
            ans.append(int('1' + v))
            continue
        if v[0] == '1':
            _next.append('0' + v)
            _next.append('1' + v)
            ans.append(int('1' + v))
            _next.append('2' + v)
            ans.append(int('2' + v))
            continue
        if v[0] == '9':
            _next.append('8' + v)
            ans.append(int('8' + v))
            _next.append('9' + v)
            ans.append(int('9' + v))
            continue
        i = int(v[0])
        s1 = str(i - 1)
        s2 = str(i)
        s3 = str(i + 1)
        _next.append(s1 + v)
        ans.append(int(s1 + v))
        _next.append(s2 + v)
        ans.append(int(s2 + v))
        _next.append(s3 + v)
        ans.append(int(s3 + v))
    prev = _next

print(sorted(ans)[k-1])

Solution (Python):
K = int(input())
ans = []
R = [[] for _ in range(11)]
for i in range(1,10):
  R[0].append(i)
for i in range(1,11):
  R[i] = [10**i]
  if i > 1:
    for j in range(i-1):
      for r in R[i-2-j]:
        d = r//(10**(i-2-j))
        if d <= 1:
          R[i].append(10**i+r)
  for r in R[i-1]:
    d = r//(10**(i-1))
    for j in [-1,0,1]:
      if 1<= d+j <= 9:
        R[i].append((d+j)*(10**i)+r)
A = []






for i in range(11):
  for r in R[i]:
    A.append(r)
A.sort()

print(A[K-1])

Solution (Python):
def add(N):
    n = N % 10
    ret = N * 10
    if n == 0:
        return [ret, ret + 1]
    elif n == 9:
        return [ret + 9,ret + 8]
    else:
        return [ret + n - 1, ret + n, ret + n + 1]

X = int(input())
l = [1,2,3,4,5,6,7,8,9]
lists = list()
lists.append(l)
n = 9
while n < X:
    list_ = lists[-1]
    templist = list()
    for l_ in list_:
        vals = add(l_)
        n += len(vals)
        templist.extend(vals)
    lists.append(templist)

R = list()
for list_ in lists:
    R.extend(list_)
R.sort()
print(R[X-1])

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

left = 0
right = 9

while len(lst) < k:
  for i in range(left, right + 1):
    if lst[i] % 10 > 0:
      lst.append(lst[i] * 10 + lst[i] % 10 - 1)
    lst.append(lst[i] * 10 + lst[i] % 10)
    if lst[i] % 10 < 9:
      lst.append(lst[i] * 10 + lst[i] % 10 + 1)
  left = right + 1
  right = len(lst) - 1

print(lst[k - 1])

Solution (Python):
k = int(input())
if k < 11:
    print(k)
else:
    s = [None] * 20
    target = k
    target -= 10
    s[1] = 1
    for i in range(target):
        
        for j in range(20):
            if s[j] is None:
                s[j] = 0
            
            s[j] += 1  

            if s[j] > 9:  
                
                s[j] = 0
                continue  

            if j != 0:
                
                for k in range(j, -1, -1):
                    if s[k] == 0:
                        s[k - 1] = 0
                    else:
                        s[k - 1] = s[k] - 1

            if s[j + 1] != None and abs(s[j] - s[j + 1]) > 1:
                
                continue
            
            break
    
    res = ""
    for i in range(20):
        if s[i] != None:
            res = str(s[i]) + res
        else:
            break
    print(int(res))

Solution (Python):
K = int(input())
now = 0
if K < 10:
    result = K
else:
    tmp_list = []
    for i in range(1, 10):
        tmp_list.append(i)
    now = 9
    while now != K:
        next_list = []
        for i in range(len(tmp_list)):
            fig = tmp_list[i] % 10
            if fig != 0:
                next_list.append(tmp_list[i] * 10 + fig - 1)
                now += 1
                if now == K:
                    break
            next_list.append(tmp_list[i] * 10 + fig)
            now += 1
            if now == K:
                break

            if fig != 9:
                next_list.append(tmp_list[i] * 10 + fig + 1)
                now += 1
                if now == K:
                    break
        tmp_list = next_list

if K > 10:
    result = tmp_list[-1]

print(result)

Solution (Python):

import sys

def next_lunlun(x):
    K = len(x)
    if len(x) == 1:
        return str(int(x) + 1)
    elif x[-1] == '9':
        next =  next_lunlun(x[:-1])
        if int(next[-1]) - 1 >= 0:
            return next + str(int(next[-1]) - 1)
        else:
            return next + '0'
    elif x[-2] >= x[-1]:
        return x[:-1] + str(int(x[-1]) + 1)
    else:
        next = next_lunlun(x[:-1])
        if int(next[-1]) - 1 >= 0:
            return next + str(int(next[-1]) - 1)
        else:
            return next + '0'


def solve(K: int):
    x = '0'
    for k in range(K):
        x = next_lunlun(x)
    print(x)
    return



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

if __name__ == '__main__':
    main()

Solution (Python):
def aaa(val):
    val = int(val)
    if val == 0:
        return [0, 1]
    if val == 1:
        return [0, 1, 2]
    if val == 2:
        return [1, 2, 3]
    if val == 3:
        return [2, 3, 4]
    if val == 4:
        return [3, 4, 5]
    if val == 5:
        return [4, 5, 6]
    if val == 6:
        return [5, 6, 7]
    if val == 7:
        return [6, 7, 8]
    if val == 8:
        return [7, 8, 9]
    if val == 9:
        return [8, 9]
        
l = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range(100000):
    
    
    ll = aaa(str(l[i])[-1])
    for a in ll:
        l.append(int(str(l[i]) + str(a)))
    if len(l) > 100000:
        break
        

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

Solution (Python):

"""
1,2,3,4,5,6,7,8,9,10,11,12,21,22,23,32,33,34...100,101,110,111,112,121,122,123,210,211,212,321,322,323,332,333,334,343,
"""

"""
最大の位
1のとき、100とか120とかある
9のとき、987,989,998,999
...狭い
"""
import time
t = time.time();
k = int(input())
if k <= 9:
    print(k)
else:
    ls = []
    ls_str = ["0","1","2","3","4","5","6","7","8","9"]
    ls.append(ls_str)
    
    len_ls = [9]
    dic = {"0":["0","1"],"9":["8","9"]}

    for i in range(1,9):
        dic[str(i)] = [str(i-1),str(i),str(i+1)]
    for i in range(9):
        ls_tmp = []
        ls_former = ls[-1]
        for j in range(len(ls_former)):
            for l in dic[ls_former[j][0]]:
                ls_tmp.append(l+ls_former[j])
        ls.append(sorted(ls_tmp))
    ls_ans = []
    for i in range(len(ls)):
        ls_ans.append([j for j in ls[i] if j[0] != "0"])

    for i in range(1,len(ls_ans)):
        len_ls.append(len_ls[-1] + len(ls_ans[i]))

    for i in range(len(len_ls)):
        if i != 0 and len_ls[i] >= k:
            k -= (len_ls[i-1]+1)
            break

    
    
    print(ls_ans[i][k])

Solution (Python):
k = int(input())
if k < 10:
	print(k)
else:
	dp = [[0 for _ in range(10)] for _ in range(30)] 
	for i in range(10):
		dp[1][i] = 1
	for i in range(2, 30):
		for j in range(10):
			if j == 0:
				dp[i][j] = dp[i-1][j] + dp[i-1][j+1]
			elif 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]

	
	cnt = 0
	for i in range(1, 30):
		for j in range(1, 10):
			cnt += dp[i][j]
			
			if cnt >= k:
				keta = i
				num = j
				break
		else:
			continue
		break

	left = k - cnt + dp[keta][num]


	ans = [num]
	while keta != 1:
		if num == 0:
			li = [0, 1]
		elif num == 9:
			li = [-1, 0]
		else:
			li = [-1, 0, 1]
		for i in li:
			
			if left > dp[keta-1][num+i]:
				left -= dp[keta-1][num+i]
			else:
				num += i
				ans.append(num)
				keta -= 1
				break
	ansl = []
	for i in range(len(ans)):
		ansl.append(str(ans[i]))
	anss = ''.join(ansl)
	print(anss)

Solution (Python):
K = int(input())
ln = [["0"]]
ln.append([str(i) for i in range(1,10)])
for i in range(1,10):
  tmp = []
  for j in ln[i]:
    for k in range(-1,2):
      if int(j[-1])+k >=0 and int(j[-1])+k<10:
        tmp.append(j+str(int(j[-1])+k))
  ln.append(tmp) 
ln = sum(ln,[])
print(ln[K])

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

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

K=int(input())
c=9
cb=0
r_list=[1,2,3,4,5,6,7,8,9]
while(c<K):
    tmp=[]
    for i in r_list:
        if(i%10==0):
            tmp.append(i*10)
            tmp.append(i*10+1)
        elif(i%10==9):
            tmp.append(i*10+8)
            tmp.append(i*10+9)
        else:
            tmp.append(i*10+i%10-1)
            tmp.append(i*10+i%10)
            tmp.append(i*10+i%10+1)
    cb=c
    r_list=tmp
    c+=len(r_list)

    
r_list.sort()
ans=r_list[K-cb-1]
print(ans)

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







def next_lunlun(k):
    k[0] += 1
    for i in range(len(k) - 1):
        if k[i] < 10:
            break
        k[i] -= 10
        k[i+1] += 1

    if k[-1] >= 10:
        k[-1] -= 10
        k.append(1)

    for i in range(len(k)-1, 0, -1):
        if abs(k[i] - k[i-1]) <= 1:
            continue
        elif k[i] > k[i-1]:
            k[i-1] = k[i] - 1
            for j in range(i-2, -1, -1):
                k[j] = max(k[j + 1] - 1, 0)
            break
        else:
            pivot = len(k) - 1
            for j in range(i, len(k) - 1):
                if k[j + 1] > k[j] or (k[j] < 9 and k[j+1] == k[j]):
                    pivot = j
                    break
            if pivot == len(k) - 1 and k[-1] == 9:
                for j in range(len(k)):
                    k[j] = 0
                k.append(1)
            else:
                k[pivot] += 1
                for j in range(pivot-1, -1, -1):
                    k[j] = max(k[j+1] -1 , 0)
            break

    return k

i = [0]
for idx in range(k):
    next_lunlun(i)
base = 0
for num in reversed(i):
    base *= 10
    base += num
print(base)

Solution (Python):
def inputs(): return [int(x) for x in input().split()]
def bfs(s):
    if len(s)==cnt1:
        return s
    a = s[-1]
    if a=="0":
        A = ["0","1"]
    elif a=="9":
        A = ["8","9"]
    else:
        A=[str(int(a)-1),a,str(int(a)+1)]
    for i in A:
        if bfs(s+i)!=None:
            ans.append(bfs(s+i))
ans=["1","2","3","4","5","6","7","8","9"]
n = int(input())
cnt1 = 2
while len(ans)<n:
    for i in ans:
        if len(i)==cnt1-1:
            bfs(i)
    cnt1+=1
ans = list(map(int,ans))
ans.sort()

print(ans[n-1])

Solution (Python):

k = int(input())
"""
1,2,3 ... ,9
           10, 11, 12,  21, 22, 23,  ...  98, 99,
100, 101, 110,111,112, 121,122,123
          210,211,212, 221,222,223, 232,233,234
          
...
                                            987,988,989, 998,999
"""
"""
a = ['1','2','3','4','5','6','7','8','9'] 

b = [] 
for i in range(8):
    b += [str(i+1)+str(i), str(i+1)+str(i+1), str(i+1)+str(i+2)]
i = 8
b_ [str(i+1)+str(i), str(i+1)+str(i+1)]
"""
li = []

li_ = []
for i in range(9):
    li_.append(str(i+1))
li += li_

keta = 10


for t in range(keta-1): 
    li_x = []
    for v in li_:
        i = int(v[-1])
            
        
        if i != 0:
            li_x.append(v+str(i-1))
        li_x.append(v+str(i))
        if i+1 < 10:
            li_x.append(v+str(i+1))
            
    li += li_x
    li_ = li_x
    
    
    
    
    
li = list(map(int, li))
li.sort()

print(li[k-1])

Solution (Python):
dic = {}
def rec(d, pre, acc):
    if d == 1:
        if 1 <= pre <= 8:
            return [acc+c for c in map(str, [pre-1, pre, pre+1])]
        elif pre == 9:
            return [acc+c for c in ["8", "9"]]
        else:
            return [acc+c for c in ["0", "1"]]
    ans = []
    for x in range(max(0,pre-1), min(pre+2, 10)):
        ans += rec(d-1, x, acc+str(x))
    return ans
K = int(input())
ls = [1,2,3,4,5,6,7,8,9]
d = 2
while len(ls) < K:
    for i in range(1,10):
        ls += rec(d-1, i, str(i))
    d+=1
print(ls[K-1])

Solution (Python):
import heapq
from collections import defaultdict, deque
from math import ceil, factorial
from fractions import gcd
import sys
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10**9+7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


K = ii()

runrun = deque()
runrunAll = []
new = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
runrun.append(new)
runrunAll.extend(new)
for i in range(1, 10):
    before = runrun[i-1]
    new = deque()
    for b in before:
        head = b[0]
        ihead = int(head)
        if head == '0':
            new.append(str(ihead) + b)
            new.append(str(ihead+1) + b)
        elif head == '9':
            new.append(str(ihead-1) + b)
            new.append(str(ihead) + b)
        else:
            new.append(str(ihead-1) + b)
            new.append(str(ihead) + b)
            new.append(str(ihead+1) + b)
    runrun.append(new)
    runrunAll.extend(new)

runrunAll = [int(r) for r in runrunAll]
runrunAll = sorted(set(runrunAll))
print(runrunAll[K])

Solution (Python):

import sys

def next_lunlun(x):
    K = len(x)
    if len(x) == 1:
        return str(int(x) + 1)
    if x[-1] == '9':
        next =  next_lunlun(x[:-1])
        if int(next[-1]) - 1 >= 0:
            return next + str(int(next[-1]) - 1)
        else:
            return next + '0'

    if x[-2] >= x[-1]:
        return x[:-1] + str(int(x[-1]) + 1)
    else:
        next = next_lunlun(x[:-1])
        if int(next[-1]) - 1 >= 0:
            return next + str(int(next[-1]) - 1)
        else:
            return next + '0'


def solve(K: int):
    x = '0'
    for k in range(K):
        x = next_lunlun(x)
    print(x)
    return



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

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque


def solve(K: int):
    G = []
    m = {
        '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],
    }
    q = deque([])
    for i in list(range(1, 10)):
        q.appendleft(i)
    while(len(G) <= 100000):
        v = str(q.pop())
        G.append(v)
        for nv in m[v[-1]]:
            q.appendleft(v + str(nv)) 
    print(G[K-1])
    return



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

if __name__ == '__main__':
    main()

Solution (Python):
def pat(K,count,keta,num):
    
    if count == -1:
        return -1
    elif keta == 1:
        if count == K-1:
            print(num)
            return count + 1
        else:
            return (count+1)

    else:
        if (int(num[-1])) -1 >= 0:
            count = pat(K,count,keta-1,num+str(int(num[-1])-1))
        count = pat(K,count,keta-1,num+num[-1])
        if (int(num[-1])+1) <= 9:
            count = pat(K,count,keta-1,num+str(int(num[-1])+1))
    if count >=K:
        return -1
    else:
        return count
K = int(input())
count = 0
ans = list()
keta = 0

while True:
    keta += 1
    for i in range(1,10):
        count = pat(K,count,keta,str(i))
        
        if count  == -1:
            break
    if count == -1:
        break

Solution (Python):
list=[]
for a in range(1,10):
 list.append(a)
 for b in range(a-(a>0),a+(a<9)+1):
  list.append(a*10+b) 
  for c in range(b-(b>0),b+(b<9)+1):
   list.append(a*100+b*10+c)
   for d in range(c-(c>0),c+(c<9)+1):
    list.append(a*1000+b*100+c*10+d)
    for e in range(d-(d>0),d+(d<9)+1):
     list.append(a*10000+b*1000+c*100+d*10+e)
     for f in range(e-(e>0),e+(e<9)+1):
      list.append(a*100000+b*10000+c*1000+d*100+e*10+f)
      for g in range(f-(f>0),f+(f<9)+1):
       list.append(a*1000000+b*100000+c*10000+d*1000+e*100+f*10+g)
       for h in range(g-(g>0),g+(g<9)+1):
        list.append(a*10000000+b*1000000+c*100000+d*10000+e*1000+f*100+g*10+h)
        for i in range(h-(h>0),h+(h<9)+1):
         list.append(a*100000000+b*10000000+c*1000000+d*100000+e*10000+f*1000+g*100+h*10+i)
         for j in range(i-(i>0),i+(i<9)+1):
          list.append(a*1000000000+b*100000000+c*10000000+d*1000000+e*100000+f*10000+g*1000+h*100+i*10+j)

list.sort()
x=int(input())
print(list[x-1])

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



def dil(i):
    if 1<=i<=8:
        return [i-1,i,i+1]
    if i==0:
        return [0,1]
    if i==9:
        return [8,9]

K = I()


dp = [[[0]*10 for _ in range(10)] for _ in range(12)]
for i in range(10):
    dp[1][i][i] = 1

for i in range(2,12):
    for j in range(10):
        for k in range(10):
            if 1<=k<=8:
                dp[i][j][k] = dp[i-1][j][k-1]+dp[i-1][j][k]+dp[i-1][j][k+1]
            if k==0:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j][k+1]
            if k==9:
                dp[i][j][k] = dp[i-1][j][k-1]+dp[i-1][j][k]


dp2 = [[0]*10 for _ in range(12)]
for i in range(12):
    for j in range(10):
        dp2[i][j] = sum(dp[i][j])

i = 1
aa = 0
while 1:
    if aa+sum(dp2[i][1:]) >= K:
        L = i
        break
    aa += sum(dp2[i][1:])
    i += 1

for i in range(L):
    K -= sum(dp2[i][1:])

temp = 0
now = 0
ans = ''
dl = [i for i in range(1,10)]
for l in range(L):
    last_j = dl[0]
    for j in dl:
        if temp+now+dp2[L-l][j]>=K:
            break
        else:
            now += dp2[L-l][j]
            last_j = j+1
    ans += str(last_j)
    temp = temp+now
    now = 0
    dl = dil(last_j)

print(int(ans))

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(200000)


def read():
    K = int(input())
    return K,


def dfs(i, d, s, q):
    if i == 1:
        q.append(s + str(d))
        return
    if d >= 1:
        dfs(i-1, d-1, s+str(d), q)
    dfs(i-1, d, s+str(d), q)
    if d < 9:
        dfs(i-1, d+1, s+str(d), q)


def solve(K):
    q = deque()
    for i in range(1, 11):
        for d in range(1, 10):
            dfs(i, d, "", q)
    return q[K-1]
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Solution (Python):
X = [1, 2, 3, 4, 5, 6, 7, 8, 9]
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(9):
    B = []
    for a in A:
        r = a % 10
        if r > 0:
            B.append(10*a+r-1)
        if r < 9:
            B.append(10*a+r+1)
        B.append(10*a+r)
    X = X+B
    A = B
X.sort()
k = int(input())
print(X[k-1])

Solution (Python):
from collections import deque

K = int(input())
que = deque()
runrun = []

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

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

while True:
    n = que.popleft()
    n_simo1 = int(str(n)[-1])
    nums = abs01(n_simo1)
    for num in nums:
        que.append(n*10+num)
    runrun.append(n)
    if len(runrun) == K:
        print(runrun[-1])
        
        
        exit()

Solution (Python):
import sys
sys.setrecursionlimit(10000)

K = int(input())

NL = {}

def nextLunlun(n):
    if n in NL:
        return NL[n]
    if n < 9:
        ans = n + 1
    else:
        k = n + 1
        sk = str(k)
        a = int(sk[-2])
        b = int(sk[-1])
        if b == 0 or b - a > 1:
            l = nextLunlun(n // 10)
            l1 = l % 10
            if l1 == 0:
                ans = l * 10
            else:
                ans = l * 10 + l1 - 1
        else:
            ans = k
    NL[n] = ans
    return ans

def lunlun(n):
    if n < 10:
        ans = n
    else:
        ans = 10
        for i in range(n-10):
            ans = nextLunlun(ans)
    return ans

print(lunlun(K))

Solution (Python):
k = int(input())
cnt = 9
q = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]

if k <= cnt:
    print(q[k-1])

while True:
    if cnt >= k:
        break
    num = q.pop(0)
    list_num = list(num)
    a = int(list_num[-1])
    for i in range(10):
        if abs(a-i) < 2:
            cnt += 1
            if i == 0:
                q.append(num+"0")
            elif i == 1:
                q.append(num +"1")
            elif i == 2:
                q.append(num +"2")
            elif i == 3:
                q.append(num+"3")
            elif i == 4:
                q.append(num+"4")
            elif i == 5:
                q.append(num+"5")
            elif i == 6:
                q.append(num+"6")
            elif i == 7:
                q.append(num+"7")
            elif i == 8:
                q.append(num+"8")
            elif i == 9:
                q.append(num+"9")

if k > 9:
    print(q[k-cnt-1])

Solution (Python):
from sys import stdin


def main():
    K = int(stdin.readline().rstrip())

    def check(x):
        s = str(x)
        for i in range(len(s) - 1):
            if 1 < abs(int(s[i]) - int(s[i + 1])):
                return False
        return True

    if K <= 100:
        count = 0
        i = 1
        while True:
            if check(i):
                count += 1
            if count == K:
                print(i)
                return
            i += 1
    else:
        def inner(n):
            s = str(n)
            for idx in range(len(s) - 1, 0, -1):
                c1 = int(s[idx])
                c2 = int(s[idx - 1])
                if c1 != 9 and ((c2 - 1) == c1 or c2 == c1):
                    c1 += 1
                    new_s = s[:idx] + str(c1)
                    for _ in range(len(s) - len(new_s)):
                        new_s += str(max(int(new_s[-1]) - 1, 0))
                    return int(new_s)
            if int(s[0]) != 9:
                new_s = str(int(s[0]) + 1)
                for _ in range(len(s) - len(new_s)):
                    new_s += str(max(int(new_s[-1]) - 1, 0))
                return int(new_s)
            else:
                new_s = '1'
                for _ in range(len(s)):
                    new_s += str(max(int(new_s[-1]) - 1, 0))
                return int(new_s)

        ans = 878
        for i in range(101, K + 1):
            ans = inner(ans)
        print(ans)


if __name__ == "__main__":
    main()

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

chart = [[0 for _ in range(10)] for __ in range(9)]
chart.insert(0,[1 for _ in range(10)])

for i in range(1,10): 
    for j in range(10): 
        if j == 0:
            chart[i][j] = chart[i-1][j] + chart[i-1][j+1]
        elif j == 9:
            chart[i][j] = chart[i-1][j-1] + chart[i-1][j]
        else:
            chart[i][j] = chart[i-1][j-1] + chart[i-1][j] + chart[i-1][j+1]

sum_list = [sum(row[1:]) for row in chart]

count = 0
for i,elem in enumerate(sum_list):
    count += elem
    if count > k:
        idx = i
        diff = k-sum(sum_list[:i]) 
        break

digit = ''
start = 0
end = 10
first = True

while idx >= 0:
    
    count = 0
    if first:
        target_row = chart[idx][start:end]
        target_row[0] = 0
        first = False
    else:
        target_row = chart[idx][start:end]
    for i,num in enumerate(target_row):
        count += num
        if count >= diff:
            digit += str(start+i)
            diff = diff - (count - num)
            idx -= 1
            if start + i == 0:
                start = 0
                end = 2
            elif start + i == 9:
                start = 8
                end = 10
            else:
                s = start
                start = s + i - 1
                end = s + i + 2
            break
        
print(digit)

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

te = [[i for i in range(1, 10)]]
a = te[0]
for i in range(11):
    te2 = []
    for j in te[i]:
        c = j%10
        if c == 0:
            te2 += [j*10 + c + k for k in (0, 1)]
        elif c == 9:
            te2 += [j*10 + c + k for k in (-1, 0)]
        else:
            te2 += [j*10 + c + k for k in (-1, 0, 1)]
    te.append(te2)
    a += te2
print(a[k-1])

Solution (Python):
import sys
K = int(input())
if K < 10:
    print(K)
    sys.exit()
lst = [[str(i)] for i in range(10)]
i = 9
while True:
    new_lst = [[] for j in range(10)]
    for j in range(10):     
        for k in range(-1, 2):  
            if j == 0 and k == -1:
                continue
            if j == 9 and k == 1:
                break
            for l in lst[j+k]:
                tmp = str(j) + str(l)
                new_lst[j].append(tmp)
                
                if j != 0:
                    i += 1
                    if i == K:
                        print(int(tmp))
                        sys.exit()
    
    lst = new_lst.copy()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
def f(v,i,ans):
    if i == 0:return
    if str(v)[-1] != "0":
        x = int(str(v)+str(int(str(v)[-1])-1))
        ans.add(x)
        f(x,i-1,ans)
    y = int(str(v)+str(v)[-1])
    ans.add(y)
    f(y,i-1,ans)
    if str(v)[-1] != "9":
        z = int(str(v)+str(int(str(v)[-1])+1))
        ans.add(z)
        f(z,i-1,ans)
def main():
    K = int(input())
    ans = set()
    for i in range(1,10):
        ans.add(i)
        f(i,10,ans)
    ans = list(ans)
    ans.sort()
    print(ans[K-1])
if __name__ == "__main__":
    main()

Solution (Python):








import sys
sys.setrecursionlimit(10000)
def rec(keta,num,val,cache):
    if keta==0:
        
        cache.append(val)
        return None

    
    if num!=0:
        tmp=val+(num-1)*10**(keta-1)
        rec(keta-1,num-1,tmp,cache)
    if num!=9:
        tmp=val+(num+1)*10**(keta-1)
        rec(keta-1,num+1,tmp,cache)

    
    tmp=val+(num)*10**(keta-1)
    
    
    rec(keta-1,num,tmp,cache)
    


ans=[]

for n in range(10):
    for i in range(10):
        rec(n,i,i*(10**(n)),ans)


ans=set(ans)
ans=list(ans)
ans.sort()
n=int(input())
print(ans[n])

Solution (Python):
def main():
    from builtins import int, map, list, print, len
    from collections import deque
    import sys
    sys.setrecursionlimit(10 ** 6)

    input = sys.stdin.readline
    input_list = (lambda: input().rstrip().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    K = input_number()
    cnt = [0]
    queue = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

    def check():
        now = 0
        while len(queue) > 0 and cnt[0] < K:
            now = queue.popleft()
            cnt[0] += 1
            x = now % 10
            num_ls = [x - 1, x, x + 1]
            for num in num_ls:
                if num < 0 or num > 9: continue
                queue.append(now * 10 + num)
        print(now)
    check()


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
from collections import deque

def main():
    K = int(input())
    cnt = 0
    dq = deque(['1','2','3','4','5','6','7','8','9'])
    while cnt < K:
        cnt += 1
        d = dq.popleft()
        a = int(d[-1])
        if a == 0:
            dq.append(d+str(0))
            dq.append(d+str(1))
        elif a == 9:
            dq.append(d+str(8))
            dq.append(d+str(9))
        else:
            for i in range(a-1, a+2):
                dq.append(d+str(i))
    print(d)



if __name__ == '__main__':
    main()