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

Solution (Python):


def check(mae, keta, count, k):
    if keta == 0:
        count += 1
        if count == k:
            ans = mae
        else:
            ans = -1
        return count, ans
    if mae == 0:
        count, ans = check(0, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
        count, ans = check(1, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
    elif mae == 9:
        count, ans = check(8, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
        count, ans = check(9, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
    else:
        for i in [-1, 0, 1]:
            count, ans = check(mae + i, keta - 1, count, k)
            if ans >= 0:
                ans += mae * 10 ** keta
                return count, ans
    return count, ans

k = int(input())
if k < 10:
    print(k)
else:
    count = 9
    flag = 0
    for keta in range(2, 1000):
        for sento in range(1, 10):
            count, ans = check(sento, keta - 1, count, k)
            if ans >= 0:
                print(ans)
                flag = 1
                break
        if flag == 1:
            break

Solution (Python):
def create_lun(K):
    if K == 1:
        return ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
    else:
        r = []
        d = create_lun(K - 1)
        for n in d:
            c = int(n[-1])
            if K == 10 and int(n[0]) > 3:
                continue
            if c - 1 >= 0:
                r.append(n + str(c - 1))
            r.append(n + n[-1])
            if c + 1 <= 9:
                r.append(n + str(c + 1))
        r.extend(d)
        return r


def solve(K):
    A = create_lun(10)
    S = set([int(l) for l in A])
    S.remove(0)
    A = sorted(list(S))

    return A[K - 1]


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

Solution (Python):

k = int(input())
lun = [i for i in range(10)]
while len(lun)<k+1:
    lun2 = []
    for i in lun:
        lun2.append(i*10+(i%10))
        if i%10:
            lun2.append(i*10+(i%10)-1)
        if (i%10)<9:
            lun2.append(i*10+(i%10)+1)
    lun = list(set(lun+lun2))
lun.sort()
print(lun[k])

Solution (Python):

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
rr = range


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '
        
        
    return ret


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from fractions import gcd


def lcm(a, b):
    
    g = gcd(a, b)
    return a * b // g


K = read_a_int()


cnt = 0

candi = set()


def dfs(now: int):  
    if len(str(now)) >= 11:
        return
    candi.add(now)
    right = now % 10  
    
    if right == 0:
        tmp = [right, right + 1]
    elif right == 9:
        tmp = [right - 1, right]
    else:
        tmp = [right - 1, right, right + 1]
    for ad in tmp:
        dfs(now * 10 + ad)



for i in range(1, 10):
    dfs(i)
print(sorted(candi)[K - 1])

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

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

memo = [[1]*10] + [[1]*10 for _ in range(9)]

n = 9
digit = 1
i = -1
ans = []
while True:
    i += 1
    if i == 10:
        i = 0
        digit += 1
    tmp = memo[digit-1][i]
    if i >= 1:
        tmp += memo[digit-1][i-1]
    if i <= 8:
        tmp += memo[digit-1][i+1]
    memo[digit][i] = tmp
    if i != 0:
        if n + tmp >= K:
            while digit >= 0:
                t = memo[digit][i]
                
                
                
                
                
                if n + t >=  K:
                    ans.append(i)
                    digit -= 1
                    i = max(0, i-1)
                else:
                    n += t
                    i += 1
            break
        else:
            n += tmp

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

Solution (Python):


MOD = 10**9
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors




K = int(input())

r = [1,2,3,4,5,6,7,8,9]
if K < 10:
    print(r[K-1])
    exit()
f = True
index = 10
cnt = 0
start = 0
while f==True:
    r_len = len(r)
    for i in range(start, r_len):
        s = str(r[i])
        migi = len(s)-1
        ix1 = str(int(s[migi])-1)
        ix2 = str(int(s[migi])+1)
        if int(ix1)>=0:
            r.append(int(s+ix1))
        r.append(int(s+s[migi]))
        if int(ix2)<=9:
            r.append(int(s+ix2))
    start = r_len
    if len(r) > 100000:
        f = False

r = sorted(r)
print(r[K-1])

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

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


while len(ll) < k:
    nq = []
    for i in range(len(lq)):
        d = lq[i] % 10
        if d > 0:
            nl = lq[i] * 10 + d - 1
            nq.append(nl)
            ll.append(nl)
        nl = lq[i] * 10 + d
        nq.append(nl)
        ll.append(nl)
        if d < 9:
            nl = lq[i] * 10 + d + 1
            nq.append(nl)
            ll.append(nl)

    lq = nq

print(ll[k-1])

Solution (Python):



K = int(input())


def solve(dp, i, j, s):
    if i == 0:
        return
    for k in range(max(0, j - 1), min(10, j + 2)):
        if s + dp[i][k] >= K:
            print(k, end="")
            return solve(dp, i - 1, k, s)
        else:
            s += dp[i][k]


def main():
    if K < 10:
        print(K)
        return
    dp = [[None], [1] * 10]
    sn = [[0] * 10, [i for i in range(10)]]
    i = 2
    while True:
        l = [0] * 10
        sl = [0] * 10
        l[0] = dp[i-1][0] + dp[i-1][1]
        sl[0] = sn[i-1][9]
        for j in range(1, 10):
            if j == 9:
                l[9] = dp[i-1][8] + dp[i-1][9]
            else:
                l[j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]
            sl[j] = sl[j-1] + l[j]
            if sl[j] >= K:
                print(j, end="")
                solve(dp, i - 1, j, sl[j-1])
                return
        dp.append(l)
        sn.append(sl)
        i += 1


if __name__ == "__main__":
    main()

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


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

    l = []
    def dfs(i, p, keta):
        l.append(i)
        if keta >= 10:
            return None
        if p != 0 and p != 9:
            for j in range(p-1, p+2):
                temp = j*(10**keta)+i
                l.append(temp)
                dfs(temp, j, keta+1)
        if p == 0:
            for j in range(p, p+2):
                temp = j*(10**keta)+i
                l.append(temp)
                dfs(temp, j, keta+1)
        if p == 9:
            for j in range(8, 10):
                temp = j*(10**keta)+i
                l.append(temp)
                dfs(temp, j, keta+1)

    for i in range(10):
        dfs(i, i, 1)
    
    l = list(set(l))
    
    l.sort()
    
    
    print(l[k])

if __name__ == '__main__':
    main()

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


def check(s):
    for i in range(len(s)-1):
        if(abs(int(s[i])-int(s[i+1])) > 1):
            return len(s)-i-2
    return -1


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

    if k < 10:
        print(k)
        return

    c = 10
    s = '1'
    table = [0] * (10**5+5)
    while c <= k+1:
        d = check(s)
        if d != -1:
            s = str(int(s)+10**d)
            continue
        last = int(s[-1])
        if last != 0:
            table[c] = s+str(last-1)
            c += 1
        table[c] = s+str(last)
        c += 1
        if last != 9:
            table[c] = s+str(last+1)
            c += 1
        s = str(int(s)+1)

    print(table[k])


main()

Solution (Python):
k = int(input())
a = [1,2,3,4,5,6,7,8,9] 
kosu = [0,1,1,1,1,1,1,1,1,1]
total = sum(kosu)
i = 0 
tempk = k*1
while k > total:
  b = a.copy() 
  tempk = k - total
  i += 1
  a = [] 
  kosub = kosu.copy() 
  kosu = []
  for i in range(10):
    if i == 0:
      kosu.append(kosub[i]+kosub[i+1])
    elif i == 9:
      kosu.append(kosub[i-1]+kosub[i])
    else:
      kosu.append(kosub[i-1]+kosub[i]+kosub[i+1])
  total += sum(kosu)
  for i in range(len(b)):
    if b[i]%10 == 0:
      a.append(b[i]*10)
      a.append(b[i]*10+1)
    elif b[i]%10 == 9:
      a.append(b[i]*10+8)
      a.append(b[i]*10+9)
    else:
      a.append(b[i]*10+b[i]%10-1)
      a.append(b[i]*10+b[i]%10)      
      a.append(b[i]*10+b[i]%10+1)
  
  
  

print(a[tempk-1])

Solution (Python):
import itertools
k = int(input())
def a(b):
    list_ = []
    for i in b:
        ii = str(i)
        z = int(ii[-1])
        if z==0:
            list_.append(int(ii+'0'))
            list_.append(int(ii+'1'))
        elif z==9:
            list_.append(int(ii+'8'))
            list_.append(int(ii+'9'))
        else:
            list_.append(int(ii+str(z-1)))
            list_.append(int(ii+str(z)))
            list_.append(int(ii+str(z+1)))
    return list_

l1 = [[1]]

for _ in range(9):
    l1.append(a(l1[-1]))

c1 = list(itertools.chain.from_iterable(l1))
l2 = [[2]]

for _ in range(9):
    l2.append(a(l2[-1]))
c2 = list(itertools.chain.from_iterable(l2))
l3 = [[3]]

for _ in range(9):
    l3.append(a(l3[-1]))
c3 = list(itertools.chain.from_iterable(l3))

l4 = [[4]]
for _ in range(9):
    l4.append(a(l4[-1]))
c4 = list(itertools.chain.from_iterable(l4))
l5 = [[5]]

for _ in range(9):
    l5.append(a(l5[-1]))
c5 = list(itertools.chain.from_iterable(l5))

l6 = [[6]]

for _ in range(9):
    l6.append(a(l6[-1]))
c6 = list(itertools.chain.from_iterable(l6))
l7 = [[7]]

for _ in range(9):
    l7.append(a(l7[-1]))
c7 = list(itertools.chain.from_iterable(l7))
l8 = [[8]]

for _ in range(9):
    l8.append(a(l8[-1]))
c8 = list(itertools.chain.from_iterable(l8))

l9 = [[9]]

for _ in range(9):
    l9.append(a(l9[-1]))
c9 = list(itertools.chain.from_iterable(l9))

cc = c1+c2+c3+c4+c5+c6+c7+c8+c9


cc.sort()

print(cc[k-1])

Solution (Python):
import collections
import math
import operator as op
from functools import reduce
from collections import Counter
import numpy as np
import math
import bisect
import heapq


MOD = 1000000007


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def main():
    K = get_input(int)

    Lun = [None for _ in range(10)]
    for n in range(10):
        Lun[n] = [[] for _ in range(11)]
    for n in range(10):
        Lun[n][1].append(n)
    

    for d in range(2, 11):
        for n in range(10):
            o = n*10**(d-1) 
            for i in [n-1, n, n+1]:
                if i >= 0 and i <= 9:
                    Lun[n][d].extend([l + o for l in Lun[i][d-1]])

    flag = True
    cnt = K
    for d in range(1, 11):
        for n in range(1, 10):
            if cnt - len(Lun[n][d]) <= 0:
                flag = False
                break
            else:
                cnt -= len(Lun[n][d])
        if not flag:
            break
    
    
    print(Lun[n][d][cnt-1])


    
    
    
    
    
    
    





    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
 


if __name__ == '__main__':
    main()

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

ans = []
next_list = []
now_list = [""]
cnt = 0
while cnt < K:
    for now in now_list:
        if now == "":
            for i in range(1,10):
                next_list.append(str(i))
                ans.append(str(i))
                cnt += 1
        else:
            end = int(now[-1])
            for i in range(-1,2):
                i += end
                if i < 0 or i > 9:
                    continue
                next_list.append(now+str(i))
                ans.append(now+str(i))
                cnt += 1
    now_list = next_list
    next_list = []

print(ans[K-1])

Solution (Python):
import heapq
k = int(input())
l = [1,2,3,4,5,6,7,8,9]
heapq.heapify(l)
count = 0
now = 0
while count < k:
    
    a = str(heapq.heappop(l))
    count += 1
    now = int(a)
    al = list(a)
    if al[-1] == "0":
        heapq.heappush(l,int(a+"0"))
        heapq.heappush(l,int(a+"1"))
    elif al[-1] == "9":
        heapq.heappush(l,int(a+"8"))
        heapq.heappush(l,int(a+"9"))
    else:
        heapq.heappush(l,int(a+str(int(al[-1])-1)))
        heapq.heappush(l,int(a+str(int(al[-1]))))
        heapq.heappush(l,int(a+str(int(al[-1])+1)))
print(now)

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


cand = [[str(i)] for i in range(10)]


k = 9
end = 0

if K <= 9:
    print(K)
else:
    for j in range(10000000):
        new_cand = [[] for i in range(10)]
        for top in range(10):
            if top == 0:
                new = []
                new += [str(top) + rest for rest in cand[0]]
                new += [str(top) + rest for rest in cand[1]]
                new_cand[top] = new
            elif top != 0 and top != 9:
                new = []
                new += [str(top) + rest for rest in cand[top-1]]
                new += [str(top) + rest for rest in cand[top]]
                new += [str(top) + rest for rest in cand[top+1]]
                new_cand[top] = new
                if k + len(new) >= K:
                    print(new[K-k-1])
                    end = 1
                    break
                k += len(new)
            elif top == 9:
                new = []
                new += [str(top) + rest for rest in cand[8]]
                new += [str(top) + rest for rest in cand[9]]
                new_cand[top] = new
                if k + len(new) >= K:
                    print(new[K-k-1])
                    end = 1
                    break
                k += len(new)
        cand = new_cand
        if end == 1:
            break

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


def fun(h, n):
    tmp = str(n)
    if tmp[-1] == '0':
        heapq.heappush(h, int(tmp + '0'))
        heapq.heappush(h, int(tmp + '1'))
    elif tmp[-1] == '9':
        heapq.heappush(h, int(tmp + '8'))
        heapq.heappush(h, int(tmp + '9'))
    else:
        heapq.heappush(h, int(tmp + str(int(tmp[-1]) - 1)))
        heapq.heappush(h, int(tmp + tmp[-1]))
        heapq.heappush(h, int(tmp + str(int(tmp[-1]) + 1)))


h = list(range(1, 10))
while K > 0:
    tmp = heapq.heappop(h)
    fun(h, tmp)
    K -= 1
else:
    print(tmp)

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    k = int(input())
    dp = [[[] for _ in range(10)] for _ in range(11)]
    
    num = ['0','1','2','3','4','5','6','7','8','9']
    for i in range(10):
        dp[1][i] = [num[i]]

    if k <= 9:
        print(*dp[1][k])
        return 
    
    cnt = 9
    for i in range(2,11):
        for l in range(len(dp[i - 1][0])):
            dp[i][0].append('0' + dp[i - 1][0][l])
        for l in range(len(dp[i - 1][1])):
            dp[i][0].append('0' + dp[i - 1][1][l])   

        for j in range(1,10):
            for l in range(len(dp[i - 1][j - 1])):
                dp[i][j].append(num[j] + dp[i - 1][j - 1][l])
                cnt += 1
                if cnt == k:
                    print(dp[i][j][-1])
                    
                    
                    return

            for l in range(len(dp[i - 1][j])):
                dp[i][j].append(num[j] + dp[i - 1][j][l])
                cnt += 1
                if cnt == k:
                    print(dp[i][j][-1])
                    
                    
                    return

            if j < 9:
                for l in range(len(dp[i - 1][j + 1])):
                    dp[i][j].append(num[j] + dp[i - 1][j + 1][l])
                    cnt += 1
                    if cnt == k:
                        print(dp[i][j][-1])
                        
                        
                        
                        return
        

 
if __name__ =='__main__':
    main()

Solution (Python):
k=int(input())
ans=[[i for i in range(1,10)]]
d=9
while d<k:
    ans.append([])
    for i in ans[-2]:
        x=str(i)
        y=int(x[0])
        if y==1:
            ans[-1].append(str(y)+x)
            ans[-1].append(str(y+1)+x)
        elif 2<=y<=8:
            ans[-1].append(str(y-1)+x)
            ans[-1].append(str(y)+x)
            ans[-1].append(str(y+1)+x)
        else:
            ans[-1].append(str(y-1)+x)
            ans[-1].append(str(y)+x)
        z=int(x[-1])
        if z==0:
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        elif 1<=z<=8:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        else:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
    ans[-1]=list(set(ans[-1]))
    d+=len(ans[-1])
l=len(ans[-1])
v=sorted([int(i) for i in ans[-1]])

print(v[k-(d-l)-1])

Solution (Python):
k=int(input())
count=0
def rec(l,keta,countive,s):
    global count
    global k
    
    if keta==1:
        if countive:
            count+=1
            if count==k:
                while s[0]=="0":
                    s=s[1:]
                print(s)
                return True 
    
    else:
        if l==0:
            if countive==False:
                if rec(0,keta-1,False,s+str(0)):return True
                for i in range(1,10):
                    if rec(i,keta-1,True,s+str(i)):return True
            else:
                if rec(l,keta-1,True,s+str(l)):return True
                if rec(l+1,keta-1,True,s+str(l+1)):return True
        elif l==9:
            if rec(l-1,keta-1,True,s+str(l-1)):return True
            if rec(l,keta-1,True,s+str(l)):return True
        else:
            if rec(l-1,keta-1,True,s+str(l-1)):return True
            if rec(l,keta-1,True,s+str(l)):return True
            if rec(l+1,keta-1,True,s+str(l+1)):return True
rec(0,11,False,"0")

Solution (Python):
X = [i for i in range(1, 10)]
prev = X[:]
for i in range(9):
    ne = []
    for x in prev:
        s = x % 10
        ne.append(x * 10 + s)
        if s: ne.append(x * 10 + s - 1)
        if s < 9: ne.append(x * 10 + s + 1)
    X += ne
    prev = ne
X = sorted(X)
print(X[int(input()) - 1])

Solution (Python):
import sys
sys.setrecursionlimit(pow(10, 6))
N = 12
rs = []
def f(s, bb):
    if len(s) == N:
        rs.append(int(s))
        return
    b = int(s[-1])
    r = []
    if bb == 0:
        for i in range(10):
            if i == 0:
                f(s+str(i), bb)
            else:
                f(s+str(i), 1)
        return
    if b > 0:
        f(s+str(b-1), 1)
    f(s+str(b), 1)
    if b < 9:
        f(s+str(b+1), 1)

f(str(0), 0)
print(rs[int(input())])

Solution (Python):
def next(n):
    s = [int(i) for i in str(n)]
    l = len(s)
    if l == 1:
        return n + 1
    ans = s
    for i in range(l - 1):
        if s[-i - 1] <= s[-i - 2] and s[-i - 1] != 9:
            ans = s[:-i - 1]
            ans.append(s[-i - 1] + 1)
            for j in range(i):
                if ans[-1] == 0:
                    ans.append(0)
                else:
                    ans.append(ans[-1] - 1)
            return int(''.join([str(i) for i in ans]))
    if s[0] == 9:
        return n + 1
    ans = [s[0] + 1]
    for j in range(l - 1):
        if ans[-1] == 0:
            ans.append(0)
        else:
            ans.append(ans[-1] - 1)
    return int(''.join([str(i) for i in ans]))


K = int(input())
ans = 1
for i in range(K - 1):
    ans = next(ans)
print(ans)

Solution (Python):

import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

T = list(map(int,input().split()))

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''


K = int(input())

runrun = []
runrun.append([1, 2, 3, 4, 5, 6, 7, 8, 9])


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


keta = 10
for i in range(1, 20):
    max = 9*pow(3, i-1)

    if max>=K:
        keta = i
        break

for i in range(2, keta+2):
    temp = []
    for j in range(len(runrun[i-2])):

        last = runrun[i-2][j] % 10

        tugi = (last+1) 
        same = last
        mae = (last-1) 

        if tugi != 10:
            temp.append(runrun[i-2][j]*10 + tugi)
        temp.append(runrun[i-2][j]*10 + same)
        
        if mae != -1:
            temp.append(runrun[i-2][j]*10 + mae)

    runrun.append(temp)

sum_size = 0
nokori  =0
for i in range(100):
    runrun[i].sort()
    sum_size+=len(runrun[i])
    if sum_size >= K:
        keta = i
        nokori = K- sum_size+len(runrun[i])
        break

runrun[keta].sort()

print(runrun[keta][nokori-1])

Solution (Python):
K=int(input())
cnt=0
dp=[0]*(10**6)
piv=0
dig=[0]*10000
d=0
cnt=float("inf")
zure=0
befnum=0
i=0
buf=""
cntall=0
while i<2*(10**5):
    if i+1<10:
        dp[i]=i+1
        dig[d]=dig[d]+1
    else:
        if cnt>=dig[d-1]:
            i=i+zure
            zure=0
            cnt=0
            befnum=dig[d]
            d=d+1
        
        buf=str(dp[i-befnum])
        piv=buf[len(buf)-1]
        
        
        if int(piv)==0:
            dp[i+zure]=dp[i-befnum]*10
            dp[i+1+zure]=dp[i - befnum] * 10+1
            dig[d]=dig[d]+2
            zure=zure+1
        elif int(piv)==9:
            dp[i + zure] = dp[i - befnum] * 10+8
            dp[i + 1 + zure] = dp[i - befnum] * 10+9
            dig[d] = dig[d] + 2
            zure = zure + 1
        else:
            dp[i+zure]=dp[i-befnum]*10+int(piv)-1
            dp[i+1+zure]=dp[i - befnum] * 10+int(piv)
            dp[i+2+zure] = dp[i - befnum] * 10 + int(piv)+1
            dig[d] = dig[d] + 3
            zure=zure+2
        cnt=cnt+1
    i=i+1
    
        
    
    
print(dp[K-1])

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

if target<13:
    print(target)
    exit()

cnt=9

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

for j in range(20):
    temp=[]
    for i in [1,2,3,4,5,6,7,8,9]:
        for k in result[i-1][j]:
            result[i][j+1].append(str(i)+str(k))
            cnt+=1
            if cnt==target:
                print(str(i)+str(k))
                exit()
        for k in result[i][j]:
            result[i][j+1].append(str(i)+str(k))
            cnt+=1
            if cnt==target:
                print(int(str(i)+str(k)))
                exit()
        if i!=9:                
            for k in result[i+1][j]:
                result[i][j+1].append((str(i)+str(k)))
                cnt+=1
                if cnt==target:
                    print(int(str(i)+str(k)))
                    exit()
    for item in result[0][j]:
        result[0][j+1].append(str(0)+str(item))
        
    for item in result[1][j]:
        result[0][j+1].append(str(0)+str(item))

print(result[0])

Solution (Python):

import copy

k = int(input())

lun = [1,2,3,4,5,6,7,8,9]
tlun = []
tlun = copy.deepcopy(lun)
length = 2
while len(lun) < k:
    tmp = []
    for x in tlun:
        y = str(x)
        xt = int( y[-1] )
        a = xt + 1
        b = xt - 1
        if a != 10:
            lun.append(int(y+str(a)))
            tmp.append(int(y+str(a)))
        
        if b != -1:
            lun.append(int(y+str(b)))
            tmp.append(int(y+str(b)))
        
        lun.append(int(y+str(xt)))
        tmp.append(int(y+str(xt)))
    tlun = copy.deepcopy(tmp)

lun.sort()
print(lun[k-1])

Solution (Python):
def addketa(x):
    lunlun.append(x)
    if(x > 999999999):
        return 0
    strx = str(x)
    strxlast = int(strx[-1])
    if(strxlast == 0):
        addketa(int(strx+"0"))
        addketa(int(strx+"1"))
    else:
        if(strxlast == 9):
            addketa(int(strx+"8"))
            addketa(int(strx+"9"))
        else:
            addketa(int(strx+str(strxlast-1)))
            addketa(int(strx+str(strxlast)))
            addketa(int(strx+str(strxlast+1)))

            
K = int(input())
lunlun = []


for x in range (1, 10):
    addketa(x)

lunlun.sort()

print(lunlun[K-1])

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

a = [list(range(1, 10))]
while True:
    new = []
    for aa in a[-1]:
        mod = aa % 10
        if mod != 0:
            new.append(aa * 10 + mod - 1)
        new.append(aa * 10 + mod)
        if mod != 9:
            new.append(aa * 10 + mod + 1)
    a.append(new)

    if sum([len(aa) for aa in a]) > k:
        break
flat = sorted(sum(a, []))

print(flat[k - 1])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
K = int(input())
RUN = {
    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]
}
cnt = 0
for i10 in range(10):
    ans10 = i10 * 10 ** 9
    if ans10 == 0:
        i9s = range(10)
    else:
        i9s = RUN[i10]
    for i9 in i9s:
        ans9 = ans10 + i9 * 10 ** 8
        if ans9 == 0:
            i8s = range(10)
        else:
            i8s = RUN[i9]
        for i8 in i8s:
            ans8 = ans9 + i8 * 10 ** 7
            if ans8 == 0:
                i7s = range(10)
            else:
                i7s = RUN[i8]
            for i7 in i7s:
                ans7 = ans8 + i7 * 10 ** 6
                if ans7 == 0:
                    i6s = range(10)
                else:
                    i6s = RUN[i7]
                for i6 in i6s:
                    ans6 = ans7 + i6 * 10 ** 5
                    if ans6 == 0:
                        i5s = range(10)
                    else:
                        i5s = RUN[i6]
                    for i5 in i5s:
                        ans5 = ans6 + i5 * 10 ** 4
                        if ans5 == 0:
                            i4s = range(10)
                        else:
                            i4s = RUN[i5]
                        for i4 in i4s:
                            ans4 = ans5 + i4 * 10 ** 3
                            if ans4 == 0:
                                i3s = range(10)
                            else:
                                i3s = RUN[i4]
                            for i3 in i3s:
                                ans3 = ans4 + i3 * 10 ** 2
                                if ans3 == 0:
                                    i2s = range(10)
                                else:
                                    i2s = RUN[i3]
                                for i2 in i2s:
                                    ans2 = ans3 + i2 * 10
                                    if ans2 == 0:
                                        i1s = range(1, 10)
                                    else:
                                        i1s = RUN[i2]
                                    for i1 in i1s:
                                        ans1 = ans2 + i1
                                        cnt += 1
                                        
                                        if cnt == K:
                                            print(ans1)
                                            exit()

Solution (Python):
K = int(input())
ans_list = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
nex = ans_list.copy()


def resp(n):
    if n == "0":
        return ["0", "1"]
    elif n == "9":
        return ["8", "9"]
    else:
        n_tmp = int(n)
        return [n, str(n_tmp + 1), str(n_tmp - 1)]


for j in range(1000):
    tmp = nex.copy()
    nex = []
    for i in tmp:
        nex += [i + x for x in resp(i[-1])]
    ans_list += nex
    if len(ans_list) > 10 ** 5:
        break

ans_list = list(map(int, ans_list))
ans_list.sort()
print(ans_list[K - 1])