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

Solution (Python):

from collections import deque
k = int(input())
for digit in range(1,11):
    q = []
    cnt = 0
    for i in range(10):
        s = str(i)
        if digit == 1:
            if s[0] != "0":
                cnt += 1
                if cnt == k:
                    print(s)
                    exit()
            continue
        plus = 1
        stack = deque(s)
        while len(stack[0]) < digit:
            t = stack.popleft()
            top = int(t[0])
            for j in [top-1,top,top+1]:
                if j >= 0 and j <= 9:
                    l = str(j) + t
                    stack.append(l)
        while stack:
            t = stack.popleft()
            if t[0] != "0":
                cnt += 1
                q.append(t)
    q.sort()
    
    if k > cnt:
        k -= cnt
    else:
        print(q[k-1])
        exit()

Solution (Python):
K = int(input())
A = [1,2,3,4,5,6,7,8,9]
for i in range(len(A)):
    if A[i] != 9:
        for j in range(-1,2):
            a = int(str(A[i]) + str(A[i]+j))
            A.append(a)
    else:
        A.append(98)
        A.append(99)
A.append(100)
A.append(101)
L1 = len(A.copy())
for i in range(10,L1):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L2 = len(A.copy())
for i in range(L1,L2):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B%10) + j))
            A.append(a)
L3 = len(A.copy())
for i in range(L2,L3):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L4 = len(A.copy())
for i in range(L3,L4):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L5 = len(A.copy())
for i in range(L4,L5):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L6 = len(A.copy())
for i in range(L5,L6):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L7 = len(A.copy())
for i in range(L6,L7):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L8 = len(A.copy())
for i in range(L7,L8):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
A = sorted(A)

print(A[K-1])

Solution (Python):
from collections import defaultdict
def solve(K):
    d = defaultdict(list)

    d[0] = ["00", "01", "10", "11", "12"]
    d[1] = ["00", "01", "10", "11", "12", "21", "22", "23"]
    d[2] = ["10", "11", "12", "21", "22", "23", "32", "33", "34"]
    d[3] = ["21", "22", "23", "32", "33", "34", "43", "44", "45"]
    d[4] = ["32", "33", "34", "43", "44", "45", "54", "55", "56"]
    d[5] = ["43", "44", "45", "54", "55", "56", "65", "66", "67"]
    d[6] = ["54", "55", "56", "65", "66", "67", "76", "77", "78"]
    d[7] = ["65", "66", "67", "76", "77", "78", "87", "88", "89"]
    d[8] = ["76", "77", "78", "87", "88", "89", "98", "99"]
    d[9] = ["87", "88", "89", "98", "99"]

    initial = [0, 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 < len(initial):
        print(initial[K])
        return

    counter = len(initial)
    while True:
        new_adj = defaultdict(list)
        for i in range(0, 10):
            for j in d[i]:  
                n = (str(i)+j)
                if(n[0]!="0"):
                    counter += 1
                if counter == K+1:
                    print(n)
                    return

                new_adj[i].append(n)
                if i != 0:
                    new_adj[i-1].append(n)
                if i != 9:
                    new_adj[i+1].append(n)

        d = new_adj
K = int(input())
solve(K)

Solution (Python):
K=int(input())
Xs=[1,2,3,4,5,6,7,8,9]
s=0
e=9
while K > len(Xs):
    for i in range(e-s):
        n=list(str(Xs[s+i]))
        if int(n[-1])-1 >= 0:
            Xs.append(int(''.join(n+[str(int(n[-1])-1)])))
        Xs.append(int(''.join(n+[str(int(n[-1]))])))
        if int(n[-1])+1 <= 9:
            Xs.append(int(''.join(n+[str(int(n[-1])+1)])))
    s=e
    e=len(Xs)
print(Xs[K-1])

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

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

lst = [[1] * 11 for _ in range(2)]

lst[0][10] = 0
lst[1][0] = 0
lst[1][10] = 0

now = 9
p = 0
flag = 0
while True:
    if p == 0:
        lst[flag + 1][0] = lst[flag][0] + lst[flag][1]
        p += 1
        continue
    tmp = lst[flag][p - 1] + lst[flag][p] + lst[flag][p + 1]
    lst[flag + 1][p] = tmp
    if now + tmp >= K:
        break
    now += tmp
    p += 1

    if p == 10:
        p = 0
        flag += 1
        lst.append([0] * 11)








ans = str(p)
flag += 1
while True:
    if flag == 0:
        break
    
    if p >= 1 and K <= now + lst[flag - 1][p - 1]:
        flag -= 1
        ans += str(p - 1)
        p -= 1
    elif K <= now + lst[flag - 1][p - 1] + lst[flag - 1][p]:
        now += lst[flag - 1][p - 1]
        flag -= 1
        ans += str(p)
    else:
        now += lst[flag - 1][p - 1] + lst[flag - 1][p]
        flag -= 1
        ans += str(p + 1)
        p += 1

print (ans)