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):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    k = II()
    d = defaultdict(list)
    d[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    i = 0
    l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    while len(l) < k:
        tmp = d[i]
        tt = []
        for t in tmp:
            st = str(t)
            for i in range(-1, 2):
                x = int(st[-1]) + i
                if 10 > x >= 0:
                    ss = st + str(x)
                    tt.append(int(ss))
        i += 1
        d[i] = tt
        for ttt in tt:
            l.append(ttt)
    l.sort()
    print(l[k - 1])
    return



if __name__ == '__main__':
    solve()

Solution (Python):


import sys

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

def is_luun(i):
    last_digit = i % 10
    i //= 10
    while i > 0:
        if abs((i % 10) - last_digit) > 1:
            return False
        last_digit = i % 10
        i //= 10
    return True

next_luun_memo = {}

def next_luun(n):
    if n in next_luun_memo:
        dprint("memoed: %d -> %d" % (n, next_luun_memo[n]))
        return next_luun_memo[n]
    if n < 10:
        dprint("here")
        next_luun_memo[n] = n + 1
        return n + 1
    first = n % 10
    tenth = (n // 10) % 10
    if first < 9 and abs(first + 1 - tenth) <= 1:
        next_luun_memo[n] = n + 1
        return n + 1

    ans_tenth = next_luun(n // 10)
    dprint("ans_tenth: %d" % ans_tenth)
    ans_first = min(abs(ans_tenth % 10 - 1), ans_tenth % 10)
    dprint("ans_first: %d" % ans_first)
    ans = ans_tenth * 10 + ans_first
    next_luun_memo[n] = ans
    return ans


def main():
    k = read(int)

    i = 1
    luun = 1
    while i < k:
        dprint("%dth luun: %d" % (i, luun))
        luun = next_luun(luun)
        i += 1
    dprint("%dth luun: %d" % (i, luun))
    print(luun)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

if __name__ == "__main__":
    K = int(input())
    runruns = []

    queue = deque()
    for i in range(1, 10):
        queue.appendleft(str(i))
        runruns.append(str(i))

    while len(runruns) < K:
        cur = queue.pop()
        for diff in [-1, 0, 1]:
            right = cur[-1]
            if (right == '0' and diff == -1) or (right == '9' and diff == 1):
                continue
            next_right = str(int(right) + diff)
            next_cur = cur + next_right
            runruns.append(next_cur)
            queue.appendleft(next_cur)

    runruns = list(map(int, runruns))
    
    
    print(runruns[K-1])

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

ans = []


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

while len(ans) <= 110000:
    n = []
    cnt = 0
    for x in l:
        y = x * 10
        b = x % 10
        if b == 0:
            n.append(y)
            n.append(y+1)
        elif b == 9:
            n.append(y+b-1)
            n.append(y+b)
        else:
            n.append(y+b-1)
            n.append(y+b)
            n.append(y+b+1)
    l = n[:]
    ans.extend(l)

print(ans[k-1])

Solution (Python):

"""
Created on Sat Apr  4 20:49:45 2020

@author: naoki
"""

K = int(input())

count = K
for keta_num in range(1,100):
    op = list(map(str,[i for i in range(1,10)]))
    for keta in range(1,keta_num):
        op = [j + i for j in op for i in [str(int(j[-1])-1),str(int(j[-1])),str(int(j[-1])+1)]  \
                         if int(i) >= 0 and int(i) <=9]
    if count > len(op):
        count -= len(op)
    else:
        print(int(op[count-1]))
        break

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    k=int(input())
    dp=[[0]*10 for _ in range(1000)]
    for i in range(10):
        dp[0][i]=1
    for i in range(999):
        dp[i+1][0]=dp[i][0]+dp[i][1]
        for j in range(1,9):
            dp[i+1][j]=dp[i][j-1]+dp[i][j]+dp[i][j+1]
        dp[i+1][9]=dp[i][8]+dp[i][9]
    flag=0
    for i in range(1000):
        for j in range(1,10):
            if k>dp[i][j]:
                k-=dp[i][j]
            else:
                flag=1
                break
        if flag==1:
            break
    ans=j*10**i
    while i>0:
        if j!=0:
            if k>dp[i-1][j-1]:
                k-=dp[i-1][j-1]
            else:
                i-=1
                ans+=(j-1)*10**i
                j-=1
                continue
        if k>dp[i-1][j]:
            k-=dp[i-1][j]
        else:
            i-=1
            ans+=j*10**i
            continue
        if j!=9:
            if k>dp[i-1][j+1]:
                k-=dp[i-1][j+1]
            else:
                i-=1
                ans+=(j+1)*10**i
                j+=1
                continue 
    print(ans)
if __name__ == '__main__':
    main()

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

Solution (Python):
import sys

K = int(input())

if K < 10:
    print(K)
    sys.exit(0)

runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 9
while True:
    new_runrun = []
    for run in runrun:
        run_str = str(run)
        last_num = int(run_str[-1])
        for i in range(3):
            diff = i - 1
            if (last_num == 9 and diff == 1) or (last_num == 0 and diff == -1):
                continue
            ans = int(run_str + str(last_num + diff))
            new_runrun.append(ans)
            count += 1
            if count == K:
                print(ans)
                sys.exit(0)
    runrun = new_runrun

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

X = [0] * 20
l = 0

for _ in range(K):
  for i in range(l + 2):
    if X[i] < 9 and (i >= l or X[i] < X[i + 1] + 1):
      if i > l:
        l = i
      X[i] += 1
      for j in range(i - 1, -1, -1):
        X[j] = max(X[j + 1] - 1, 0)
      break

print(''.join(str(x) for x in X[l::-1]))

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

for i in l:
    p=str(i)
    if 0<=int(p[-1])-1<10:
        l.append(int(str(i)+str(int(p[-1])-1)))
    l.append(int(str(i)+p[-1]))
    if 0<=int(p[-1])+1<10:
        l.append(int(str(i)+str(int(p[-1])+1)))
    if len(l)>10**5:
        break
print(l[k-1])

Solution (Python):
import sys
from collections import deque

def solve():
      input = sys.stdin.readline
      K = int(input())
      low, high = 0, 3234566668
      while high - low > 1:
            mid = (low + high) // 2
            midS = str(mid)
            lenS = len(midS)
            q = deque()
            for j in range(lenS):
                  for i in range(1, 10): q.append((i, i, j + 1))
            count = 0
            isRunrun = False
            while q:
                  ns, last, length = q.pop()
                  if length == lenS:
                        if ns <= mid: count += 1
                        if ns == mid: isRunrun = True
                  else:
                        if last == 0: 
                              q.append((ns*10 + 1, 1, length + 1))
                              q.append((ns*10 + 0, 0, length + 1))
                        elif last == 9: 
                              q.append((ns*10 + 8, 8, length + 1))
                              q.append((ns*10 + 9, 9, length + 1))
                        else:
                              q.append((ns*10 + last+1, last + 1, length + 1))
                              q.append((ns*10 + last-1, last - 1, length + 1))
                              q.append((ns*10 + last, last, length + 1))
            if count > K: high = mid
            elif count == K:
                  if isRunrun: low = mid
                  else: high = mid
            else: low = mid
            
      print(low)
            
      return 0

if __name__ == "__main__":
      solve()

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


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


def Get(i):
    ans[i] = []
    for v in ans[i - 1]:
        if v[-1] == '0':
            ans[i].append(v + '0')
            ans[i].append(v + '1')
        elif v[-1] == '9':
            ans[i].append(v + '8')
            ans[i].append(v + '9')
        else:
            t = v[-1]
            ans[i].append(v + str(int(t) - 1))
            ans[i].append(v + str(int(t)))
            ans[i].append(v + str(int(t) + 1))


def GetValueIndex(K):
    i = 1
    while True:
        if len(ans[i]) < K:
            K -= len(ans[i])
            i += 1
        else:
            ans[i].sort()
            return ans[i][K - 1]


K = int(input())

ans = {1: [str(i) for i in range(1, 10)]}
i = 2
while sum(len(v) for v in ans.values()) < K:
    Get(i)
    i += 1

print(GetValueIndex(K))

Solution (Python):
k = int(input())
c = 0
ans = [[]]
ans[0] = [1,2,3,4,5,6,7,8,9]
for i in range(1,10):
  s = []
  for j in range(10):
    for a in ans[i-1]:
      if j == a%10 or j-1 == a%10 or j+1 == a%10:
        s.append(int(str(a)+str(j)))
  ans.append(s)
        
ans = list(sum(ans,[]))
ans.sort()
print(ans[k-1])

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
count = 0


def solve(K: int):

    def cDfs(prev, prevDigit, remainDigit):
        global count
        if remainDigit == 0:
            count += 1
            if count == K:
                print(prev)
                exit()
            
            return
        else:
            if prevDigit == 0:
                cDfs(prev*10, prevDigit, remainDigit-1)
                cDfs(prev*10+1, 1, remainDigit-1)
            elif prevDigit == 9:
                cDfs(prev*10+8, 8, remainDigit-1)
                cDfs(prev*10+9, prevDigit, remainDigit-1)
            else:
                a = (prevDigit+1) % 10
                b = (prevDigit-1) % 10
                MIN = min(a, b)
                MAX = max(a, b)
                cDfs(prev*10+MIN, MIN, remainDigit-1)
                cDfs(prev*10+prevDigit, prevDigit, remainDigit-1)
                cDfs(prev*10+MAX, MAX, remainDigit-1)
    for i in range(0, 100):
        for j in range(1, 10):
            cDfs(j, j, i)
    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):
K = int(input())
t = {}
cnt = 0

for ie in range(10):
    ne = ie
    for id in range(10):
        nd = ne*10+id
        if abs(ie-id)>1 and ne!=0:
            continue
        for ic in range(10):
            nc = nd*10+ic
            if abs(id-ic)>1 and nd!=0:
                continue
            for ib in range(10):
                nb = nc*10+ib
                if abs(ic-ib)>1 and nc!=0:
                    continue
                for ia in range(10):
                    na = nb*10+ia
                    if abs(ib-ia)>1 and nb!=0:
                        continue
                    for i1 in range(10):
                        n1 = na*10+i1
                        if abs(ia-i1)>1 and na!=0:
                            continue
                        for i2 in range(10):
                            n2 = n1*10+i2
                            if abs(i1-i2)>1 and n1!=0:
                                continue
                            for i3 in range(10):
                                n3 = n2*10+i3
                                if abs(i2-i3)>1 and n2!=0:
                                    continue
                                for i4 in range(10):
                                    n4 = n3*10+i4
                                    if abs(i3-i4)>1 and n3!=0:
                                        continue
                                    for i5 in range(10):
                                        n5 = n4*10+i5
                                        if abs(i4-i5)>1 and n4!=0:
                                            
                                            continue
                                        if n5 ==0:
                                            
                                            continue
                                        cnt += 1
                                        
                                        if cnt==K:
                                            print(n5)
                                            exit()

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

if K < 10:
    print(K)
    exit()
cnt = 9
number_list = [str(i) for i in range(1, 10)]

while True:
    new_number_list = []
    for number in number_list:
        if number[-1] == '0':
            new_number_list.append(number + '0')
            new_number_list.append(number + '1')
        elif number[-1] == '1':
            new_number_list.append(number + '0')
            new_number_list.append(number + '1')
            new_number_list.append(number + '2')
        elif number[-1] == '2':
            new_number_list.append(number + '1')
            new_number_list.append(number + '2')
            new_number_list.append(number + '3')
        elif number[-1] == '3':
            new_number_list.append(number + '2')
            new_number_list.append(number + '3')
            new_number_list.append(number + '4')
        elif number[-1] == '4':
            new_number_list.append(number + '3')
            new_number_list.append(number + '4')
            new_number_list.append(number + '5')
        elif number[-1] == '5':
            new_number_list.append(number + '4')
            new_number_list.append(number + '5')
            new_number_list.append(number + '6')
        elif number[-1] == '6':
            new_number_list.append(number + '5')
            new_number_list.append(number + '6')
            new_number_list.append(number + '7')
        elif number[-1] == '7':
            new_number_list.append(number + '6')
            new_number_list.append(number + '7')
            new_number_list.append(number + '8')
        elif number[-1] == '8':
            new_number_list.append(number + '7')
            new_number_list.append(number + '8')
            new_number_list.append(number + '9')
        elif number[-1] == '9':
            new_number_list.append(number + '8')
            new_number_list.append(number + '9')
    cnt += len(new_number_list)
    if cnt >= K:
        print(new_number_list[-(cnt-K+1)])
        exit()
    number_list = new_number_list

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

def dfs(now, d, L):
    if d==L:
        return 1
    
    res = 0
    
    for nex in range(max(0, now-1), min(9, now+1)+1):
        res += dfs(nex, d+1, L)
    
    return res

K = int(input())

for i in range(1, 100):
    r = 0
    
    for j in range(1, 10):
        r += dfs(j, 1, i)
    
    if K-r>0:
        K -= r
    else:
        k = i
        break

def dfs2(l, d, k):
    global K
    
    if d==k:
        K -= 1

        if K==0:
            l = list(map(str, l))
            print(''.join(l))
            exit()
        
        return
    
    now = l[-1]
    
    for nex in range(max(0, now-1), min(9, now+1)+1):
        l.append(nex)
        dfs2(l, d+1, k)
        l.pop()

for i in range(1, 10):
    dfs2(deque([i]), 1, k)

Solution (Python):
def gen_lunlun(digit, li):
    if len(li) == digit:
        lunluns.append(''.join(map(str, li)))
        return
    min_num = max(0, li[-1] - 1)
    max_num = min(9, li[-1] + 1)
    for i in range(min_num, max_num + 1):
        gen_lunlun(digit, li + [i])


k = int(input())

lunluns = []
for d in range(1, 11):
    for i in range(1, 10):
        gen_lunlun(d, [i])
print(lunluns[k - 1])

Solution (Python):
import sys
k = int(input())
klist=list(map(str, [1,2,3,4,5,6,7,8,9]))
dic = {'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']}
if k <= 9:
    print(klist[k-1])
    sys.exit()
else:
    count = 0
    ok = 9
    while 1:
        tmp = klist[count]
        for add in dic[tmp[-1]]:
            klist.append(''.join([tmp, add]))
            ok+=1
            if ok == k:
                print(''.join([tmp, add]))
                sys.exit()
        count+=1

Solution (Python):
from collections import defaultdict as dd
import sys
k = int(input())

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

matsubi_dic = dd(lambda: [])
for i in range(0, 10):
  nums = [i-1, i, i+1]
  matsubi_dic[i] = [num for num in nums if num >= 0 and num <= 9]

  

runrun = dd(list)
counter = 0
for keta in range(1, 100000000000):
  if keta == 1:
    runrun[keta] = list(range(1, 10))
    counter += 9
    
  else:
    for num in runrun[keta - 1]:
      matsubi = int(str(num)[keta-2])
      for new_matsubi in matsubi_dic[matsubi]:
        runrun[keta].append(int(str(num) + str(new_matsubi)))
        counter += 1
        if counter == k:
          print(int(str(num) + str(new_matsubi)))
          sys.exit()

Solution (Python):

a = int(input())
from collections import deque
stack_deque = deque([])


if a <= 9:
    print(a)
    from sys import exit
    exit()
else:
    base = [1,2,3,4,5,6,7,8,9]
    cnt = 9
    while cnt<a:
        nb = deque([])
        for i in base:
            first_v = i%10
            v = i*10
            if first_v==0:
                nb.append(v)
                cnt+=1
                if cnt==a:
                    break
                else:
                    nb.append(v+1)
                    cnt+=1
            elif first_v==9:
                nb.append(v+8)
                cnt+=1
                if cnt==a:
                    break
                else:
                    nb.append(v+9)
                    cnt+=1
            else:
                for j in [first_v-1,first_v,first_v+1]:
                    nb.append(v+j)
                    cnt+=1
                    if cnt==a:
                        break
                if cnt==a:
                    break
        base = nb
print(nb[-1])

Solution (Python):
from collections import deque
l = [i for i in range(1,10)]
deque = deque(l)
cnt = 9

def lunlun(i):
    s =str(i)
    s_last=int(s[-1])
    if s_last == 0:
        s1 = s + str(s_last)
        s2 = s + str(s_last + 1)
        return int(s1),int(s2)
    elif s_last == 9:
        s0 = s + str(s_last - 1)
        s1 = s + str(s_last)
        return int(s0),int(s1)
    else:
        s0 = s + str(s_last - 1)
        s1 = s + str(s_last)
        s2 = s + str(s_last + 1)
        return int(s0),int(s1),int(s2)

while cnt <= 10**5:
    num = deque.popleft()
    t = list(lunlun(num))
    cnt += len(t)
    l.extend(t)
    deque.extend(t)

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

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

run=deque()

def rec(n,cnt):
    if cnt>10:return
    run.append(int(n))
    if n[-1]!="0":
        rec(n+str(int(n[-1])-1),cnt+1)
    if n[-1]!="9":
        rec(n+str(int(n[-1])+1),cnt+1)
    rec(n+n[-1],cnt+1)
k=int(input())
for i in range(1,10):
    rec(str(i),1)
a=sorted(run)
print(a[k-1])

Solution (Python):
from collections import deque

def get_lunlun(i):
    ret = [i]
    if i  > 0:
        ret.append(i-1)
    if i < 9:
        ret.append(i+1)
    return sorted(ret)

def main():
    n = int(input())
    cand = deque()
    adj = {i: get_lunlun(i) for i in range(0,10)}
    for i in range(1, 10):
        cand.append(i)
    for _ in range(n):
        pos = cand.popleft()
        for cnd in adj[pos%10]:
            cand.append(pos*10+cnd)
    print(pos)

if __name__ == '__main__':
    main()

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



ans = ""
cumsum = 0
brflag = False
for i in range(11):
    for j in range(1,10):
        cumsum += dp[i][j]
        if cumsum >= k:
            ans += str(j)
            k -= cumsum - dp[i][j]
            brflag = True
            break
    if brflag == True:
        brflag = False
        break
        
while i > 0:
    
    i -= 1
    cumsum = 0
    psfl = False
    if j > 0:
        cumsum += dp[i][j-1]
        if cumsum >= k:
            ans += str(j-1)
            k -= cumsum - dp[i][j-1]
            j = j - 1
            
            psfl = True
    if not psfl:
        cumsum += dp[i][j]
        if cumsum >= k:
            ans += str(j)
            k -= cumsum - dp[i][j]
            psfl = True
            
    if (not psfl) and j < 9:
        cumsum += dp[i][j+1]
        if cumsum >= k:
            ans += str(j+1)
            k -= cumsum - dp[i][j+1]
            j = j + 1
            psfl = True    
            
print(ans)

Solution (Python):
K = int(input())
s = '0'
cnt = 0
while cnt<K:
  cnt += 1
  ns = ''
  j = -1
  for i in range(len(s)-1,0,-1):
    if int(s[i])+1<=int(s[i-1])+1 and int(s[i])+1<10:
      j = i
      break
  else:
    if s[0]<'9':
      j = 0
  if j!=-1:
    m = int(s[j])
    for i in range(len(s)):
      if i==j:
        x = str(int(s[i])+1)
      elif i<j:
        x = s[i]
      elif i==j+1:
        x = str(m)
      else:
        x = str(max(m-1,0))
        m = max(m-1,0)
      ns += x
  else:
    ns = '1'+'0'*len(s)
  s = ns

print(s)

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


if k<10:
    print(k)

else:
    q=[str(i+1) for i in range(9)]
    ans=9
    for i in range(20):
        nq = []
        for j in range(len(q)):
            if q[j][-1]=='0'or q[j][-1]== '9':
                if q[j][-1]=='0':
                    nq.append(q[j]+'0')
                    nq.append(q[j]+'1')
                else:
                    nq.append(q[j]+'8')
                    nq.append(q[j]+'9')

                ans+=2
                if ans>=k:
                    print(nq[-(ans-k+1)])
                    exit()
            else:
                nq.append(q[j] +str(int(q[j][-1])-1))
                nq.append(q[j] +str(int(q[j][-1])))
                nq.append(q[j]+ str(int(q[j][-1])+ 1))
                ans+=3
                if ans>=k:
                    print(nq[-(ans-k+1)])
                    exit()
        q=nq

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

S = list(range(1, 10))
A = S[:]

cnt = 0
while len(A) < K:
    T = []
    for s in S:
        q, r = divmod(s, 10)
        if r != 0:
            T.append(s * 10 + r - 1)
        T.append(s * 10 + r)
        if r != 9:
            T.append(s * 10 + r + 1)
    S = T
    A += T

print(A[K - 1])

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

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

def make_lunlun(digit, start):
    if digit == 1:
        return [start]
    res = []
    for start_neighbor in neighbor(start):
        b = make_lunlun(digit-1, start_neighbor)
        c = list(map(lambda x:x+(start*(10**(digit-1))), b))
        res.extend(c)
    return res
lunlun = []
for i in range(1,11):
    for j in range(1,10):
        lunlun.extend(make_lunlun(i, j))

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

Solution (Python):

import sys



K = int(input())

ans = []

def make(prev,scale,now):
    if scale == 0:
        ans.append("".join(now))
        return
    if prev > 0:
        n = list(now)
        n.append(str(prev-1))
        make(prev-1,scale-1,n)
    n = list(now)
    n.append(str(prev))
    make(prev,scale-1,n)
    if prev < 9:
        n = list(now)
        n.append(str(prev+1))
        make(prev+1,scale-1,n)
    
for i in range(10):
    for j in range(1,10):
        make(j,i,[str(j)])

print(ans[K-1])

Solution (Python):
k=int(input())
if k<=9:
    print(k)
    exit()
a=[1,2,3,4,5,6,7,8,9]
cnt=9
while True:
    q=[]
    for i in a:
       for j in range(10):
            if abs(int(str(i)[-1])-j)<=1:
                cnt+=1
                if cnt==k:
                    print(int(str(i)+str(j)))
                    exit()
                q.append(int(str(i)+str(j)))         
    a=list(sorted(set(q)))

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

ans = []
def add(t,d,v):
  if d == 0:
    ans.append(v)
  else:
    if t != 0:
      add(t-1, d-1, v+str(t-1))    
    add(t, d-1, v+str(t))
    if t != 9:
      add(t+1, d-1, v+str(t+1))
  
for d in range(10):
  for t in range(1,10):
    add(t,d,str(t))
  if len(set(ans)) > k:
    break

ans = [int(a) for a in ans]
ans = sorted(list(set(ans)))
print(ans[k-1])

Solution (Python):
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % mod) % mod
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    K = iRaw()
    if K <= 10:
        return K
    runrun = [1,0]
    leftK = K-10
    while leftK >0:
        leftK-=1
        lenRun = len(runrun)
        digit = lenRun -1
        while digit>0:
            if runrun[digit] <runrun[digit-1]:
                runrun[digit]+=1
                break
            if runrun[digit] == runrun[digit-1] and runrun[digit]!=9:
                runrun[digit]+=1
                break
            digit -=1
        
        if digit==0:
            if runrun[0] < 9:
                runrun[0]+=1
            else:
                runrun = [1]+([0]*lenRun)
                continue
        for idx in range(digit+1,lenRun):
            runrun[idx] = max(runrun[idx-1]-1,0)

    return "".join([str(r) for r in runrun])
    
if __name__ == "__main__":
    print(main())

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

def solve(K: int):
    first = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    heapq.heapify(first)
    res = 1
    while K > 0:
        res = heapq.heappop(first)
        if res % 10 != 0:
            heapq.heappush(first, res * 10 + res % 10 - 1)
        heapq.heappush(first, res * 10 + res % 10)
        if res % 10 != 9:
            heapq.heappush(first, res * 10 + res % 10 + 1)
        K -= 1
    return res


def main():
    K = int(input().rstrip())
    res = solve(K)
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):

K = int(input())

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

ll = [1,2,3,4,5,6,7,8,9]
aft_l = []
cnt = 9
while cnt < K:
    for l in ll:
        tmp = 10 * l
        last = l%10
        if last >= 1:
            aft_l.append(tmp+last-1)
            cnt += 1
            if cnt == K:
                print(aft_l[-1])
                exit()
        
        aft_l.append(tmp+last)
        cnt += 1
        if cnt == K:
            print(aft_l[-1])
            exit()
        if last <= 8:
            aft_l.append(tmp+last+1)
            cnt +=1
            if cnt == K:
                print(aft_l[-1])
                exit()
    ll = aft_l
    aft_l = []

Solution (Python):
k = int(input())
count = 9
from collections import deque
que = deque([1,2,3,4,5,6,7,8,9])
if k<10:
    print(k)
    exit()
while que:
    v = que.popleft()
    matu = v%10
    for i in range(10):
        if abs(matu-i)<=1:
            que.append(v*10+i)
            count +=1
            if count == k:
                print(que.pop())
                exit()

Solution (Python):
K = int(input())
lun = list(range(1, 10))
for n in range(K):
    lm = lun[n] % 10
    if lm > 0:
        lun.append(lun[n] * 10 + (lm - 1))
    lun.append(lun[n] * 10 + lm)
    if lm < 9:
        lun.append(lun[n] * 10 + (lm + 1))
print(lun[K-1])

Solution (Python):
K = int(input())
h = [0]*10
h[0] = {1,2,3,4,5,6,7,8,9}

def digit_lunlun(x):
    if x == 0:
        return h[0]
    G = digit_lunlun(x-1)
    a = set()
    for g in G:
        b = g%10
        for i in set([max(0,b-1),b,min(b+1,9)]):
            a.add(g*10+i)
    h[x] = a
    return a

digit_lunlun(9)
for i in range(10):
    le = len(h[i])
    if le < K:
        K -= le
    else:
        for g in sorted(h[i]):
            if K == 1:
                print(g)
                exit()
            else:
                K -= 1

Solution (Python):
def d1(x):
    y = x % 10
    if y == 0:
        return [0, 1]
    elif y == 9:
        return [8, 9]
    else:
        return [y-1, y, y+1]


K = int(input())

runrun = []
N = 0
digit = 0
while N < K:
    d_i = []
    if digit == 0:
        for i in range(1, 10):
            d_i.append(i)
        N += len(d_i)
        runrun.append(d_i)
        digit += 1
    else:
        tmp = runrun[digit-1]
        for x in tmp:
            for y in d1(x):
                d_i.append(10*x+y)
        N += len(d_i)
        runrun.append(d_i)
        digit += 1

print(runrun[-1][K-N-1])