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):
n = int(input())
listnum = [[0, 1],[0, 1, 2],[1, 2, 3],[2, 3, 4],[3, 4, 5],[4, 5, 6],[5, 6, 7],[6, 7, 8],[7, 8, 9],[8, 9]]
listans = []
for i in range(1, 10):
    numb = str(i)
    listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        numb = str(i) + str(j)
        listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            numb = str(i) + str(j) + str(m)
            listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                numb = str(i) + str(j) + str(m) + str(x)
                listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                for x2 in listnum[x]:
                    numb = str(i) + str(j) + str(m) + str(x) + str(x2)
                    listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                for x2 in listnum[x]:
                    for x3 in listnum[x2]:
                        numb = str(i) + str(j) + str(m) + str(x) + str(x2) + str(x3)
                        listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                for x2 in listnum[x]:
                    for x3 in listnum[x2]:
                        for x4 in listnum[x3]:
                            numb = str(i) + str(j) + str(m) + str(x) + str(x2) + str(x3) + str(x4)
                            listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                for x2 in listnum[x]:
                    for x3 in listnum[x2]:
                        for x4 in listnum[x3]:
                            for x5 in listnum[x4]:
                                numb = str(i) + str(j) + str(m) + str(x) + str(x2) + str(x3) + str(x4) + str(x5)
                                listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                for x2 in listnum[x]:
                    for x3 in listnum[x2]:
                        for x4 in listnum[x3]:
                            for x5 in listnum[x4]:
                                for x6 in listnum[x5]:
                                    numb = str(i) + str(j) + str(m) + str(x) + str(x2) + str(x3) + str(x4) + str(x5) + str(x6)
                                    listans.append(int(numb))
for i in range(1, 5):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                for x2 in listnum[x]:
                    for x3 in listnum[x2]:
                        for x4 in listnum[x3]:
                            for x5 in listnum[x4]:
                                for x6 in listnum[x5]:
                                    for x7 in listnum[x6]:
                                        numb = str(i) + str(j) + str(m) + str(x) + str(x2) + str(x3) + str(x4) + str(x5) + str(x6) + str(x7)
                                        listans.append(int(numb))
print(listans[n - 1])

Solution (Python):
import numpy as np

K = int(input())

top = np.ones(10, dtype=int)
adj = np.eye(10, dtype=int)
adj[1:, :-1] += np.eye(9, dtype=int)
adj[:-1, 1:] += np.eye(9, dtype=int)

counts = [top]
tmp = top
for _ in range(10):
    tmp = np.dot(tmp, adj)
    counts.append(tmp)

for i in range(10):
    for j in range(1, 10):
        if K > counts[i][j]:
            K -= counts[i][j]
        else:
            break
    else:
        continue
    break

ans = [-1] * (i + 1)
ans[i] = j

for d in range(i, 0, -1):
    for k in range(max(0, j - 1), min(9, j + 1) + 1):
        if K > counts[d - 1][k]:
            K -= counts[d - 1][k]
        else:
            ans[d - 1] = k
            j = k
            break


print("".join(list(map(str, ans))[::-1]))

Solution (Python):
K = int(input())
l = [0]*(10**5+10)
l[1:10] = list(range(1,10))
keta = 2
i=10
def res(now):
    if int(now[-1])==0:
      for a in range(0,2):
        ret=str(now)+str(a)
        yield ret
    elif int(now[-1])==9:
      for a in range(8,10):
        ret=str(now)+str(a)
        yield ret
    else:
      for a in range(int(now[-1])-1,int(now[-1])+2):
        ret=str(now)+str(a)
        yield ret
        
while i!=10**5+1:
  if keta==1:
    keta+=1
    l[i]=i
    i+=1
  elif keta==2:
    for j in range(1,10):
      for k in res(str(j)):
        l[i]=k
        i+=1
    keta+=1
  elif keta==3:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          l[i]=a
          i+=1
    keta+=1
  elif keta==4:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            l[i]=b
            i+=1
    keta+=1
  elif keta==5:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            for c in res(str(b)):
              l[i]=c
              i+=1
    keta+=1
  elif keta==6:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            for c in res(str(b)):
              for d in res(str(c)):
                l[i]=d
                i+=1
    keta+=1
  elif keta==7:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            for c in res(str(b)):
              for d in res(str(c)):
                for e in res(str(d)):
                  l[i]=e
                  i+=1
    keta+=1
  elif keta==8:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            for c in res(str(b)):
              for d in res(str(c)):
                for e in res(str(d)):
                  for f in res(str(e)):
                    l[i]=f
                    i+=1
    keta+=1
  elif keta==9:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            for c in res(str(b)):
              for d in res(str(c)):
                for e in res(str(d)):
                  for f in res(str(e)):
                    for g in res(str(f)):
                      l[i]=g
                      i+=1
    keta+=1
  elif keta==10:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            for c in res(str(b)):
              for d in res(str(c)):
                for e in res(str(d)):
                  for f in res(str(e)):
                    for g in res(str(f)):
                      for h in res(str(g)):
                        l[i]=h
                        i+=1
                        if i==10**5+5:
                          break
                      else:
                        continue
                      break
                    else:
                      continue
                    break
                  else:
                    continue
                  break
                else:
                  continue
                break
              else:
                continue
              break
            else:
              continue
            break
          else:
            continue
          break
        else:
          continue
        break
      else:
        continue
      break
    else:
      continue
    break
    
print(int(l[K]))

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

ans = [0]

def hoge(n):
    global ans
    if ans[-n] != 9:
        ans[-n]+=1
        if check():
            pass
        else:
            huga(n)
    else:
        if len(ans) < n+1:
            ans = [0] * (n+1)
            ans[0] = 1
        else:
            huga(n)

def huga(n):
    global ans
    ans[-(n+1)]+=1
    for i in range(n,0,-1):
        if(ans[-(i+1)]==0):
            ans[-i] = 0
        else:
            ans[-i]=ans[-(i+1)]-1
    ans[-(n+1)]-=1
    hoge(n+1)


def check():
    global ans
    for i in range(len(ans)-1):
        if abs(ans[i]-ans[i+1])>1:
            return False
    return True
       


for i in range(K):
    hoge(1)
print(''.join(map(str,ans)))

Solution (Python):
n=int(input())
if n<10: print(n); exit()
l=[[[] for _ in range(10)] for _ in range(10)]
l[0]=[[i] for i in range(10)]
c=9
for i in range(9):
  for j in range(10):
    for k in (-1,0,1):
      if 0<=j+k<=9:
        for h in l[i][j+k]:
          if j: c+=1
          t=j*10**(i+1)+h
          l[i+1][j]+=[t]
          if c==n: print(t); exit()

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

k = INT()
if k <= 10:
    print(k)
    exit()
arr = [0 for _ in range(15)]
arr[1] = 1
for i in range(k - 10):
    for j in range(12):
        
        flag = True
        for k in range(j):
            if arr[k] == arr[k + 1] + 1 or arr[k] == 9:
                continue
            flag = False
        
        if flag and sum(arr[j + 1:]) == 0 and arr[j] < 9:
            
            arr[j] += 1
            for k in reversed(range(j)):
                arr[k] = max(0, arr[k + 1] - 1)
            break
        elif arr[j] == arr[j + 1] + 1 and arr[j + 1] < arr[j + 2] + 1:
            
            arr[j + 1] += 1
            for k in reversed(range(j + 1)):
                arr[k] = max(0, arr[k + 1] - 1)
            break
        elif sum(arr[:j + 1]) == 9 * (j + 1) and arr[j + 1] < 9 and (arr[j + 1] < arr[j + 2] + 1 or arr[j + 2] == 0):
            
            arr[j + 1] += 1
            for k in reversed(range(j + 1)):
                arr[k] = max(0, arr[k + 1] - 1)
            break
        elif (arr[j] == arr[j + 1] or arr[j] == arr[j + 1] - 1) and arr[j] < 9:
            
            arr[j] += 1
            break
    
arr.reverse()
for i in range(15):
    arr[i] = str(arr[i])
ans = ''.join(arr)
ans = int(ans)
print(ans)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

k = ii()
if k//10 ==0:
    print(k)
    exit()
ans = 0
alis = [[0]*10 for _ in range(100)]
blis = [[0]*10 for _ in range(100)]
for i in range(10):
    alis[0][i] = 1
    blis[0][i] = i
    tmp = i
flag = False
for l in range(1,100):
    for i in range(10):
        if i == 0:
            alis[l][i] = alis[l-1][1] + alis[l-1][0]
            continue
        elif i == 9:
            alis[l][i] = alis[l-1][8] + alis[l-1][9]
        else:
            alis[l][i] = alis[l-1][i] + alis[l-1][i+1] + alis[l-1][i-1]
        blis[l][i] = tmp + alis[l][i] 
        if blis[l][i] >= k:
            banme = k - tmp
            retu = l+1
            hazime = i
            flag = True
            break
        else:
            tmp = blis[l][i]
    if flag:
        break

ans = [0]*retu
ans[0] = hazime
for i in range(1,retu):
    if hazime == 0:
        if banme - alis[retu-1-i][hazime] <=0:
            ans[i] = hazime 
        else:
            banme -= alis[retu-1-i][hazime]
            ans[i] = hazime +1
            hazime = hazime +1
        continue
    elif hazime == 9:
        if banme - alis[retu-1-i][hazime-1] <=0:
            ans[i] = hazime -1
            hazime = hazime -1
        else:
            banme -= alis[retu-1-i][hazime-1]
            ans[i] = hazime 
            hazime = hazime 
        continue
    else:
        if banme - alis[retu-1-i][hazime-1] <=0:
            ans[i] = hazime -1
            hazime = hazime -1
        elif banme - alis[retu-1-i][hazime-1] - alis[retu-1-i][hazime] <=0:
            banme -= alis[retu-1-i][hazime-1]
            ans[i] = hazime 
            hazime = hazime 
        else:
            banme -= (alis[retu-1-i][hazime-1] + alis[retu-1-i][hazime])
            ans[i] = hazime +1
            hazime = hazime +1
aa = 0
for i in range(len(ans)):
    aa += ans[i]*(10**(len(ans)-1-i))
print(aa)

Solution (Python):
import numpy as np

k = int(input())


def get_top(rem):
    number = 0

    numbers = np.zeros((100,10), dtype=np.int64)
    numbers[0] += 1
    for i in range(100):
        for j in range(10):
            if j == 0:
                numbers[i+1][j] = numbers[i][j] + numbers[i][j+1]
            elif j == 9:
                numbers[i+1][j] = numbers[i][j-1] + numbers[i][j]
                number += numbers[i+1][j]
            else:
                numbers[i+1][j] = numbers[i][j-1] + numbers[i][j] + numbers[i][j+1]
                number += numbers[i+1][j]
            if number >= rem:
                break
        if number >= rem:
            break
    return i, j, k-(number - numbers[i+1][j]), numbers


def get_after_second(top, remains):
    pass

ans = ""

if k <= 9:
    print(k)
else:
    k -= 9
    dig, top, remain, nums = get_top(k)
    ans += str(top)
    for i in range(dig+1):
        digit = dig - i
        if not top == 0:
            second_top = top - 1
            if not top == 9:
                for j in range(3):
                    if remain - nums[digit][second_top + j] <= 0:
                        top = second_top + j
                        break
                    else:
                        remain -= nums[digit][second_top + j]
            else:
                for j in range(2):
                    if remain - nums[digit][second_top + j] <= 0:
                        top = second_top + j
                        break
                    else:
                        remain -= nums[digit][second_top + j]
        else:
            second_top = top
            for j in range(2):
                if remain - nums[digit][second_top + j] <= 0:
                    top = second_top + j
                    break
                else:
                    remain -= nums[digit][second_top + j]
        ans += str(top)
    print(ans)

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

q=["1","2","3","4","5","6","7","8","9"]
x=9
for i in q:
    if x>100000:
        break
    x+=1
    a=i[-1]
    for j in ([-1,0,1]):
        bb=int(a)+j
        if bb<10 and bb>=0:
            q.append(i+str(bb))
 
       
print(q[k-1])

Solution (Python):



def f(n):
    C = [[1 for i in range(10)]]
    while sum(d for c in C for d in c[1:]) < n:
        C.append([sum(C[-1][max(0,i-1):min(i+2,10)]) for i in range(10)])
    return C

def solve():
    n = int(input())
    C = f(n)
    X = []
    m = sum(d for c in C[:-1] for d in c[1:])
    x = 1
    for x in range(1,10):
        if m + C[-1][x] < n:
            m += C[-1][x]
        else:
            break
    X.append(x)
    C = C[:-1]
    for c in C[::-1]:
        for x in range(max(0,X[-1]-1), min(10,X[-1]+2)):
            if m + c[x] < n:
                m += c[x]
            else:
                break
        X.append(x)
    return ''.join(map(str,X))


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

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K = INT()

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


l = []
while len(l) != K:
    a = q.popleft()
    l.append(a)
    for i in range(0, 10):
        last = int(a[-1])
        b = deepcopy(a)
        if last == 0:
            if i == 1 or i == 0:
                b = b + str(i)
                q.append(b)
        elif last == 9:
            if i == 8 or i == 9:
                b = b + str(i)
                q.append(b)
        else:
            if last - 1 <= i <= last + 1:
                b = b + str(i)
                q.append(b)
        
        
        
print(l[-1])

Solution (Python):
K = int(input())
ary = [0]*(K+1)
for i in range(min(K+1, 10)):
    ary[i] = str(i)
bi = 1
n = 0
b = int(ary[bi][-1])
for i in range(10, K+1):
    if n > 9:
        bi += 1
        b = int(ary[bi][-1])
        n = b-1
    if n > b+1:
        bi += 1
        b = int(ary[bi][-1])
        n = b-1
    if n < 0:
        n = 0
    ary[i] = ''.join([ary[bi], str(n)])
    n += 1
print(ary[-1])

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

q=["1","2","3","4","5","6","7","8","9"]
x=9
for i in q:
    if x>100000:
        break
    x+=1
    a=i[-1]
    for j in ([-1,0,1]):
        bb=int(a)+j
        if bb<10 and bb>=0:
            q.append(i+str(bb))
 
       
print(q[k-1])

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

if k < 10:
    print(k)
    exit(0)

digits = [{k: 1 for k in range(10)}]
count = 9
digits[0]["lc"] = 9
while count < k:
    dg = {}
    dg[0] = digits[-1][0] + digits[-1][1]
    for i in range(1, 9):
        dg[i] = digits[-1][i - 1] + digits[-1][i] + digits[-1][i + 1]
    dg[9] = digits[-1][8] + digits[-1][9]
    dg["lc"] = digits[-1]["lc"] + sum(dg[i] for i in range(1, 10))
    count = dg["lc"]
    digits.append(dg)

def count_lun(base, index, last_digit=None):
    if index < 0:
        return ""
    if last_digit is None:
        rng = range(1, 10)
    elif last_digit == 0:
        rng = range(2)
    elif last_digit == 9:
        rng = range(8, 10)
    else:
        rng = range(last_digit - 1, last_digit + 2)
    for i in rng:
        base += digits[index][i]
        if base >= k:
            return str(i) + count_lun(base - digits[index][i], index - 1, i)

res = count_lun(digits[-2]["lc"], len(digits) - 1)
print(res)

Solution (Python):
K=int(input())
l=[0,1,2,3,4,5,6,7,8,9]
cnt=0
def dfs(s, depth):
    if depth>8:
        return
    S=str(s)
    ls=int(S[-1])
    for i in range(max(0,ls-1),min(10,ls+2)):
        n=int(S+str(i))
        l.append(n)
        dfs(n, depth+1)
for i in range(1, 10):
    dfs(i, 0)
l.sort()
print(l[K])

Solution (Python):

import sys

K = int(input())
if K < 10:
    print(K)
    sys.exit()
i = 9
operation = [-1, 0, 1]
lst = [str(i + 1) for i in range(9)]
while True:
    tmp = []
    for a in lst:
        for ope in operation:
            val = int(a[-1]) + ope
            if 0 <= val <= 9:
                i += 1
                if i == K:
                    print(int(a + str(val)))
                    sys.exit()
                tmp.append(a + str(val))
    lst = tmp

Solution (Python):

import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")


K = int(input())						


A=[0,1,2,3,4,5,6,7,8,9]
S=[]
for a in A:
	S.append(str(a))

from collections import deque
Q = deque()


B=list(S)

while True:
	for a in B:
		Q.append(str(a))
	B=[]

	while Q:
		s = Q.popleft()
		
		a = int(s[0])
		
		x = (str(a-1) + s) if a>0 else ""
		y = (str(a) + s)
		z = (str(a+1) + s) if a<9 else ""
		
		if x!="": B.append(x)
		if y!="": B.append(y)
		if z!="": B.append(z)

	B.sort()
	for b in B:
		if b[0]=="0": continue
		A.append(int(b))

	if len(A)>K:
		ans = A[K]
		print(ans)
		
		
		exit(0)

Solution (Python):
def main():
    k=int(input())
    l=[[] for _ in range(20)]
    l[1]=[0,1,2,3,4,5,6,7,8,9]
    cnt=9
    if cnt>=k:
        print(l[1][k])
        exit()
    for i in range(2,20):
        for keta in range(1,i):
            for j in l[keta]:
                f=j//10**(i-2)
                if j==0:
                    l[i].append(10**(i-1)+j)
                if f==0:
                    if j//10**(len(str(j))-1)==1:
                        l[i].append(10**(i-1)+j)
                elif f==1:
                    l[i].append(10**(i-1)+j)
                    l[i].append(2*10**(i-1)+j)
                elif f==9:
                    l[i].append(8*10**(i-1)+j)
                    l[i].append(9*10**(i-1)+j)
                elif f>0:
                    l[i].append((f-1)*10**(i-1)+j)
                    l[i].append(f*10**(i-1)+j)
                    l[i].append((f+1)*10**(i-1)+j)
        if cnt+len(l[i])>=k:
            l[i].sort()
            ans=l[i][k-cnt-1]
            if ans==0:
                print(10**(i-1))
            else:
                print(ans)
            exit()
        else:
            cnt+=len(l[i])

if __name__ == '__main__':
    main()

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

ans = list(range(1, 10))
next_ans = ans

while len(ans)<k:
  temp_ans = []
  
  for a in next_ans:
    a_0 = int(str(a)[-1])
    new_ans = [int(str(a)+str(a_0+i)) for i in [-1,0,1] if 0<=a_0+i<=9]
    temp_ans.extend(new_ans)
  
  ans.extend(temp_ans)
  next_ans = temp_ans
  
  
print(ans[k-1])

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


cnt = 9
while True:
    a_tmp = []
    for s in a:
        for t in range(max(0, int(str(s[-1])) - 1), min(9, int(str(s[-1])) + 1) + 1):
            a_tmp.append(s+str(t))
            cnt += 1
            if cnt == K:
                print(s+str(t))
                exit()
    a = a_tmp

Solution (Python):
k = int(input())
ans = 0
a = ["0","1","2","3","4","5","6","7","8","9"]
old = ["0","1","2","3","4","5","6","7","8","9"]
b = []
l = 0
while l <= 9:
	b = []
	for i in range(10):
		x = str(i)
		for j in old:
			if abs(i- int(j[0])) <= 1:
				y = x + j
				b.append(y)
	a.extend(b)
	old = b.copy()
	l += 1
c = set()
for i in a:
	c.add(int(i))
d = list(c)
d.sort()
print (d[k])

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

lunlun = []
for i in range(10):
    lunlun.append([0, i])

count, itr = 9, 1
while count < K:
    if lunlun[itr][1] == 0:
        lunlun.append([itr, 0])
        lunlun.append([itr, 1])
        count += 2
    elif lunlun[itr][1] == 9:
        lunlun.append([itr, 8])
        lunlun.append([itr, 9])
        count += 2
    else:
        lunlun.append([itr, lunlun[itr][1] - 1])
        lunlun.append([itr, lunlun[itr][1]])
        lunlun.append([itr, lunlun[itr][1] + 1])
        count += 3
    itr += 1

ans = ""
itr = K
while True:
    ans = str(lunlun[itr][1]) + ans
    if lunlun[itr][0] != 0:
        itr = lunlun[itr][0]
    else:
        break

print(ans)

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

F = {}
for i in range(10):
    F[(1, i)] = 1


def f(n, d):
    if (n, d) in F:
        return F[(n, d)]
    nf = 0
    for i in [d - 1, d, d + 1]:
        if 0 <= i <= 9:
            nf += f(n - 1, i)
    F[(n, d)] = nf
    return nf


k = 0
p = (1, 0)
for i in range(1, 11):
    for j in range(1, 10):
        fij = f(i, j)
        if k + fij >= K:
            p = (i, j)
            break
        k += fij
        p = (i, j)
    else:
        continue
    break


def g(n, d, index):
    if n == 1:
        return str(d)
    total = 0
    for i in [d - 1, d, d + 1]:
        if not 0 <= i <= 9:
            continue
        if total + f(n - 1, i) >= index:
            break
        total += f(n - 1, i)
    return str(d) + g(n - 1, i, index - total)


print(g(p[0], p[1], K - k))

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque

def main():

    K = int(input())

    ans = []

    queue = deque(['1','2','3','4','5', '6', '7', '8', '9'])

    visited = set()
    for i in range(9):
        visited.add(queue[i])

    for i in range(K):

        current = queue.popleft()
        ans.append(int(current))
        digit_tail = int(current[-1])


        digit_tail_1 = str(digit_tail - 1)
        digit_tail_2 = str(digit_tail)
        digit_tail_3 = str(digit_tail + 1)

        if int(digit_tail_1) != -1 and current+digit_tail_1 not in visited:

            queue.append(current+digit_tail_1)
            visited.add(current+digit_tail_1)

        if current+digit_tail_2 not in visited:
            queue.append(current+digit_tail_2)
            visited.add(current+digit_tail_2)

        if int(digit_tail_3) != 10 and current+digit_tail_3 not in visited:
            queue.append(current+digit_tail_3)
            visited.add(current+digit_tail_3)

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

if __name__ == "__main__":
    main()

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

def listappend(list, length):
    templist = [i for i in list if i >= 10 ** (length - 1)]
    for x in templist:
        if x % 10 != 0: list.append(x * 10 + x % 10 - 1)
        list.append(x * 10 + x % 10)
        if x % 10 != 9 : list.append(x * 10 + x % 10 + 1)
    return list

list = [i + 1 for i in range(9)]
numList = [i + 1 for i in range(9)]
for x in numList:
    list.append(x * 10 + x - 1)
    list.append(x * 10 + x)
    if x != 9 : list.append(x * 10 + x + 1)
for x in range(11):
    if x == 0 or x == 1: continue
    list = listappend(list, x)
list.sort()
print(list[k - 1])

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

ans = [[] for _ in range(10)]
ans[0] = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]

for i in range(9):
    for num in ans[i]:
        if num[-1] == "0":
            ans[i + 1].append(num + "0")
            ans[i + 1].append(num + "1")
        elif num[-1] == "1":
            ans[i + 1].append(num + "0")
            ans[i + 1].append(num + "1")
            ans[i + 1].append(num + "2")
        elif num[-1] == "2":
            ans[i + 1].append(num + "1")
            ans[i + 1].append(num + "2")
            ans[i + 1].append(num + "3")
        elif num[-1] == "3":
            ans[i + 1].append(num + "2")
            ans[i + 1].append(num + "3")
            ans[i + 1].append(num + "4")
        elif num[-1] == "4":
            ans[i + 1].append(num + "3")
            ans[i + 1].append(num + "4")
            ans[i + 1].append(num + "5")
        elif num[-1] == "5":
            ans[i + 1].append(num + "4")
            ans[i + 1].append(num + "5")
            ans[i + 1].append(num + "6")
        elif num[-1] == "6":
            ans[i + 1].append(num + "5")
            ans[i + 1].append(num + "6")
            ans[i + 1].append(num + "7")
        elif num[-1] == "7":
            ans[i + 1].append(num + "6")
            ans[i + 1].append(num + "7")
            ans[i + 1].append(num + "8")
        elif num[-1] == "8":
            ans[i + 1].append(num + "7")
            ans[i + 1].append(num + "8")
            ans[i + 1].append(num + "9")
        elif num[-1] == "9":
            ans[i + 1].append(num + "8")
            ans[i + 1].append(num + "9")

for j in range(10):
    l = len(ans[j])
    if k <= l:
        print(ans[j][k - 1])
        break
    elif k > l:
        k -= l

Solution (Python):
import heapq
K=int(input())
if K<10:
  print(K)
  exit()
  
nums=[1, 2, 3, 4, 5, 6, 7, 8, 9]
heapq.heapify(nums)
for i in range(K):
  value=heapq.heappop(nums)
  tmp=str(value)
  if tmp[-1]=='0':
    cand=[int(tmp+'0'), int(tmp+'1')]
  elif tmp[-1]=='9':
    cand=[int(tmp+'8'), int(tmp+'9')]
  else:
    h=int(tmp[-1])
    cand=[int(tmp+str(h-1)), int(tmp+str(h)), int(tmp+str(h+1))]
  for c in cand:
    heapq.heappush(nums, c)
print(value)

Solution (Python):
from collections import deque

d = deque([(0, i) for i in range(1, 10)])
K = int(input())
cnt = 0

while len(d) > 0:
    s, i = d.popleft()
    

    cnt += 1
    ns = 10*s + i
    
    if cnt == K:
        print(10*s + i)
        break

    l = max(0, i-1)
    r = min(10, i+2)
    for i in range(l, r):
        d.append((ns, i))

Solution (Python):
def is_ll(n):
    cur = n % 10
    while n > 10:
        n //= 10
        if abs(n % 10 - cur) > 1:
            return False
        cur = n % 10
    return True

def find_next_ll(n):
    o = n
    cur = n % 10
    while n > 10:
        n //= 10
        if -1 < n % 10 - cur < 2 and cur != 9:
            n *= 10
            n += cur
            break
        cur = n % 10
    n += 1
    while n < o:
        cur = n % 10
        n *= 10
        n += max(0, cur - 1)
    return n

K = int(input())

ll = 1
for i in range(1, K):
    n = ll + 1
    if not is_ll(n):
        ll = find_next_ll(ll)
    else:
        ll = n
print(ll)

Solution (Python):
import copy
k=int(input())
l=[1,2,3,4,5,6,7,8,9]
h=1
s=0
s1=0
A=[]
C=[1]
D=[]
while len(l)<k:
    s1=len(l)
    for i in range(0,len(A)):
        l.append(A[i]+10**h)
        D.append(A[i]+10**h)
    A.extend(C)
    C=copy.deepcopy(D)
    D=[]
    for i in range(s,s1):
        j=str(l[i])
        an=int(j[0])
        if an==1:
            l.append((10**h)+l[i])
            l.append(2*(10**h)+l[i])
            C.append((10**h)+l[i])
        elif an==9:
            l.append(9*(10**h)+l[i])
            l.append(8*(10**h)+l[i])
        elif an==2:
            l.append((10**h)+l[i])
            l.append((2)*(10**h)+l[i])
            l.append((3)*(10**h)+l[i])
            C.append((10**h)+l[i])
        else:
            l.append(an*(10**h)+l[i])
            l.append((an+1)*(10**h)+l[i])
            l.append((an-1)*(10**h)+l[i])
    l.append(10**h)
    C.append(10**h)
    h=h+1
    s=s1
B=l[s:]
B.sort()
print(B[k-s-1])