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

Solution (Python):
import math

def is_lunlun(num):
    if num < 10:
        return True
    str_num = str(num)
    length = len(str_num)
    for i in range(length - 1):
        left = int(str_num[i])
        right = int(str_num[i + 1])
        
        if abs(left - right) > 1:
            if left > right:
                
                return i + 2
            
            return [i + 1, left + 1]
            
    return True

k = int(input())

i = 1
counta = 0
lunlun = 0
while(True):
    lunlun = is_lunlun(i)
    if lunlun == True:
        counta += 1
        if counta >= k:
            break
        i += 1
    elif type(lunlun) == int:
        length = len(str(i))
        i += 10 ** (length - lunlun)
        continue
    else:
        length = len(str(i))
        div = 10 ** (length - lunlun[0])
        i = math.floor(i / div / 10) * div * 10 + lunlun[1] * div
print(i)

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

ans = 1
cnt = 0
while cnt < k:
    
    if ans <= 9:
        cnt+=1
        ans+=1
        continue
    li = list(map(int, list(str(ans))))
    flag=1
    for i in range(len(li)-1):
        if abs(li[i]-li[i+1]) > 1:
            ans+=10**(len(li)-i-2)
            flag=0
            break
    if flag:
        cnt+=1
        ans+=1
print(ans-1)

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

def lunlun(a):
    res = []
    for i in a:
        j = int(i[-1])
        if j == 0:
            res += [i + '0', i +'1']
        elif j == 9:
            res += [i + '8', i +'9']
        else:
            res += [i + str(j-1),  i + str(j), i + str(j+1)]
    return res


res = []
a = list(map(str, range(1, 10)))
while len(res) < k:
    if not res:
        tmp = a
    else:
        tmp = lunlun(tmp)
    res.extend(tmp)

print(res[k-1])

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

num = [0] * 10
num[0] = 1
keta = 1
for i in range(k-1):
  change = 0
  for j in range(keta-1):
    if (num[j] < num[j+1]) or (num[j]==num[j+1] and num[j+1]<9):
      num[j] += 1
      change = 1
      for x in range(j, 0, -1):
        num[x-1] = max(0, num[x]-1) 
      break
  if not change:
    if num[keta-1]<9:
      num[keta-1] += 1
      for x in range(keta-1, 0, -1):
        num[x-1] = max(0, num[x]-1) 
    else:
      num[keta-1] = 0
      num[keta] = 1
      for x in range(keta, 0, -1):
          num[x-1] = max(0, num[x]-1) 
      keta += 1
  
ans = 0
d = 1
for i in range(10):
  
  ans += num[i]*d
  d *= 10
  
print(ans)

Solution (Python):
def dp(i, j, memo):
    key = "{}.{}".format(i, j)

    if i == 1:
        memo[key] = 1
        return memo[key]

    if key in memo:
        return memo[key]

    if j == 0:
        memo[key] = dp(i-1, j, memo) + dp(i-1, j+1, memo)
        return memo[key]

    if j == 9:
        memo[key] = dp(i-1, j-1, memo) + dp(i-1, j, memo)
        return memo[key]

    memo[key] = dp(i-1, j-1, memo) + dp(i-1, j, memo) + dp(i-1, j+1, memo)
    return memo[key]


k = int(input())
memo = {"1.0": 0}

num = 0

i = 1
j = 0

while(num < k):
    j += 1
    j %= 10
    if j == 0:
        i += 1
    else:
        num += dp(i, j, memo)

p = k - num + dp(i, j, memo)
ans = [j]
for l in range(1, i):
    n = 0
    x = max(-1, ans[-1] - 2)
    while n < p and x < 10:
        x += 1
        n += dp(i-l, x, memo)
    ans.append(x)
    p = p - n + dp(i-l, x, memo)

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

Solution (Python):
K = int(input())
Lun_count = 0
if K<=9:
    print(K)
else:
    N=10
    Lun_count = 9
    while(1):
        strN = list(str(N))
        lenN = len(strN)
        for i in range(1,lenN):
            if int(strN[i-1])-int(strN[i]) > 1:
                strN[i]= str(int(strN[i-1])-1)
                N = int(''.join(strN))
                break
            elif int(strN[i-1])-int(strN[i]) < -1:
                strN[i-1] = str(int(strN[i-1])+1)
                strN[i] = '0'
                N = int(''.join(strN))
                break
        else:
            Lun_count +=1
            if Lun_count == K:
                break
            N +=1
    print(N)

Solution (Python):
k = int(input())
a = [[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]]

b = 9  
runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9] + [0]*150000
hk = 1
keta = 2

def hi(hitoketamae):
    pass

'''
if k<=9:
    print(k)
else:
'''
while b<k:
    """
    if keta == 11:
        for i1 in a[hk]:
            for i2 in a[i1]:
                for i3 in a[i2]:
                    for i4 in a[i3]:
                        for i5 in a[i4]:
                            for i6 in a[i5]:
                                for i7 in a[i6]:
                                    for i8 in a[i7]:
                                        for i9 in a[i8]:
                                            for i10 in a[i9]:
                                                b += 1
                                                runrun[b] = [hk, i1, i2, i3, i4, i5, i6, i7, i8, i9]
        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    """
    if keta == 10:
        for i1 in a[hk]:
            for i2 in a[i1]:
                for i3 in a[i2]:
                    for i4 in a[i3]:
                        for i5 in a[i4]:
                            for i6 in a[i5]:
                                for i7 in a[i6]:
                                    for i8 in a[i7]:
                                        for i9 in a[i8]:
                                            b += 1
                                            runrun[b] = [hk, i1, i2, i3, i4, i5, i6, i7, i8, i9]
        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 9:
        for i1 in a[hk]:
            for i2 in a[i1]:
                for i3 in a[i2]:
                    for i4 in a[i3]:
                        for i5 in a[i4]:
                            for i6 in a[i5]:
                                for i7 in a[i6]:
                                    for i8 in a[i7]:
                                        b += 1
                                        runrun[b] = [hk, i1, i2, i3, i4, i5, i6, i7, i8]
        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 8:
        for i1 in a[hk]:
            for i2 in a[i1]:
                for i3 in a[i2]:
                    for i4 in a[i3]:
                        for i5 in a[i4]:
                            for i6 in a[i5]:
                                for i7 in a[i6]:
                                    b += 1
                                    runrun[b] = [hk, i1, i2, i3, i4, i5, i6, i7]
        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 7:
        for i1 in a[hk]:
            for i2 in a[i1]:
                for i3 in a[i2]:
                    for i4 in a[i3]:
                        for i5 in a[i4]:
                            for i6 in a[i5]:
                                b += 1
                                runrun[b] = [hk, i1, i2, i3, i4, i5, i6]
        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 6:
        for i1 in a[hk]:
            for i2 in a[i1]:
                for i3 in a[i2]:
                    for i4 in a[i3]:
                        for i5 in a[i4]:
                            b += 1
                            runrun[b] = [hk, i1, i2, i3, i4, i5]
        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 5:
        for i in a[hk]:
            for j in a[i]:
                for jj in a[j]:
                    for jjj in a[jj]:
                            b += 1
                            runrun[b] = [hk, i, j, jj, jjj]

        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 4:
        for i in a[hk]:
            for j in a[i]:
                for jj in a[j]:
                    b += 1
                    runrun[b] = [hk, i, j, jj]

        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 3:
        for i in a[hk]:
            for j in a[i]:
                b += 1
                
                runrun[b] = [hk, i, j]

        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    elif keta == 2:
        for i in a[hk]:
            b += 1
            runrun[b] = [hk, i]

        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
        
ans = ''


if k<=9:
    ans = int(k)
else:
    for i in runrun[k]:
        ans = ans + str(i)
    ans = int(ans)
print(ans)

Solution (Python):
K=int(input())
u12 = [i for i in range(1,10)]
ans = 0
for i in range(K):
    if ans <=11:
        ans += 1
        continue
    flg = True
    l = len(str(ans))
    for j in range(l-1,-1,-1):
        if 0<j<l-1:
            x,y,z = map(int,str(ans)[j-1:j+2])
            if y!=9 and abs(x-(y+1))<=1 and abs((y+1)-z)<=1:
                ans = int(str(ans)[:j]+''.join([str(max(0,y+1-i)) for i in range(l-j)]))
                flg = False
                break
        elif j==0:
            x,y = map(int,str(ans)[:2])
            if x != 9 and abs(x+1-y) <=1:
                ans = int(''.join([str(max(0,x+1-i))for i in range(l)]))
                flg = False
                break
        else:
            x,y = map(int,str(ans)[-2:])
            if y != 9 and abs(x-(y+1))<=1:
                ans += 1
                flg = False
                break
    if flg:
        ans = 10**l
print(ans)

Solution (Python):

K=int(input())

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

for i in range(10):
    for j in range(10):
        if abs(i-j)<=1:
            lun[i].append(j)

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

for i in range(9):
    lunlun.append([])

for i in range(9):
    for j in range(len(lunlun[i])):
        for k in range(len(lun[lunlun[i][j]%10])):
            lunlun[i+1].append(lunlun[i][j]*10+lun[lunlun[i][j]%10][k])
LUNLUN=[]

for i in range(10):
    LUNLUN.extend(lunlun[i])
LUNLUN.sort

print(LUNLUN[K-1])

Solution (Python):
import sys

input = sys.stdin.readline


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

    L = []
    n1 = [[i + 1] for i in range(9)]
    L.append(n1)
    cnt = 0
    if 1 <= K <= 9:
        print(K)
        exit()
    else:
        cnt += 9

    
    n2 = [[] for _ in range(9)]
    L.append(n2)
    for i in range(9):
        base = 11 * (i + 1)
        if i != 8:
            L[1][i].extend([base - 1, base, base + 1])
        else:
            L[1][i].extend([base - 1, base])
        if K <= cnt + len(L[1][i]):
            print(L[1][i][K - cnt - 1])
            exit()
        else:
            cnt += len(L[1][i])

    k = 2
    while True:
        n = [[] for _ in range(9)]
        L.append(n)
        for i in range(9):
            base = (10 ** k) * (i + 1)
            if i == 0:
                ll = []
                ll += [base, base + 1]
                if k >= 3:
                    for m in range(2, k):
                        ll += [base + j for j in L[m-1][0]]
                ll += [base + j for j in L[k-1][i]]
                ll += [base + j for j in L[k-1][i + 1]]
                L[k][i].extend(ll)
            elif i < 8:
                ll = []
                ll += [base + j for j in L[k-1][i - 1]]
                ll += [base + j for j in L[k-1][i]]
                ll += [base + j for j in L[k-1][i + 1]]
                L[k][i].extend(ll)
            else:
                ll = []
                ll += [base + j for j in L[k-1][i - 1]]
                ll += [base + j for j in L[k-1][i]]
                L[k][i].extend(ll)
            if K <= cnt + len(L[k][i]):
                print(L[k][i][K - cnt - 1])
                exit()
            else:
                cnt += len(L[k][i])
        k += 1


if __name__ == "__main__":
    main()

Solution (Python):
X=int(input())
a=[1,2,3,4,5,6,7,8,9]
if 1<=X<=10**5:
    while len(a)<X:
        i=0
        for i in range(X-10):
            if i<len(a):
                c=int(a[i])
                d=10*c
                b=c%10
                b_1=b-1
                b_2=b
                b_3=b+1
                if (b_1>=0)and(b_3<10):
                    a_1=d+b_1
                    a_2=d+b_2
                    a_3=d+b_3
                    a.append(a_1)
                    a.append(a_2)
                    a.append(a_3)
                elif b_1<0:
                    a_2=d+b_2
                    a_3=d+b_3
                    a.append(a_2)
                    a.append(a_3)
                else:
                    a_1=d+b_1
                    a_2=d+b_2
                    a.append(a_1)
                    a.append(a_2)
            i+=1
    a=sorted(a)
    print(a[X-1])

Solution (Python):

"""
Created on Sat Apr  4 21:48:09 2020

@author: Kanaru Sato
"""

k = int(input())

gl = list(map(str,[0,1,2,3,4,5,6,7,8,9]))

starti = 0
endi = len(gl)
l=[]

while len(l) < k:
    ngl = gl[starti:endi]
    for i in range(len(ngl)):
        if ngl[i][0] == "0":
            gl.append("0"+ngl[i])
            gl.append("1"+ngl[i])
        elif ngl[i][0] == "9":
            gl.append("8"+ngl[i])
            gl.append("9"+ngl[i])
        else:
            gl.append(str(int(ngl[i][0])-1)+ngl[i])
            gl.append(str(int(ngl[i][0]))+ngl[i])
            gl.append(str(int(ngl[i][0])+1)+ngl[i])
    starti = endi
    endi = len(gl)
    
    l = []
    for i in gl:
        if i[0] != "0":
            l.append(int(i))

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

Solution (Python):
"""k = int(input())
A = [0] * k

i = 1
r = 0
while r < k:
    if i <= 9:
        A[r] = i
        r = r + 1
    else:
        for j in range(len(str(i)) - 1):
            if not (-1 <= int(str(i)[j]) - int(str(i)[j + 1]) <= 1):
                break
            if j == len(str(i)) - 2:
                A[r] = i
                r = r + 1

    i = i + 1

print(A[k - 1])"""

k = int(input())
A = [1] * k
i = 0
j = 0
treat = [-1, 0, 1]

while i < k:
    if i < 9:
        A[i] = i + 1
        i = i + 1
    else:
        for l in range(3):
            if l == 0 and str(A[j])[-1] == "0":
                continue
            elif l == 2 and str(A[j])[-1] == "9":
                continue
            else:
                A[i] = int(str(A[j]) + str(int(str(A[j])[-1]) + treat[l]))
                i = i + 1

            if i == k:
                break
        j = j + 1

print(A[-1])

Solution (Python):
class Tree:
    def __init__(self, num, count, zeroflag, accum):
        self.num = num
        self.count = count
        self.zeroflag = zeroflag
        self.accum = accum.copy()
        self.accum.append(self.num)

        if self.num != 0:
            self.zeroflag = False

        if self.zeroflag == True:
            self.list = list(range(0,10))
        elif self.zeroflag == True and self.count == 10:
            self.list = list(range(0,3))
        else:
            self.list = list(filter(lambda x: 0<=x and x<=9, [num-1,num,num+1]))

        if(count > 0):
            self.nodes = [Tree(elem, count-1,self.zeroflag,self.accum.copy()) for elem in self.list]

    def __repr__(self):
        if(self.count == 0):
            return "Tree: {}".format(self.num)
        else:
            return "Tree: {}<".format(self.num) + str(list(self.nodes))

    def print_accum(self, a):
        if(self.count == 0):
            
            a.append(self.accum)
        else:
            for elem in self.nodes:
                elem.print_accum(a)



if __name__ == '__main__':
    
    K = int(input())
    a = []
    t = Tree(0,9,True,[])
    t.print_accum(a)
    t = Tree(1,9,True,[])
    t.print_accum(a)
    t = Tree(2,9,True,[])
    t.print_accum(a)
    t = Tree(3,9,True,[])
    t.print_accum(a)
    lst = a[K]
    flag = True;
    for i in lst:
        if i != 0:
            flag = False                
        if i == 0 and flag == True:
            print("", end="")
        else:
            print(i, end="")

    print("")

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

list = []

def standard(n, cur):
  if n == 0:
    
    add = ''.join(cur)
    if str(add).isnumeric() and add != "0":
        list.append(int(add))
  else:
    newC = chr(ord(cur[-1]) + 1)
    standard(n - 1, cur + [newC])
    newC2 = chr(ord(cur[-1]) - 1)
    standard(n - 1, cur + [newC2])
    newC3 = chr(ord(cur[-1]))
    standard(n - 1, cur + [newC3])

for i in range(10):
    for j in range(9):
        standard(i, [str(j+1)])

list = sorted(list)
print(list[N-1])

Solution (Python):
from collections import defaultdict
K = int(input())
mapping = defaultdict(list)
for j in range(10):
    mapping[(0, j)].append(str(j))


for i in range(1, 10):
    for j in range(10):
        if j == 0:
            for item in mapping[(i-1, j)]:
                mapping[(i, j)].append( str(j) + item )
            for item in mapping[(i-1, j+1)]:
                mapping[(i, j)].append( str(j) + item )
        elif j == 9:
            for item in mapping[(i-1, j-1)]:
                mapping[(i, j)].append( str(j) + item )
            for item in mapping[(i-1, j)]:
                mapping[(i, j)].append( str(j) + item )
        else:
            for item in mapping[(i-1, j-1)]:
                mapping[(i, j)].append( str(j) + item )
            for item in mapping[(i-1, j)]:
                mapping[(i, j)].append( str(j) + item )
            for item in mapping[(i-1, j+1)]:
                mapping[(i, j)].append( str(j) + str(item) )


ans = set()
for j in range(10):
    for item in mapping[(0, j)]:
        ans.add(int(item))
for i in range(1, 10):
    for j in range(1, 10):
        for item in mapping[(i, j)]:
            ans.add(int(item))
ans = sorted(list(ans))
print(ans[K])

Solution (Python):


K = int(input())

fueru = [[(x + i - 1) for x in range(3) if 0 <= x + i - 1 <= 9]
         for i in range(10)]

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

last_lst = [i + 1 for i in range(9)]
count = len(last_lst)
for idx in range(10):
    new_lst = []
    for l in last_lst:
        for c in fueru[int(str(l)[-1])]:
            new_lst.append(str(l) + str(c))

    if K <= count + len(new_lst):
        ans = new_lst[K - count - 1]
        print(ans)
        exit()

    count += len(new_lst)
    last_lst = new_lst

Solution (Python):
import copy

    
keta=2
lis=[]
for i in range(1,10):
    lis.append(i)


while len(lis)<=10**5:

    que=[]
    for i in range(1,10):
        a=[-1]*keta
        a[0]=i
        que.append(a)
    
    for k in range(1,keta):
        que_new=[]
        for q in que:
            a,b,c=q[k-1]-1,q[k-1],q[k-1]+1

            if (0<=a) and (9>=a):

                p=copy.copy(q)
                p[k]=a
                que_new.append(p)

            if (0<=b) and (9>=b):
                p=copy.copy(q)
                p[k]=b
                que_new.append(p)
            if (0<=c) and (9>=c):
                p=copy.copy(q)
                p[k]=c
                que_new.append(p)
        que=que_new
    lis+=que
    keta+=1
    

ans=lis[int(input())-1]
if type(ans)==int:
    print(ans)
else:
    en=0
    for i in range(len(ans)):
        en+=10**(len(ans)-i-1)*ans[i]
    print(en)

Solution (Python):
import sys
from itertools import accumulate
K = int(input())

MAX = 22
dp = [[0]*10 for _ in [0]*MAX]

for j in range(0, 10):
    dp[1][j] = 1

for i in range(2, MAX):
    for j in range(1, 9):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]
    dp[i][0] = dp[i-1][0] + dp[i-1][1]
    dp[i][9] = dp[i-1][8] + dp[i-1][9]

acc = [[] for _ in [0]*MAX]
for i in range(1, MAX):
    acc[i] = accumulate(dp[i])


num = [0]
for i in range(1, MAX):
    num.append(num[i-1] + sum(dp[i][1:]))


cnt = 0
for i, n in enumerate(num):
    if n < K:
        keta = i+1
        cnt = n
    else:
        break

ans = 0

rg = range(1, 10)
p = 1
for i in range(keta, 0, -1):
    for j in rg:
        if cnt + dp[i][j] < K:
            flg = True
            p = j+1
            cnt += dp[i][j]
        else:
            break

    ans += 10**(i-1)*p

    rg = range(max(0, p-1), min(10, p+2))
    p = max(0, p-1)

print(ans)

Solution (Python):
K = int(input())
k =9
i = 10
if K > 9:
    while True:
        
        flag = True
        I  = list(map(int,list(str(i))))
        for l in range(len(I)-1):
            if abs(I[l]-I[l+1]) > 1:
                flag = False
                if I[l] < I[l+1]:
                    i = i -i%(10**(len(I)-l-1)) + 10**(len(I)-l-1) -1
                else:
                    i = i -i%(10**(len(I)-l-1)) + (I[l]-1)*10**(len(I)-l-2) -1
                break
        if flag == True:
            k +=1
        
        
        
        if k == K:
            break
        
        i+=1
    print(i)  
else:
    print(K)

Solution (Python):

import sys


def solve(K: int):
    if K <= 12:
        print(K)
        return
    
    
    
    
    
    
    
    
    
    
    
    
    matrix = [[0]*10 for _ in range(11)]

    for i in range(0,10):
        matrix[1][i] = 1

    keta = 2
    SUM = 9
    last = 0
    while True:
        for i in range(10):
            if SUM >= K:
                break

            if i == 0:                
                matrix[keta][i] = matrix[keta-1][0]+matrix[keta-1][1]
            elif i == 9:
                matrix[keta][i] = matrix[keta-1][i-1]+matrix[keta-1][i]
            else:
                matrix[keta][i] = matrix[keta-1][i-1]+matrix[keta-1][i]+matrix[keta-1][i+1]

            if i > 0:
                SUM += matrix[keta][i]
            last = i

        else:
            keta += 1
            continue
        
        break

    answer = str(last)

    while keta > 0:
        i = int(answer[-1])
        SUM -= matrix[keta][i]
        keta -= 1
 
        if i == 0:                
            for j in range(0,2):
                SUM += matrix[keta][j]
                if SUM >= K:
                    answer += str(j)
                    break        
        elif i == 9:
            for j in range(8,10):
                SUM += matrix[keta][j]
                if SUM >= K:
                    answer += str(j)
                    break
        else:
            for j in range(i-1,i+2):
                SUM += matrix[keta][j]
                if SUM >= K:
                    answer += str(j)
                    break
    print(answer)

    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):
import copy
k = int(input())
tmp = [1, 2, 3, 4, 5, 6, 7, 8, 9]
tmp2 = []
if k <= 9:
    print(tmp[k - 1])
    exit()
cnt = 9
while True:
    for t in tmp:
        for i in range(10):
            if abs(int(str(t)[-1]) - i) <= 1:
                tmp2.append(t * 10 + i)
                cnt += 1
                if k == cnt:
                    print(t * 10 + i)
                    exit()
    tmp = copy.copy(tmp2)
    tmp2 = []

Solution (Python):
def count_lunlun(num):
    num = list(map(int, str(num)))
    d = len(num)
    dp = [[[[0] * 10 for _ in range(2)] for _ in range(2)] for _ in range(d + 1)]
    dp[0][0][0][0] = 1
    for i in range(d):
        for j in range(2):
            for k in range(10):
                for z in range(2):
                    for x in range(10 if j else (num[i] + 1)):
                        if abs(x - k) <= 1:
                            dp[i + 1][j or x < num[i]][x != 0 or z][x] += dp[i][j][z][k]
                        elif z == 0:
                            dp[i + 1][j or x < num[i]][x != 0 or z][x] += dp[i][j][z][k]
    return sum(dp[d][0][0]) + sum(dp[d][0][1]) + sum(dp[d][1][0]) + sum(dp[d][1][1]) - 1


K = int(input())
left = 0
right = 10 ** 12
while right - left > 1:
    mid = (left + right) // 2
    count = count_lunlun(mid)
    if count >= K:
        right = mid
    else:
        left = mid
print(right)

Solution (Python):
k = int(input())
l = [[0,1]] + [[i,i+1,i+2] for i in range(8)]+[[8,9]]
ln = [i+1 for i in range(9)]
aln = [i+1 for i in range(9)]
for i in range(10):
    tln = []
    for j in ln:
        for m in l[int(str(j)[-1])]:
            tln.append(j*10+m)
    aln += tln
    ln =tln
    if len(aln) >= k:
      break
print(aln[k-1])

Solution (Python):
def make_tree(G,keta,count):
    if keta==1:
        num =[]
        for i in range(1,10):
            count+=1
            if count ==k:
                print(i)
                exit()
            else:
                num.append(i)
        G.append(num)
        make_tree(G,2,count)
    else:
        
        num_list = G[keta-2]
        num_lis =[]
        for num in num_list:
            num_str = str(num)
            num_e = int(num_str[-1])
            if num_e == 0:
                count +=1
                if count == k :
                    print(int(num_str + "0"))
                    exit()
                num_lis.append(int((num_str)+"0"))
                count+=1
                if count == k :
                    print(int(num_str + "1"))
                    exit()
                num_lis.append(int((num_str)+"1"))
            elif num_e == 9:
                count +=1
                if count == k :
                    print(int(num_str + "8"))
                    exit()
                num_lis.append(int((num_str)+"8"))
                count+=1
                if count == k :
                    print(int(num_str + "9"))
                    exit()
                num_lis.append(int((num_str)+"9"))
            else:
                count +=1
                if count == k :
                    print(int(num_str + str(num_e-1)))
                    exit()
                num_lis.append(int(num_str + str(num_e-1)))
                count+=1
                if count == k :
                    print(int(num_str + str(num_e)))
                    exit()
                num_lis.append(int(num_str + str(num_e)))
                count+=1
                if count == k :
                    print(int(num_str + str(num_e+1)))
                    exit()
                num_lis.append(int(num_str + str(num_e+1)))
        G.append(num_lis)

        make_tree(G,keta+1,count)


k = int(input())
G=[]
make_tree(G,1,0)

Solution (Python):
cnt = 9


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

    numl = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    keta = 1
    dr = [-1, 0, 1]

    def dfs(n, nowk, s):
        if nowk == keta:
            global cnt
            cnt = cnt + 1
            
            if cnt == k:
                print(s)
                return True
            else:
                return False


        for d in dr:
            cand = n + d
            if cand == -1 or cand == 10:
                continue
            if dfs(cand, nowk+1, s + str(cand)):
                return True
        return False

    flag = False

    while 1:
        if k < 10:
            print(k)
            break
        keta = keta + 1
        for n in numl:
            
            if dfs(n, 1, str(n)):
                flag = True
                
                break
        if flag:
            break




if __name__ == '__main__':
    solve()

Solution (Python):
from sys import *
N = int(input())
things = []

def giveNext(first, left_n):
    if left_n < 0:
        return
    if first[-1] +1 < 10:
        things.append(first+ [first[-1]+1])
        giveNext(first+ [first[-1]+1],left_n-1)
    if first[-1] -1 > -1:
        things.append(first+ [first[-1]-1])
        giveNext(first+ [first[-1]-1],left_n-1)

    things.append(first+ [first[-1]])
    giveNext(first+ [first[-1]],left_n-1)

for i in range(1, 10):
    giveNext([i], 8)
things = [int("".join(str(y) for y in x)) for x in things]

things += [1,2,3,4,5,6,7,8,9]
things.sort()
print(things[N-1])

Solution (Python):
import sys

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

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

    lunlun_map = {
        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 < 10:
        print(k)
        sys.exit()

    count = 9
    all_lunluns = [list(range(1, 10))]
    i = 0
    while True:
        for lunlun in all_lunluns[i]:
            least = int(str(lunlun)[-1])
            lunluns = []
            for j in lunlun_map[least]:
                new_lunlun = int(str(lunlun) + str(j))
                lunluns.append(new_lunlun)
                count += 1
                if count == k:
                    print(new_lunlun)
                    sys.exit(0)
            all_lunluns.append(lunluns)
        i += 1

if __name__ == "__main__":
    main()

Solution (Python):

"""
Created on Sat Apr  4 20:58:44 2020

@author: ctiuser
"""
import sys

K = int(input())

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

M = [0,[1,1,1,1,1,1,1,1,1,1]]
s = 9
while K > s:    
    m = [0 for _ in range(10)]
    for i in range(10):
        if i == 0:
            m[i] += M[-1][i] + M[-1][i+1]
        elif i == 9:
            m[i] += M[-1][i-1] + M[-1][i]
        else:
            m[i] += M[-1][i-1] + M[-1][i] + M[-1][i+1]
    M.append(m)
    s += sum(m[1:])
s -= sum(m[1:])
keta = len(M) - 1
ans = ''

i = 0
while K > s:
    i += 1
    s += M[keta][i]

s -= M[keta][i]
ans += str(i)
keta -= 1
d = K - s


while keta > 0:
    if i == 0:
        d -= M[keta][i]
        if d <= 0:
            i = i
            ans += str(i)
            d += M[keta][i]            
        else:
            d -= M[keta][i+1]
            if d <= 0:
                i = i+1
                ans += str(i)
                d += M[keta][i]
    elif i == 9:
        d -= M[keta][i-1]
        if d <= 0:
            i = i-1
            ans += str(i)
            d += M[keta][i]
        else:
            d -= M[keta][i]
            if d <= 0:
                i = i
                ans += str(i)
                d += M[keta][i]
    else:
        d -= M[keta][i-1]
        if d <= 0:
            i = i-1
            ans += str(i)
            d += M[keta][i]
        else:
            d -= M[keta][i]
            if d <= 0:
                i = i
                ans += str(i)
                d += M[keta][i]
            else:
                d -= M[keta][i+1]
                if d <= 0:
                    i = i+1
                    ans += str(i)
                    d += M[keta][i]
        
        
    keta -= 1




print(ans)