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

lunlun=[[0 for i in range(0,10)] for i in range(0,13)]
for i in range(0,10):
    lunlun[1][i]=1
for i in range(2,13):
    for j in range(0,10):
        if j==0:
            lunlun[i][j]=lunlun[i-1][0]+lunlun[i-1][1]
        else:
            ans=0
            ans+=lunlun[i-1][j-1]+lunlun[i-1][j]
            if 9>j:
                ans+=lunlun[i-1][j+1]

            lunlun[i][j]=ans

def condition(num):
    s=str(num)
    n=len(s)
    ans=0
    dp=[0 for i in range(0,n+1)]
    dp[n]=1
    for k in range(0,n-1):
        i=n-1-k
        j=int(s[i-1])
        ans=0
        if j>0:
            if int(s[i])>j-1:
                ans+=lunlun[n-i][j-1]
            elif int(s[i])==j-1:
                ans+=dp[i+1]

        if int(s[i])>j:
            ans+=lunlun[n-i][j]
        elif int(s[i])==j:
            ans+=dp[i+1]

        if 9>j:
            if int(s[i])>j+1:
                ans+=lunlun[n-i][j+1]
            elif int(s[i])==j+1:
                ans+=dp[i+1]

        dp[i]=ans

    ans=0
    for i in range(1,int(s[0])):
        ans+=lunlun[n][i]
    ans+=dp[1]
    for i in range(1,n):
        for j in range(1,10):
            ans+=lunlun[i][j]

    return ans>=K
start=1
end=10**12
while end-start>1:
    test=(end+start)//2
    if condition(test):
        end=test
    else:
        start=test

if condition(start):
    print(start)
else:
    print(end)