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

Solution (Python):
k = int(input())
lun = [str(e) for e in list(range(10))]
num = [str(e) for e in list(range(10))]
preindex = 1
index = 10
count = 10
while count <= 100003:
    for i in range(preindex,index):
        if int(lun[i][-1]) !=0:
            lun.append(lun[i]+num[int(lun[i][-1])-1])
            count +=1
        lun.append(lun[i] +num[int(lun[i][-1])])
        count +=1
        if int(lun[i][-1]) !=9:
            lun.append(lun[i]+num[int(lun[i][-1])+1])
            count+=1
    preindex = index
    index = count
print(lun[k])

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


dp = [[1 for _ in range(10)]]
dp
s = [[sum(dp[0][1:i + 1]) for i in range(1, 10)]]
ends = s[0][8]

for j in range(10 * 5):
    dp.append([dp[j][0] + dp[j][1]] + [dp[j][i - 1] + dp[j][i] + dp[j][i + 1]
                                       for i in range(1, 9)] + [dp[j][8] + dp[j][9]])
    s.append([ends + sum(dp[j + 1][1:i + 1]) for i in range(1, 10)])
    ends = s[j + 1][8]
    if ends > 10**5:
        break


def search(jj, ii, m):
    if jj == 0:
        return ii
    else:
        if ii != 0:
            if m <= dp[jj - 1][ii - 1]:
                return (ii) * 10**jj + search(jj - 1, ii - 1, m)
            elif m <= dp[jj - 1][ii - 1] + dp[jj - 1][ii]:
                return (ii) * 10**jj + search(jj - 1, ii, m - dp[jj - 1][ii - 1])
            else:
                return (ii) * 10**jj + search(jj - 1, ii + 1, m - dp[jj - 1][ii - 1] - dp[jj - 1][ii])
        else:
            if m <=  dp[jj - 1][ii]:
                return (ii) * 10**jj + search(jj - 1, ii, m)
            else:
                return (ii) * 10**jj + search(jj - 1, ii + 1, m - dp[jj - 1][ii])


for j in range((len(s))):
    if s[j][8] >= K:
        jj = j
        break
for i in range(9):
    if s[jj][i] >= K:
        ii = i + 1
        if ii > 1:
            m = K - s[jj][i - 1]  
        else:
            m = K - s[jj - 1][8]
        break

print(search(jj, ii, m))

Solution (Python):
n=int(input())
now=[1,2,3,4,5,6,7,8,9]
if n<10:
  print(now[n-1])
  exit()
cnt=9
while True:
  next=[]
  for s in now:
    s=str(s)
    if s[-1]!="0":
      cnt+=1
      if cnt<n:
        next.append(s+str(int(s[-1])-1))
      else:
        print(s+str(int(s[-1])-1))
        exit()
    cnt+=1
    if cnt<n:
      next.append(s+s[-1])
    else:
      print(s+s[-1])
      exit()
    if s[-1]!="9":
      cnt+=1
      if cnt<n:
        next.append(s+str(int(s[-1])+1))
      else:
        print(s+str(int(s[-1])+1))
        exit()
  now=next

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

DP = [[0] * 10 for _ in range(11)]

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

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

total = 0

ans = []




def dfs(j, k):
    global ans
    global total
    if j == 0:
        print(int("".join(ans)))
        sys.exit(0)

    if k == 0:
        kList = [0, 1]
    elif k == 9:
        kList = [8, 9]
    else:
        kList = [k-1, k, k+1]

    for i in kList:
        if total + DP[j][i] >= K:
            ans.append(str(i))
            dfs(j-1, i)
        else:
            total += DP[j][i]


for j in range(1, 11):
    for i in range(1, 10):
        if total + DP[j][i] >= K:
            ans.append(str(i))
            dfs(j-1, i)
        else:
            total += DP[j][i]

Solution (Python):
n=int(input())
ans=[]
def dfs(num,step,tmp):
    if len(ans)>1e5:
        return
    if num==step:
        ans.append(tmp)
        return
    if step==0:
        for i in range(1,10):
            dfs(num,step+1,tmp*10+i)
    else:
        if tmp%10!=0:
            dfs(num,step+1,tmp*10+tmp%10-1)
        dfs(num,step+1,tmp*10+tmp%10)
        if tmp%10!=9:
            dfs(num,step+1,tmp*10+tmp%10+1)
for i in range(11):
    dfs(i+1,0,0)
print(ans[n-1])

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

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

if k <= 12 :
    print(k)
else :
    for i in range(10) :
        b = []
        for s in a[i] :
            if s[-1] == '0' :
                b.append(s+'0')
                b.append(s+'1')
            elif s[-1] == '9' :
                b.append(s+'8')
                b.append(s+'9')
            else :
                b.append(s+str(int(s[-1])-1))
                b.append(s+str(int(s[-1])))
                b.append(s+str(int(s[-1])+1))

            if c + len(b) > k :
                print(b[k-c-len(b)-1])
                break
    
        if c + len(b) > k :
            break
    
        a.append(b)
        c += len(b)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    k = int(input())
    d = deque([0])

    while 1:
        a = d.popleft()
        if a==0:
            for i in range(1, 10):
                d.append(i)
                k -= 1
                if k==0:
                    print(i)
                    exit()
        else:
            b = a%10
            if b==0:
                d.append(a*10+b)
                k -= 1
                if k == 0:
                    print(a*10+b)
                    exit()
                d.append(a*10+(b+1))
                k -= 1
                if k == 0:
                    print(a*10+(b+1))
                    exit()
            elif b==9:
                d.append(a*10+(b-1))
                k -= 1
                if k == 0:
                    print(a*10+(b-1))
                    exit()
                d.append(a*10+b)
                k -= 1
                if k == 0:
                    print(a*10+b)
                    exit()
            else:
                d.append(a*10+(b-1))
                k -= 1
                if k == 0:
                    print(a*10+(b-1))
                    exit()
                d.append(a*10+b)
                k -= 1
                if k == 0:
                    print(a*10+b)
                    exit()
                d.append(a*10+(b+1))
                k -= 1
                if k == 0:
                    print(a*10+(b+1))
                    exit()


if __name__ == '__main__':
    main()

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

ans = 9

def countup(before):
  global ans
  global K
  next_arr = []
  for s in before:
    for diff in range(-1, 2):
      next_num = int(s[-1]) + diff
      if(0 <= next_num and next_num <= 9):
        next_arr.append(s + str(next_num))
        ans += 1
        if(ans == K):
          print(s + str(next_num))
          exit()
  return next_arr


if(K < 10):
  print(K)
  exit()
hoge = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
for _ in range(100):
  hoge = countup(hoge)

Solution (Python):
import copy
n = int(input())
ans = [1,2,3,4,5,6,7,8,9]
stock = ["1","2","3","4","5","6","7","8","9"]
stock2 = []
a = 2
def d(x):
    if x == 0:
        return(["0","1"])
    elif x == 9:
        return(["8","9"])
    else:
        return([str(x-1),str(x),str(x+1)])
if n > 9:
    while True:
        if len(ans) > n-1:
            print(ans[n-1])
            break
        for i in stock:
            s = ""
            x = d(int(i[-1]))
            
            for j in x:
                s = i+j
                ans.append(int(float(s)))
                stock2.append(s)
        stock = copy.deepcopy(stock2)
        stock2 = []
else:
    print(ans[n-1])

Solution (Python):
k = int(input())
a = [100]*15
a[0] = 1


def runrun_generater(x):
    for i in range(14):
        if(x[i]+1 - x[i+1] < 2 and (x[i] < 9 or x[i] == 100)):
            if(x[i] == 100):
                x[i] = 1
                if(i != 0):
                    x[:i] = [0]*i
            else:
                x[i] += 1
                if(i != 0):
                    k = i
                    for xx in range(i):
                        if(x[k] == 0):
                            x[k-1] = 0
                        else:
                            x[k-1] = x[k]-1
                        k -= 1
            return x


for i in range(k-1):
    a = runrun_generater(a)
ans = 0
keta = 1
for y in a:
    if(y != 100):
        ans += y * keta
        keta *= 10
print(ans)

Solution (Python):
K = int(input())
def runrun(num,keta):
    num_str = str(num)
    result = True
    for i in range(keta-1):
        if abs(int(num_str[i]) - int(num_str[i+1])) > 1:
            result = False
            break
    return result
def next_runrun(n):
    if str(n) == "9"*(len(str(n))):
        return n+1
    keta = len(str(n))
    while keta >= 0:
        tmp = n + 10**(len(str(n))-keta)
        if runrun(tmp,keta):
            break
        else:
            keta -= 1
    tmp_str = str(tmp)[0:keta] + "x"*(len(str(n))-keta)
    tmp_array = []
    for t in tmp_str:
        tmp_array.append(t)
    for i in range(len(tmp_array)-1):
        if tmp_array[i+1] == "x":
            j = int(tmp_array[i]) - 1
            j = j if j >= 0 else 0
            tmp_array[i+1] = str(j)
    
    return int(''.join(tmp_array))
cnt = 1
n = 1
while True:
    if cnt == K:
        break
    else:
        n = next_runrun(n)
        cnt += 1
print(n)

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

alllist=[0,1,2,3,4,5,6,7,8,9]
maelist=[0,1,2,3,4,5,6,7,8,9]
tobilist=[]

for i in range(9):
    atolist=[]
    for j in maelist:
        sentou = j // (10**(i))
        jousuu = 10**(i+1)
        if sentou == 1:
            atolist.append(1 * jousuu + j)
            atolist.append(2 * jousuu + j)
            tobilist.append(j)
        elif sentou == 9:
            atolist.append(8*jousuu+j)
            atolist.append(9*jousuu+j)
        elif sentou == 0:
            atolist.append(jousuu + j)
            tobilist.append(j)
        else:
            atolist.append((sentou - 1)*jousuu+j)
            atolist.append(sentou*jousuu+j)
            atolist.append((sentou + 1)*jousuu+j)

    alllist.extend(atolist)
    maelist=[]
    for l in atolist:
        maelist.append(l)
    maelist.extend(tobilist)

kusolist=list(set(alllist))
kusolist.sort()
print(kusolist[k])

Solution (Python):







def rec(x, digit, K):
    
    global candidates

    
    
    
    
    
    
    if len(str(x)) == digit:
        candidates.append(x)
        return None
        

    
    
    
    
    
    
        
    tail = int(str(x)[-1])
    if tail == 0:
        rec(10*x + 0, digit, K)
        rec(10*x + 1, digit, K)
    elif tail == 9:
        rec(10*x + 8, digit, K)
        rec(10*x + 9, digit, K)
    else:
        rec(10*x + tail-1, digit, K)
        rec(10*x + tail, digit, K)
        rec(10*x + tail+1, digit, K)


def main():
    global candidates

    K = int(input())

    
    
    
            
    

    
    

    
    

    
    
    
    
    
    
    
    
    
    
    

    n_run = 0
    n_digit = 1
    while True:  
        candidates = []
        for x in range(1, 10):
            rec(x, n_digit, K)
            
            
            
            
        if n_run + len(candidates) >= K:
            return candidates[K-n_run-1]
        
        n_run += len(candidates)
        n_digit += 1
        
    


print(main())

Solution (Python):
K=int(input())
def run(K):
	run=[1,2,3,4,5,6,7,8,9]
	run2=[1,2,3,4,5,6,7,8,9]
	while len(run)<K:
		run3=[]
		for i in run2:
			st=str(i)
			for j in range(10):
				if abs(int(st[-1])-j)<=1:
					run.append(int(10*i+j))
					run3.append(int(10*i+j))
		run2=run3
	return run
ans=run(K)
print(ans[K-1])

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

counter = 0
num_object = [i for i in range(1,10)]

ketaflag_min = 0
ketaflag_max = len(num_object)
index = 1
if k <= 10:
    print(k)

else:
    while True:
        
        for i in range(ketaflag_min,ketaflag_max):
            last_keta = num_object[i] % 10
            
            if last_keta != 9 and last_keta != 0:
                max_keta = last_keta + 1
                min_keta = last_keta - 1
                newnum_max =  num_object[i] * 10 + max_keta
                newnum_mid =  num_object[i] * 10 + last_keta
                newnum_min =  num_object[i] * 10 + min_keta
                num_object.append(min(newnum_max,newnum_min))
                num_object.append(newnum_mid)
                num_object.append(max(newnum_max,newnum_min))
            elif last_keta == 9:
                newnum_min = num_object[i] * 10 + 8
                newnum_mid = num_object[i] * 10 + 9
                num_object.append(newnum_min)
                num_object.append(newnum_mid)
            else:
                newnum_min = num_object[i] * 10 + 0
                newnum_mid = num_object[i] * 10 + 1
                num_object.append(newnum_min)
                num_object.append(newnum_mid)
            if len(num_object) >= k:
                print(num_object[k-1])
                exit()
        ketaflag_min = ketaflag_max
        ketaflag_max = len(num_object)

Solution (Python):
import collections, math

local = False
if local:
    file = open("inputt.txt", "r")

def inp():
    if local:
        return file.readline().rstrip()
    else:
        return input().rstrip()

def ints():
    return [int(_) for _ in inp().split()]



K = int(inp())

nex = [[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]]
globcount = 0

def dfs(curdepth, curval):
    if curdepth<0:
        return False
    
    if curdepth==0:
        global globcount
        globcount += 1

        if globcount==K:
            print(curval)
            return True

    nexarr = nex[int(curval[-1])]
    for j in range(len(nexarr)):
        if dfs(curdepth-1, curval+str(nexarr[j])):
            return True
    
    return False


for depth in range(1, 15):
    found = False
    for i in range(1, 10):
        if dfs(depth-1, str(i)):
            found = True
            break
    
    if found:
        break

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



K = ii()


l = [1,2,3,4,5,6,7,8,9]
for i in range(K-9):
    a = l[i]
    b = int(str(a)[-1])
    if b!=0 and b != 9:
        for k in range(b-1, b+2):
            l.append(int(str(a)+str(k)))
    elif b==0:
        for k in range(b, b+2):
            l.append(int(str(a)+str(k)))
    else:
        for k in range(8, 10):
            l.append(int(str(a)+str(k)))

print(l[K-1])

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


ANS=[[[] for _ in range(10)] for _ in range(10)]
for i in range(10):
    ANS[0][i].append(str(i))
for i in range(1,10):
    for j in range(10):
        if 1<=j and j<=8:
            for k in [j-1,j,j+1]:
                for v in ANS[i-1][k]:
                    ANS[i][j].append(str(j)+v)
        elif j==0:
            for k in [j,j+1]:
                for v in ANS[i-1][k]:
                    ANS[i][j].append(str(j)+v)
        elif j==9:
            for k in [j-1,j]:
                for v in ANS[i-1][k]:
                    ANS[i][j].append(str(j)+v)

X=[]
for i in range(10):
    for j in range(1,10):
        for k in ANS[i][j]:
            X.append(int(k))
X.sort()
print(X[K-1])

Solution (Python):
from collections import deque

K = int(input())

d = [-1, 0, 1]

que = deque([])
for i in range(1, 10):
    que.append(i)
cnt = 0
while que:
    p = que.popleft()
    cnt += 1
    if cnt == K:
        print(p)
        break
    for i in d:
        if 0 <= int(str(p)[-1]) + i <= 9:
            que.append(int(str(p) + str(int(str(p)[-1]) + i)))

Solution (Python):
import sys

inputLine=input()
K=int(inputLine)

runrunNumberList=[]
runrunNumberCount=0
for i in range(10):
    runrunNumberList.append(str(i))
    if i != 0:
        runrunNumberCount += 1
    if runrunNumberCount == K:
        result = i
        print(result)
        sys.exit()

startPoint=0
endPoint=len(runrunNumberList)


while(True):
    for i in range(10):
        for j in range(startPoint, endPoint):
            
            if abs( int(i) - int( runrunNumberList[j][0] ) ) <= 1:
                runrunNumberList.append( str(i) + runrunNumberList[j] )

                if i != 0:
                    runrunNumberCount += 1

                if runrunNumberCount == K:

                    result = int( str(i) + runrunNumberList[j] )
                    print(result)
                    sys.exit()

    startPoint = endPoint
    endPoint = len(runrunNumberList)

Solution (Python):
import itertools

def new_lunlun(org_str):
    last_digit = org_str[-1]
    if last_digit == "0":
        return org_str + "0", org_str + "1"
    elif last_digit == "9":
        return org_str + "8", org_str + "9"
    else:
        minus_digit = str(int(last_digit) - 1)
        plus_digit = str(int(last_digit) + 1)
        return org_str + minus_digit, org_str + last_digit, org_str + plus_digit

def get_next_lunluns(lunluns):
    next_lunluns = [list(new_lunlun(lunlun)) for lunlun in lunluns]
    return list(itertools.chain.from_iterable(next_lunluns))

K = int(input())

sum_num = 0

digits = [0,1,2,3,4,5,6,7,8,9]
ditits_str = list(map(str, digits))
lunluns = ditits_str.copy()[1:]

while(True):
    prev_num = sum_num
    sum_num += len(lunluns)
    if sum_num < K:
        lunluns = get_next_lunluns(lunluns)
    else:
        ind = K - prev_num - 1
        print(lunluns[ind])
        break

Solution (Python):
from collections import deque
k=int(input())
nums=[1,2,3,4,5,6,7,8,9]
lst=deque()
for j in nums:
  d=deque()
  d.append(j)
  while len(d)<10**5:
    num=d.popleft()
    lst.append(num)
    s=str(num)
    l=len(s)
    t=int(s[l-1])
    if 1<=t<=8:
      d.append(s+str(t-1))
      d.append(s+str(t))
      d.append(s+str(t+1))
    if t==0:
      d.append(s+str(0))
      d.append(s+str(1))
    if t==9:
      d.append(s+str(8))
      d.append(s+str(9))

Lst=list(lst)
Lst=list(map(int,Lst))
Lst.sort()
print(Lst[k-1])

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

x = [0]

while(k > 0):
    len_x = len(x)

    if len_x == 1:
        if x[0] != 9:
            x[0] = x[0] + 1
        else:
            x[0] = 1
            x.append(0)
    elif len_x == 2:
        if (x[0] == 9 and x[1] == 9):
            x = [0] * len(x)
            x.insert(0, 1)
        elif x[1] - x[0] < 1:
            x[1] += 1
        else:
            x[0] += 1
            x[1] = x[0] - 1
    else:
        for i in range(len_x):
            if sum(x) == 9 * len_x:
                x = [0] * len(x)
                x.insert(0, 1)
                break
            elif i == len_x - 1:
                x[0] += 1
                temp = x[0]
                x = [temp - i if temp - i >= 0 else 0 for i in range(len_x)]
                break
            elif x[-1 - i] - x[-2 - i] < 1:
                if x[-1 - i] == 9:
                    continue
                x[-1 - i] = x[-1 - i] + 1
                temp = x[-1 - i]
                for j in range(i):
                    j = i - j
                    x[-j] = x[-1 -j] - 1 if x[-1 -j] - 1 >= 0 else 0
                break
    k -= 1

print("".join([str(x) for x in x]))

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

idx = 0
l = list(range(1, 10))

while len(l) < K:
    m = l[idx]
    for i in (-1, 0, 1):
        n = (m % 10) + i
        if n in {-1, 10}:
            continue
        tmp = int(str(m) + str(n))
        l.append(tmp)
    idx = idx + 1

print(l[K-1])

Solution (Python):
k = int(input())
cnt = 1
loop = 1
r_li = []


def make_runrun(i, runrun_list):
    new_list = []
    for runrun in runrun_list:
        new_list.append('{}{}'.format(i, runrun))
    return new_list

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


while len(r_li) < k:
    
    next_tmp = [[]] * 10
    for i in range(1, 10):
        l = 0
        r_li.extend(make_runrun(i, tmp[i - 1]))
        l += len(tmp[i - 1])
        r_li.extend(make_runrun(i, tmp[i]))
        l += len(tmp[i])
        if i != 9:
            r_li.extend(make_runrun(i, tmp[i + 1]))
            l += len(tmp[i + 1])
        next_tmp[i] = r_li[-l:]
    for i in tmp[0]:
        next_tmp[0].append('{}{}'.format(0, i))
    for i in tmp[1]:
        next_tmp[0].append('{}{}'.format(0, i))
    tmp = next_tmp

print(r_li[k - 1])

Solution (Python):
from collections import defaultdict
import math

N = int(input())
run = [list(map(str, range(1, 10)))]
l = 0
count = 9
stop = 10**5
while(1):
    if count > stop:
        break
    nextrun = []
    for i in run[l]:
        if i[-1] == '0':
            nextrun.append(i+'0')
            nextrun.append(i+'1')
        elif i[-1] == '9':
            nextrun.append(i+str(int(i[-1])-1))
            nextrun.append(i+str(int(i[-1])))
        else:
            nextrun.append(i+str(int(i[-1])-1))
            nextrun.append(i+str(int(i[-1])))
            nextrun.append(i+str(int(i[-1])+1))
    run.append(nextrun)
    count += len(nextrun)
    l += 1

newrun = []
for i in run:
    newrun.extend(i)
print(newrun[N-1])

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
import numpy as np

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())

def LI(): return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number): return [LI() for _ in range(rows_number)]

k = int(input())
m = []
flatten = lambda x: [str(z) for y in x for z in (flatten(y) if hasattr(y, '__iter__') and not isinstance(y, str) else (y,))]

ll = [str(i) for i in range(1,10)]
o = []
for s in ll:
    l = []
    l.append(s)
    for i in range(10):
        p = []
        for j in l[-1]:
            t = []
            if str(j[-1])=='0':
                t.append(j+'0')
                t.append(j+'1')
            elif str(j[-1])=='9':
                t.append(j+'8')
                t.append(j+'9')
            else:
                t.append(j+str(int(j[-1])-1))
                t.append(j+str(int(j[-1])))
                t.append(j+str(int(j[-1])+1))
            p.append(t)
        l.append(flatten(p))
    o.append(l)

flatten = lambda x: [int(z) for y in x for z in (flatten(y) if hasattr(y, '__iter__') and not isinstance(y, str) else (y,))]


print(sorted(set(flatten(o)))[k-1])

Solution (Python):
from itertools import product

k = int(input())
ls = []

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

while len(ls) < k:
    for i in range(1, 10):
        for j in product([-1, 0, 1], repeat=digit):
            num = str(i)
            skip = 0
            for y in j:
                x = int(num[-1])+y
                if x < 0 or 9 < x:
                    skip = 1
                    break
                num += str(x)
            if skip:
                continue
            ls.append(int(num))
    digit += 1
print(ls[k-1])

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

    if K < 10:
        print(K)
        return

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

    x = 9
    while True:
        T = []
        for r in R:
            if r % 10 > 0:
                T.append(r * 10 + (r % 10) - 1)
                x += 1
                if x >= K:
                    print(r * 10 + (r % 10) - 1)
                    return
            T.append(r * 10 + (r % 10))
            x += 1
            if x >= K:
                print(r * 10 + (r % 10))
                return
            if r % 10 < 9:
                T.append(r * 10 + (r % 10) + 1)
                x += 1
                if x >= K:
                    print(r * 10 + (r % 10) + 1)
                    return

        R = T[::]

if __name__ == '__main__':
    main()

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

while len(ans) < k:
    now = ans[c]
    t = int(now[-1])
    if t != 0:
        ans.append(str(now) +str(t-1))

    ans.append(str(now) +str(now)[-1])

    if t != 9:
        ans.append(str(now) +str(t+1))

    c += 1
print(ans[k-1])

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

def dfs(now, depth):
    STACK.append(str(now))
    if depth == limit:
        LUNLUN.append(int("".join(STACK)))
    else:
        for next in range(now - 1, now + 2):
            if next == -1 or next == 10:
                continue
            dfs(next, depth + 1)
    STACK.pop()

LUNLUN = []
STACK= []
for limit in range(10):
    for i in range(1, 10):
        dfs(i, 0)

print(LUNLUN[k - 1])

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

while len(a) < K:
    temp = set()
    for now in prev:
        c = now%10
        if c == 0:
            temp.add(now*10)
            temp.add(now*10+1)
        elif c == 9:
            temp.add(now*10+9)
            temp.add(now*10+8)
        else:
            temp.add(now*10+c-1)
            temp.add(now*10+c)
            temp.add(now*10+c+1)
    prev = temp
    a = a|temp
print(sorted(list(a))[K-1])

Solution (Python):
import sys

K = int(input())
s = [1,2,3,4,5,6,7,8,9,10,11,12,21,22,23,32,33,34,43,44,45,54,55,56,65,66,67,76,77,78,87,88,89,98,99]

if K <= 35:
  print(s[K-1])
  sys.exit()

heads = ["10","11","12","21","22","23","32","33","34","43","44","45","54","55","56","65","66","67","76","77","78","87","88","89","98","99"]
s = len(heads)
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]}


i = 0
K = K-10
while True:
  lenHeads = len(heads)
  if lenHeads-1 >= K:
      print(int(heads[K]))
      sys.exit()
  now = heads[i]
  tail = now[-1]
  values = dic[int(tail)]
  for v in values:
      newHead = "".join([now,str(v)])
      heads.append(newHead)
  i+=1

Solution (Python):
nyuryoku=int(input())
lunlun=[["1","2","3","4","5","6","7","8","9"],[],[],[],[],[],[],[],[],[]]
numbers=[["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"]]

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

newrunrun=[]
for i in range(len(lunlun)):
    newrunrun+=lunlun[i]
newlunlun=list(map(int,newrunrun))
newlunlun.sort()
print(newlunlun[nyuryoku-1])

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

def cal():
    count = 9
    d = [[1,2,3,4,5,6,7,8,9]]
    for i in range(10**9):
        d_ = []
        for j in range(len(d[i])):
            a = str(d[i][j])
            if a[-1]=="0":
                for k in [0, 1]:
                    d_.append(int(a)*10+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return
            elif a[-1]=="9":
                for k in [8, 9]:
                    d_.append(int(a)*10+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return 
            else:
                for k in [-1, 0, 1]:
                    d_.append(int(a)*10+int(a[-1])+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return
        d.append(d_)
if K <= 9:
    print(K)
else:
    cal()

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

lun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for idx, ll in enumerate(lun, start=1):
    base = int(str(ll)[-1])
    candi = list(filter(lambda x: 0 <= x < 10, [base - 1, base, base + 1]))
    for c in candi:
        target = str(ll) + str(c)
        lun.append(int(target))
    if idx > K:
        break
lun.sort()

print(lun[K-1])