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 sys
k = int(input())
keta = 0
for x in range(1,11):
    memo_ls = [[0 if (i != 0 or j == 0) else 1 for j in range(10)] for i in range(x)]
    for i in range(1, x):
        for j in range(10):
            memo_ls[i][j] = memo_ls[i-1][j]
            if j > 0:
                memo_ls[i][j] += memo_ls[i-1][j-1]
            if j < 9:
                memo_ls[i][j] += memo_ls[i-1][j+1]
    _sum = sum(memo_ls[-1])
    if _sum >= k:
        keta = x
        break
    else:
        k -= _sum
res = ""
cur_k = k
for start in range(keta, 0, -1):
    last_k = cur_k
    if res == "":
        ls = list(range(1, 10))
    else:
        if 9 > int(res[-1]) > 0:
            ls = [int(res[-1]) - 1, int(res[-1]), int(res[-1]) + 1]
        elif int(res[-1]) > 0:
            ls = [int(res[-1]) - 1, int(res[-1])]
        else:
            ls = [int(res[-1]), int(res[-1]) + 1]
    for i in ls:
        memo_ls = [[0 for i in range(10)] for j in range(start)]
        memo_ls[0][i] = 1
        for ind_keta in range(1, start):
            for j in range(10):
                memo_ls[ind_keta][j] = memo_ls[ind_keta - 1][j]
                if j > 0:
                    memo_ls[ind_keta][j] += memo_ls[ind_keta - 1][j - 1]
                if j < 9:
                    memo_ls[ind_keta][j] += memo_ls[ind_keta - 1][j + 1]
        if sum(memo_ls[-1]) >= cur_k:
            res += str(i)
            break
        else:
            if i == 9:
                res += "0"
                cur_k = last_k
            cur_k -= sum(memo_ls[-1])
print(res)

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

ans = [-10]*11
ans[0] = 1
c = 1
for i in range(k - 1):
    for j in range(c):
        if ans[j] == 9 and ans[j + 1] == -10:
            c += 1
            ans[j + 1] = 1
            for l in range(c - 1):
                ans[l] = 0
            break
        elif ans[j] == 9 or (ans[j] > ans[j + 1] and ans[j + 1] != -10):
            continue
        else:
            ans[j] += 1
            for l in range(j - 1,-1,-1):
                ans[l] = max(0,ans[l + 1] - 1)
            break

for i in range(len(ans)-1,-1,-1):
    if ans[i] == -10:continue
    print(ans[i],end="")
print()

Solution (Python):
from collections import deque

def main():
    K = int(input())
    num_list = list(range(0, 10))
    def bfs():
        q = deque(list(map(str, num_list)))
        
        while len(num_list) < 2 * 10**6:
            now_str = q.popleft()
            now = int(now_str[0])
            for j in [now-1, now, now+1]:
                if j not in [-1, 10]:
                    new = str(j) + now_str
                    q.append(new)
                    if j != 0:
                        num_list.append(int(new))
    
    bfs()
    print(sorted(set(num_list))[K])
            
if __name__ == "__main__":
    main()

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

run = [i for i in range(10)]

for keta in range(10):
    for i in range(len(run)):
        x = run[i] // 10**keta
        if x == 0:
            if int(str(run[i])[0]) > 1:
                continue
        for j in range(max(x-1, 1), min(10, x+2)):
            run.append(run[i] + j*10**(keta+1))


run.sort()
print(run[K])

Solution (Python):




def nextRR(N):
    for i in range(0, len(N)-1):
        if (N[i] <= N[i+1]) and N[i] != 9:
            m = N[i] + 1
            for j in range(i, -1, -1):
                N[j] = m
                if m > 0:
                    m -= 1
            return N

    if N[-1] == 9:
        N = [0] * len(N) + [1]
        return N

    m = N[-1] + 1
    for i in range(len(N)-1, -1, -1):
        N[i] = m
        if m > 0:
            m -= 1
    return N


def solv(K):
    if K <= 12:
        return str(K)
    N = [1, 2]
    for i in range(13, K):
        N = nextRR(N)
    return "".join(map(str, reversed(N)))


if __name__ == "__main__":
    K = int(input())
    ans = solv(K)
    print(ans)

Solution (Python):
N =int(input())
L = [i for i in range(1,10)]
M = L.copy()
for i in range(11):
  S = []
  for x in L:
    if x % 10 == 0:
      S.append(x*10)
      S.append(x*10 + 1)
    elif x % 10 == 9:
      S.append(x*10 + 8)
      S.append(x*10 + 9)
    else:
      S.append(x*10 + x % 10 - 1)
      S.append(x*10 + x % 10)
      S.append(x*10 + x % 10 + 1)
  L = S.copy()
  M += S
print (sorted(M)[N-1])

Solution (Python):
K = input()

A = [1]
for k in range(K-1):
  for d in range(len(A)-1):
    if A[d]<9 and A[d]<=A[d+1]:
      A[d] += 1
      for i in range(d)[::-1]:
        A[i] = max(0, A[i+1]-1)
      break
  else:
    if A[-1]<9:
      A[-1]+=1
      for i in range(len(A)-1)[::-1]:
        A[i] = max(0, A[i+1]-1)
    else:
      for i in range(len(A)):
        A[i] = 0
      A += [1]
print "".join(map(str, A[::-1]))

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

runrun = [[1]*10]
s = sum(runrun[0][1:])
i = 1
while K > s:
  K -= s
  r = [sum(runrun[-1][max(0,i-1):min(10, i+2)]) for i in range(10)]
  runrun.append(r)
  s = sum(r[1:])
  i += 1

j = 1
while runrun[-1][j] < K:
  K -= runrun[-1][j]
  j += 1

ans = [j]
k = -2
while K and len(runrun) >= -k:
  j = max(0, j-1)
  while runrun[k][j] < K:
    K -= runrun[k][j]
    j += 1
  k -= 1
  ans.append(j)

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

Solution (Python):
from heapq import heappop, heappush, heapify
K = int(input())
M = K

que = list(range(1, 10))
V = set()
heapify(que)

while M + 100 >= 0:
    top = heappop(que)
    if top in V:
        continue
    V.add(top)
    M -= 1

    top = str(top)
    L = int(top[0])
    R = int(top[-1])

    for i in (L - 1, L, L + 1):
        if 1 <= i <= 9:
            heappush(que, int(str(i) + top))
    for i in (R - 1, R, R + 1):
        if 0 <= i <= 9:
            heappush(que, int(top + str(i)))

V = [int(d) for d in V]
V.sort()
print(V[K - 1])

Solution (Python):
K=int(input())
tmp=[1,2,3,4,5,6,7,8,9]
while True:
  k=len(tmp)
  if K<=k:
    print(tmp[K-1])
    break
  else:
    K-=k
    dum=tmp[:]
    tmp=[]
    for a in dum:
      if a%10==0:
        tmp.append(a*10+0)
        tmp.append(a*10+1)
      elif a%10==9:
        tmp.append(a*10+8)
        tmp.append(a*10+9)
      else:
        tmp.append(a*10+a%10-1)
        tmp.append(a*10+a%10)
        tmp.append(a*10+a%10+1)

Solution (Python):
def search(i,d,run,md,mrun):
    if d==md:
        run[0]+=1
        if run[0]==mrun:
            return str(i)
        else:
            return -1

    elif i==0:
        s=search(0,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
        s=search(1,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
    elif i==9:
        s=search(8,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
        s=search(9,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
    else:
        s=search(i-1,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
        s=search(i,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
        s=search(i+1,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
    
    return -1

N=int(input())

digit=1
run=[0]


for d in range(1,11):
    for i in range(1,10):
        a=search(i,1,run,d,N)
        if a !=-1:
            print(a)
            break

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

dp = [[str(i)] for i in range(1, 10)]
count = 9

ansFlag = False
while (True):
    if K <= 9:
        break
    for i in range(9):
        numList = dp[i]
        newNumList = []
        for n in numList:
            lastNum = n[-1]
            if int(lastNum) >= 1:
                newNum1 = str(n) + str(int(lastNum) - 1)
                count += 1
                newNumList.append(newNum1)
                if count == K:
                    ansFlag = True
                    break

            newNum2 = str(n) + str(int(lastNum))
            count += 1
            newNumList.append(newNum2)
            if count == K:
                ansFlag = True
                break

            if int(lastNum) <= 8:
                newNum3 = str(n) + str(int(lastNum) + 1)
                count += 1
                newNumList.append(newNum3)
                if count == K:
                    ansFlag = True
                    break
        if ansFlag:
            break
        dp[i] = newNumList
    if ansFlag:
        break

ans = K
if K >= 10:
    ans = newNumList[-1]

print(ans)

Solution (Python):
k = int(input())
import sys
c = 0
A = []
for i in range(10):
    for t in range(1, 10):
        if i == 0:
            c += 1
            anss = t
            
            if c == k:
                print(anss)
                sys.exit()
        else:
            
            for j in range(3**i):
                jj = j
                j3 = [0] * i
                for p in range(i-1,-1,-1):
                    j3[p] = jj%3-1
                    jj//=3
                
                ng = 0
                tt = t
                ans = [tt]
                
                for p in range(i):
                    tt += j3[p]
                    ans.append(tt)
                    if tt < 0 or tt >= 10:
                        ng = 1
                        break
                
                if ng == 0:
                    c += 1
                    anss = "".join([str(ij) for ij in ans])
                
                if c == k:
                    print(anss)
                    sys.exit()

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

rnrn = list(range(10))

idx = 0
for idx_base in range(0, K + 1):
    base = rnrn[idx_base]
    for d in (-1, 0, 1):
        digit = base % 10 + d
        if digit < 0 or 9 < digit: continue
        if base == 0: continue
        rnrn.append(10 * base + digit)
        if len(rnrn) >= K + 1: break
    if len(rnrn) >= K + 1: break


print(rnrn[K])

Solution (Python):
n = int(input())
l = [1,2,3,4,5,6,7,8,9]
if(n<=9):
    print(l[n-1])
else:
    i=9
    j=0
    while(i<n):
        s = str(l[j])
        a = int(s[-1])
        b = l[j]*(10)
        if(a==9):
            l.append(b+(a-1))
            l.append(b+a)
            i+=2
        elif(a==0):
            l.append(b+a)
            l.append(b+(a+1))
            i+=2
        else:
            l.append(b+(a-1))
            l.append(b+a)
            l.append(b+(a+1))
            i+=3
        j+=1
    print(l[n-1])

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

def hantei(n):
    string = str(n)
    length = len(string)
    ret = True
    for i in range(length-1):
        if abs(int(string[i]) - int(string[i+1])) > 1:
            ret = False
            break
    return ret

lst = [i for i in range(10)]
dic = {}
dic[1] = lst.copy()
keta = 2
while len(lst) < k+1:
    new = []
    for i in range(1, 10):
        tasu = i*(10**(keta-1))
        for j in sorted(dic.keys()):
            temp_lst = dic[j]
            bit = 0
            for youso in temp_lst:
                num = tasu + youso
                if hantei(num):
                    new.append(num)
                    bit = 1
                elif bit == 1:
                    break
    dic[keta] = new.copy()
    lst.extend(new)
    keta += 1

print(lst[k])

Solution (Python):





import sys
from io import StringIO
import unittest
import os

sys.setrecursionlimit(500*500)

runc=0

def tonari(n,x,keta,k):
    
    
    
    
    
    global runc
    if keta==1:
        runc+=1
        if runc==k:
            print(n)
            sys.exit()
        return 0

    if x==0:
        yy=[0,1]
    elif x==9:
        yy=[8,9]
    else:
        yy=[x-1,x,x+1]
    for y in yy:
        
        tonari(n+y*(10**(keta-2)),y,keta-1,k)
        
        

    

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    k=int(readline())

    for keta in range(1,100):
        for i in range(1,10):
            tonari(i*(10**(keta-1)),i,keta,k)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

Solution (Python):



def solve(*args: str) -> str:
    k = int(args[0])

    ret = 0
    count = 0
    prev = []
    while not ret:
        cur = []
        for i in range(10):
            c = str(i)
            if len(prev):
                for p in prev:
                    if abs(ord(p[0])-ord(c)) <= 1:
                        cur.append(c+p)
                        if c != '0':
                            count += 1
                            if count == k:
                                ret = c+p
            else:
                cur.append(c)
                if c != '0':
                    count += 1
                    if count == k:
                        ret = c
        prev = cur

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
from collections import deque
k = int(input())
lis = {1,2,3,4,5,6,7,8,9,10}
def dfs(x):
    d = ['-1','0','1']
    que = deque([x])
    cnt = 1
    while len(que) != 0:
        val = que.pop()
        
        val3 = str(val)
        if len(str(val)) < 10:
            
            for i in range(3):
                val2 = int(val3[-1]) + int(d[i])
                
                if val2 >= 0 and val2 < 10:
                    lis.add(int(str(val) + str(val2)))
                    que.append(int(str(val) + str(val2)))
        else:
            lis.add(val)
    return lis
for i in range(1,10):
    ans = dfs(i)
lis = list(lis)
lis.sort()




print(lis[k-1])

Solution (Python):
k = int(input())
if k < 10:
    print(k)
else:
    k -= 9
    run= {}
    run[1] = {i: 1 for i in range(0, 10)}
    now_dig = 1
    flag = 0
    flag2 = 0
    ans = 0
    while flag == 0:
        now_dig += 1
        run[now_dig] = {}
        for num in range(0, 10):
            if num == 0:
                run[now_dig][num] = run[now_dig-1][num] + run[now_dig-1][num+1]
            elif num == 9:
                run[now_dig][num] = run[now_dig-1][num-1] + run[now_dig-1][num]
            else:
                run[now_dig][num] = run[now_dig-1][num-1] + run[now_dig-1][num] + run[now_dig-1][num+1]
            if num != 0 and k - run[now_dig][num] > 0:
                k -= run[now_dig][num]
            elif num != 0:
                flag = 1
                
                ans += num*pow(10, now_dig-1)
                while now_dig > 1:
                    now_dig -= 1
                    if num == 0:
                        now_num = 0
                        end = 1
                    elif num == 9:
                        now_num = 8
                        end = 9
                    else:
                        now_num = num - 1
                        end = num + 1
                    while k - run[now_dig][now_num] > 0 and now_num <= end:
                        k -= run[now_dig][now_num]
                        now_num += 1
                    ans += now_num*pow(10, now_dig-1)
                    num = now_num
                break
        

    print(ans)

Solution (Python):
K = int(input())
dp = [['1','2','3','4','5','6','7','8','9'],[]]

cnt = 9
keta = 0
dp_num = 0
while True:
    num = 2
    current_base_num_str = dp[keta][dp_num][-1]
    current_base_num_int = int(current_base_num_str)
    break_flag = False
    for i in range(-1,num):
        if current_base_num_int + i > 9 or current_base_num_int + i < 0:
            continue
        dp[keta+1].append(dp[keta][dp_num] + str(current_base_num_int + i))
        cnt += 1
        if cnt >= K:
            break_flag = True
            break
    if break_flag:
        break
    if dp_num < len(dp[keta])-1:
        dp_num += 1
    else:
        dp_num = 0
        keta += 1
        dp.append([])
if K < 10:
    print(K)
else:
    if len(dp[keta+1]) == 0:
        print(dp[keta][-1])
    else:
        print(dp[keta+1][-1])

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

STEP = [-1,0,1]

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

    if K < 10:
        print(K)
        exit()

    l = [x for x in range(1,10)]
    c = 9

    while True:
        nxt = []
        for x in l:
            tail = int(str(x)[-1])
            for diff in STEP:
                if tail + diff >= 0 and tail + diff < 10:
                    c += 1
                    nxt.append(int(str(x) + str(tail + diff)))
                    if c == K:
                        print(nxt[-1])
                        exit()
        l = nxt



if __name__ == "__main__":
    main()

Solution (Python):
"""
NTC here
"""
import sys
inp = sys.stdin.readline
def input(): return inp().strip()




 
def iin(): return int(input())
 
 
def lin(): return list(map(int, input().split()))
 
 


 
def main():
    T = 1
    while T:
        T-=1
        k = iin()
        ans = [[0 for i in range(10)] for j in range(10)]
        for i in range(10):
            ans[0][i]=1
        for i in range(1, 10):
            for j in range(10):
                sm = ans[i-1][j]
                if j-1>=0:
                    sm+=ans[i-1][j-1]
                if j+1<10:
                    sm+=ans[i-1][j+1]
                ans[i][j] = sm
        
        br = 0
        i1, j1 = 0, 1
        for i in range(10):
            if br:break
            for j in range(1, 10):
                
                if k<=ans[i][j]:
                    i1, j1 = i, j
                    br = 1
                    break
                else:
                    k-=ans[i][j]
        
        sol = [str(j1)]
        for i in range(i1-1, -1, -1):
            chk = ([j1-1] if j1-1>=0 else []) + [j1] + ([j1+1] if j1+1<10 else [])
            for j in chk:
                if k<=ans[i][j]:
                    sol.append(str(j))
                    j1 = j
                    break
                else:
                    k-=ans[i][j]
        print(''.join(sol))





 
 
 
 
main()

Solution (Python):
from collections import deque
def main():
    q=deque()
    for i in range(1,10):
        q.append((str(i)))
    Ans=[]
    while q:
        s=q.popleft()
        if int(s)>3234566667:
            continue
        Ans.append(int(s))
        d=int(s[-1])
        if d==0:
            q.append(s+'0')
            q.append(s+'1')
        elif d==9:
            q.append(s+'8')
            q.append(s+'9')
        else:
            V=[d-1,d,d+1]
            for v in V:
                q.append(s+str(v))
    Ans.sort()
    
    k=int(input())
    print(Ans[k-1])
    
if __name__=='__main__':
    main()

Solution (Python):
K=int(input())
l=[]
for i in range(10):
    r=[]
    if (i-1)<0:
        pass
    else:
        r.append(str(i-1))
    r.append(str(i))
    if (i+1)>9:
        pass
    else:
        r.append(str(i+1))
    l.append(r)
lst=[]
count=0
for i in range(1,10):
    lst.append(str(i))
    count+=1
queue=lst[0]
tmp=0
while(1):
    queue=lst[tmp]
    s=queue[-1]
    num=int(s)
    for i in range(len(l[num])):
        s=queue
        s=s+l[num][i]
        lst.append(s)
        count+=1
    tmp+=1
    if count>=K:
        break
print(lst[K-1])

Solution (Python):
k = int(input())
len_map = dict()
cur = [i for i in range(1,10)] 
total = cur
counter = 9
cur_digit_len = 1
while counter < 10**5:
    tmp = []
    for sample in cur:
        sample_str = str(sample)
        if int(sample_str[-1]) > 0:
            tmp.append(int(sample_str + str(int(sample_str[-1])-1)))
        tmp.append(int(sample_str + sample_str[-1]))
        if int(sample_str[-1]) < 9:
            tmp.append(int(sample_str + str(int(sample_str[-1])+1)))
    total.extend(tmp)
    counter += len(tmp)
    cur = tmp
print(total[k-1])

Solution (Python):
from collections import deque

k = int(input())

tbl = []
queue = deque()

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

while queue:
    if len(tbl) >= k:
        break
    x = queue.popleft()
    tbl.append(x)
    if x % 10 == 0:
        queue.append(x * 10)
        queue.append(x * 10 + 1)
    elif x % 10 == 9:
        queue.append(x * 10 + 8)
        queue.append(x * 10 + 9)
    else:
        queue.append(x * 10 + x % 10 - 1)
        queue.append(x * 10 + x % 10)
        queue.append(x * 10 + x % 10 + 1)

print(tbl[k - 1])

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

from collections import deque

cnt = 0


s = [[i] for i in range(1, 10)]
stack = deque(s)
while stack:
    cur = stack.popleft()
    cnt += 1
    if cnt == k:
        print(''.join(list(map(str, cur))))
        sys.exit()
    c = cur[-1]
    for i in (c-1, c, c+1):
        if i >= 0 and i <= 9:
            next = cur[:]
            next.append(i)
            stack.append(next)

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

d = deque(map(str, range(1, 10)))

counter = 1
while True:
    v = d.popleft()
    if (counter == k):
        print(v)
        break

    counter += 1

    first = v[-1]
    if first == "9":
        d.append(v + "8")
        d.append(v + "9") 
    elif first == "0":
        d.append(v + "0")
        d.append(v + "1") 
    else:
        for i in [-1, 0, 1]:
            d.append(v + str(int(first) + i))

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

def serch(dp,i,j,k,now):
    if i<0:
        return ""
    
    
    for l in range(3):
        if j+l-1==-1:
            continue
        if now+dp[i][j+l-1]<k:
            now+=dp[i][j+l-1]
        else:
            return str(j+l-1)+serch(dp,i-1,j+l-1,k,now)

k=int(input())
dp=[[0]*10 for i in range(10)]
for i in range(10):
    dp[0][i]=1


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




now=0
for i in range(10):
    for j in range(1,10):
        if now+dp[i][j]<k:
            now+=dp[i][j]
            continue
        else:
            
            ans=str(j)
            ans+=serch(dp,i-1,j,k,now)
            print(ans)
            quit()

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

flag=0
lis=[]
for i in range(0, 10):
  if i == 0:
    starti = 0
    endi = 10
  else:
    starti = max(i-1, 0)
    endi = min(i+2, 10)
  for j in range(starti, endi):
    if i == 0 and j == 0:
      startj = 0
      endj = 10
    else:
      startj = max(j-1, 0)
      endj = min(j+2, 10)
    for k in range(startj, endj):
      if i == 0 and j == 0 and k == 0:
        startk = 0
        endk = 10
      else:
        startk = max(k-1, 0)
        endk = min(k+2, 10)
      for l in range(startk, endk):
        if i == 0 and j == 0 and k==0 and l == 0:
          startl = 0
          endl = 10
        else:
          startl = max(l-1, 0)
          endl = min(l+2, 10)
        for m in range(startl, endl):
          if i == 0 and j == 0 and k==0 and l == 0 and m==0:
            startm = 0
            endm = 10
          else:
            startm = max(m-1, 0)
            endm = min(m+2, 10)
          for n in range(startm, endm):
            if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0:
              startn = 0
              endn = 10
            else:
              startn = max(n-1, 0)
              endn = min(n+2, 10)
            for o in range(startn, endn):
              if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0 and o==0:
                starto = 0
                endo = 10
              else:
                starto = max(o-1, 0)
                endo = min(o+2, 10)
              for p in range(starto, endo):
                if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0 and o==0 and p==0:
                  startp = 0
                  endp = 10
                else:
                  startp = max(p-1, 0)
                  endp = min(p+2, 10)
                for q in range(startp, endp):
                  if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0 and o==0 and p==0 and q==0:
                    startq = 0
                    endq = 10
                  else:
                    startq = max(q-1, 0)
                    endq = min(q+2, 10)
                  for r in range(startq, endq):
                    if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0 and o==0 and p==0 and q==0 and r==0:
                      startr = 0
                      endr = 10
                    else:
                      startr = max(r-1, 0)
                      endr = min(r+2, 10)
                    lis.append(r+10*q+100*p+1000*o+10000*n+100000*m+1000000*l+10000000*k+100000000*j+1000000000*i)

print(sorted(set(lis))[K])

Solution (Python):
def main():
    k = int(input())
    d = dict()

    
    order = 0
    find = False
    for n_digit in range(1, 20):
        
        if n_digit == 1:
            for i in range(10):
                d[(n_digit, i)] = 1
            
        else:
            for i in range(10):
                d[(n_digit, i)] = d[(n_digit - 1, i)]
                if i >= 1:
                    d[(n_digit, i)] += d[(n_digit - 1, i - 1)]
                if i <= 8:
                    d[(n_digit, i)] += d[(n_digit - 1, i + 1)]

        for i in range(1, 10):
            if order + d[(n_digit, i)] < k:
                order += d[(n_digit, i)]
            else:
                find = True
            
            if find:
                break

        if find:
            break

    
    ans = list()
    ans.append(i)

    for digit in range(n_digit - 1, 0, -1):
        for j in range(i - 1, i + 2):
            if 0 <= j <= 9:
                if order + d[(digit, j)] < k:
                    order += d[(digit, j)]
                else:
                    ans.append(j)
                    i = j
                    break

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


main()

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

xs = list(range(1, 10))
x_cnt = 0

while x_cnt + len(xs) < k:
    x_cnt += len(xs)
    next_xs = []
    for x in xs:
        ones_place = x % 10
        mul_10 = x * 10
        if ones_place != 0:
            next_xs.append(mul_10 + ones_place - 1)
        next_xs.append(mul_10 + ones_place)
        if ones_place != 9:
            next_xs.append(mul_10 + ones_place + 1)
    xs = next_xs

print(xs[k - x_cnt - 1])

Solution (Python):
N = int(input())
digits = 1
dp = []
dp.append([i for i in range(1,10)])
K = 9

if(N<=9):
    print(dp[0][N-1])
    exit(0)
else:
    N -= 9

while(N>0):
    tmp = []
    for n in dp[digits-1]:
        base = int(str(n)[-1])
        for i in [-1,0,1]:
            if(base+i >= 0 and base+i<10):
                tmp.append(int(str(n)+str(base+i)))
    digits += 1
    K = len(tmp)
    N -= K
    dp.append(tmp)

print(dp[digits-1][N-1])

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

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

class C:
    cnt = 0
    
    def f(self, t, d, a, s, K): 
        if self.cnt == K:
            return
        if d == 0:
            
            self.cnt += 1
            if self.cnt == K:
                print(a)
                
            return
        
        l = range(1, 10) if s else nextInts(t)
        for x in l:
            self.f(x, d-1, a * 10 + x, False, K)


c = C()
q = 1
while c.cnt != K:
    c.f(0, q, 0, True, K)
    q += 1

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(1000000)
input = sys.stdin.readline
INF = 2**62-1

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


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def is_lunlun(n):
    s = str(n)
    for i in range(len(s)-1):
        if abs(int(s[i])-int(s[i+1])) > 1:
            return False
    return True

def slv(k):
    n = 1
    for _ in range(k-1):
        j = 0
        while True:
            l = 10**j
            t = 0
            t += n + l
            t -= (n+l) % l
            m = (t % (10**(j+1))) // l
            
            for i in range(j-1, -1, -1):
                t += (10 ** i) * max(0, m-(j-i))
            
            if is_lunlun(t):
                n = t
                break
            else:
                j+=1
            
            
        
    return n



def main():
    K = read_int()
    print(slv(K))



if __name__ == '__main__':
    main()

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

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

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

def f(p,x,m):
    a = [-1,0,1]
    for k in a:
        y = x+k
        if y >= 0 and y < 10:
            q = p+y*(10**m)
            if m == 0:
                aa.append(q)
            else:
                f(q,y,m-1)

for i in range(1,10):
    for j in range(1,10):
        f(j*(10**i),j,i-1)

n = ni()
print(aa[n-1])

Solution (Python):
import sys
K = int(input())
anss = [[i for i in range(1,10)]]
count = 9
if K <= 9:
  print(K)
  sys.exit()
for i in range(1,15):
  ans = []
  
  origin = anss[i-1]
  for o in origin:
    s = str(o)
    for j in range(10):
      if abs(int(s[-1]) - j) <= 1:
        a = int(s+str(j))
        count += 1
        if count == K:
          print(a)
          sys.exit()
        ans.append(a)
  anss.append(ans)

Solution (Python):
k = int(input())
nums = [i for i in range(1,10)]
tmp = [i for i in range(1,10)]
if k <= 10:
    print(tmp[k-1])
    exit()
for _ in range(10**2):
    tmpp = []
    for num in tmp:
        for i in range(-1,2):
            if 10 > num%10+i >= 0 and (num*10 + (num%10+i))!= nums[-1] and abs(num%10 - (num%10+i)) <= 1:
                nums.append(num*10+(num%10+i))
                tmpp.append(num*10+(num%10+i))
                if len(nums) == k+1:
                    print(nums[k-1])
                    exit()
    tmp = tmpp