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

one_digit = ["1","2","3","4","5","6","7","8","9"]
tem_digit = []
entity = []
entity.append(one_digit)
for j in range(10):
    tem_digit = []
    for i in range(len(entity[-1])):
        if entity[-1][i][-1] == "9":
            tem_digit.append(entity[-1][i] + "8")
            tem_digit.append(entity[-1][i] + "9")
        elif entity[-1][i][-1] == "0":
            tem_digit.append(entity[-1][i] + "0")
            tem_digit.append(entity[-1][i] + "1")
        else:
            tem_digit.append(entity[-1][i] + str(int(entity[-1][i][-1]) - 1))
            tem_digit.append(entity[-1][i] + str(int(entity[-1][i][-1])))
            tem_digit.append(entity[-1][i] + str(int(entity[-1][i][-1]) + 1))
    tem_digit.sort()
    entity.append(tem_digit)

entity = sum(entity, [])

print(entity[k-1])

Solution (Python):
def next(n):
    i = len(n) -1
    nine = False
    if len(n) == 1:
        if n == [9]:
            return [1,0]
        else:
            return [n[0]+1]
    while i >= 0:
        if nine:
            if n[i] == 8:
                nine = False
                if n[i] - n[i-1] != 1:
                    break
            if i == 0:
                return [1] + [0 for m in range(len(n))]
        else:
            if n[i] == 9:
                nine = True
            elif n[i] - n[i-1] != 1:
                break
        i -= 1
    n[i] += 1
    i += 1
    while i < len(n):
        n[i] = max(0, n[i-1] - 1)
        i += 1
    return n

k = int(input())
if k == 1:
    print('1')
    exit()
i = 1
n = [1]
while i < k:
    i += 1
    n = next(n)
print(*n, sep='')

Solution (Python):
from collections import deque

k = int(input())

d = deque()
for i in range(1,10):
    d.append(i)

i = 0
while i < k:
    a = str(d.popleft())

    if a[-1] == "0":
        d.append(a + "0")
        d.append(a + "1")
    elif a[-1] == "9":
        d.append(a + "8")
        d.append(a + "9")
    else:
        d.append(a + str(int(a[-1]) - 1))
        d.append(a + str(int(a[-1])))
        d.append(a + str(int(a[-1]) + 1))
        pass
    i += 1

print(a)

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

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

def concat(org):
  end = int(org[-1])
  r = []
  if end != 0:
    r.append(org + str(end-1))
  r.append(org + str(end))
  if end != 9:
    r.append(org + str(end+1))
  return r

t = [str(i) for i in range(1, 10)]
for i in range(2, 11):
  r = []
  for e in t:
    r.extend(concat(e))
  t = r
  lunlun.extend(t)



print(lunlun[K-1])

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


def lun(n):
    found = []

    def _lun(top, m):
        if m == 0:
            found.append(int("".join(map(str, top))))
            return
        for t in (top[-1] - 1, top[-1], top[-1] + 1):
            if 0 <= t <= 9:
                _lun(top + [t], m - 1)

    for i in range(1, 10):
        _lun([i], n - 1)

    return found


d = 1
luns = []
while True:
    luns.extend(lun(d))
    if len(luns) >= K:
        break
    d += 1

print(luns[K - 1])

Solution (Python):
K = int(input())
l_lun = [i for i in range(1, 10)]
nowp = 0
while(nowp < K):
  newp = len(l_lun)
  for i in range(nowp, newp):
    left = l_lun[i] % 10
    for j in range(left - 1, left + 2):
      if j < 0 or j >= 10:
        continue
      l_lun.append(l_lun[i] * 10 + j)
  nowp = newp
print(l_lun[K-1])

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

MAXX = 10**5*3


list = []
def genLunlun(dep, last, res):
    if dep <= 0:
        list.append(res)
        return 1

    cnt = 0
    if res == 0:
        for d in range(1, 10):
            cnt = cnt + genLunlun(dep-1, d, d)
        return cnt


    for d in range(-1,2):
        num = last + d
        if (num >= 0) and (num <= 9):
            cnt = cnt + genLunlun(dep-1, num, res*10 + num)
    return cnt

def findX(list, K):
    last = -1
    cnt = 0
    for item in list:
        if item != last:
            cnt = cnt + 1
            last = item
            if cnt == K:
                return last
    return -1

total = 0
num = 0
dep = 0
while True:
    dep = dep + 1
    cnt = genLunlun(dep, -1, 0)
    total = total + cnt
    if total >= K:
        num = list[K-1]
        
        
        break

print(num)

Solution (Python):
k = int(input())
if k <10:
    print(k)
    exit()
ls = [0] * (k+1)
for i in range(10):
    ls[i] = str(i)

l = len(str(k))
cnt = 10
tag = 1
f = False
for j in range(k+1):
    s = ls[tag]
    for i in range(10):
        if  abs(int(s[-1])-i) <=1:
            ls[cnt] =  s+str(i)
            cnt+=1
        if cnt ==k+1:
            f = True
            break
    if f:
        break
    tag +=1
print(ls[-1])

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


def lun(n):
    found = []

    def _lun(top, m):
        if m == 0:
            found.append(int("".join(map(str, top))))
            return
        for t in (top[-1] - 1, top[-1], top[-1] + 1):
            if 0 <= t <= 9:
                _lun(top + [t], m - 1)

    for i in range(1, 10):
        _lun([i], n - 1)

    return found


d = 1
luns = []
while True:
    luns.extend(lun(d))
    if len(luns) >= K:
        break
    d += 1

print(luns[K - 1])

Solution (Python):



K = int(input())

list0 = ['0']
list1 = ['1']
list2 = ['2']
list3 = ['3']
list4 = ['4']
list5 = ['5']
list6 = ['6']
list7 = ['7']
list8 = ['8']
list9 = ['9']

an = 0


def AAA(list0,list1,list2,list3,list4,list5,list6,list7,list8,list9):
    nlist0 = [0]*(len(list0)+len(list1))
    nlist1 = [0]*(len(list0)+len(list1)+len(list2))
    nlist2 = [0]*(len(list1)+len(list2)+len(list3))
    nlist3 = [0]*(len(list2)+len(list3)+len(list4))
    nlist4 = [0]*(len(list3)+len(list4)+len(list5))
    nlist5 = [0]*(len(list4)+len(list5)+len(list6))
    nlist6 = [0]*(len(list5)+len(list6)+len(list7))
    nlist7 = [0]*(len(list6)+len(list7)+len(list8))
    nlist8 = [0]*(len(list7)+len(list8)+len(list9))
    nlist9 = [0]*(len(list8)+len(list9))
    
    for i in range(len(list0)):
        nlist0[i] = '0' + list0[i]
    for j in range(len(list1)):
        nlist0[len(list0)+j] = '0' + list1[j]
        
        
    for i in range(len(list0)):
        nlist1[i] = '1' + list0[i]
    for j in range(len(list1)):
        nlist1[len(list0)+j] = '1' + list1[j]
    for k in range(len(list2)):
        nlist1[len(list0)+len(list1)+k] = '1' + list2[k]
        
    
    for i in range(len(list1)):
        nlist2[i] = '2' + list1[i]
    for j in range(len(list2)):
        nlist2[len(list1)+j] = '2' + list2[j]
    for k in range(len(list3)):
        nlist2[len(list1)+len(list2)+k] = '2' + list3[k]
        

    for i in range(len(list2)):
        nlist3[i] = '3' + list2[i]
    for j in range(len(list3)):
        nlist3[len(list2)+j] = '3' + list3[j]
    for k in range(len(list4)):
        nlist3[len(list2)+len(list3)+k] = '3' + list4[k]
    
    for i in range(len(list3)):
        nlist4[i] = '4' + list3[i]
    for j in range(len(list4)):
        nlist4[len(list3)+j] = '4' + list4[j]
    for k in range(len(list5)):
        nlist4[len(list3)+len(list4)+k] = '4' + list5[k]
    
    for i in range(len(list4)):
        nlist5[i] = '5' + list4[i]
    for j in range(len(list5)):
        nlist5[len(list4)+j] = '5' + list5[j]
    for k in range(len(list6)):
        nlist5[len(list4)+len(list5)+k] = '5' + list6[k]
    
    for i in range(len(list5)):
        nlist6[i] = '6' + list5[i]
    for j in range(len(list6)):
        nlist6[len(list5)+j] = '6' + list6[j]
    for k in range(len(list7)):
        nlist6[len(list5)+len(list6)+k] = '6' + list7[k]
    
    for i in range(len(list6)):
        nlist7[i] = '7' + list6[i]
    for j in range(len(list7)):
        nlist7[len(list6)+j] = '7' + list7[j]
    for k in range(len(list8)):
        nlist7[len(list6)+len(list7)+k] = '7' + list8[k]
    
    for i in range(len(list7)):
        nlist8[i] = '8' + list7[i]
    for j in range(len(list8)):
        nlist8[len(list7)+j] = '8' + list8[j]
    for k in range(len(list9)):
        nlist8[len(list7)+len(list8)+k] = '8' + list9[k]
    
    for i in range(len(list8)):
        nlist9[i] = '9' + list8[i]
    for j in range(len(list9)):
        nlist9[len(list8)+j] = '9' + list9[j]
        
    return(nlist0,nlist1,nlist2,nlist3,nlist4,nlist5,nlist6,nlist7,nlist8,nlist9)


while an + len(list1)+len(list2)+len(list3)+len(list4)+len(list5)+len(list6)+len(list7)+len(list8)+len(list9) < K:
    an = an + len(list1)+len(list2)+len(list3)+len(list4)+len(list5)+len(list6)+len(list7)+len(list8)+len(list9)
    list0,list1,list2,list3,list4,list5,list6,list7,list8,list9 = AAA(list0,list1,list2,list3,list4,list5,list6,list7,list8,list9)

nK = K - an
if len(list1) >= nK:
    ans = list1[nK-1]
    nK = 10**8
else:
    nK = nK - len(list1)

if len(list2) >= nK:
    ans = list2[nK-1]
    nK = 10**8
else:
    nK = nK - len(list2)

if len(list3) >= nK:
    ans = list3[nK-1]
    nK = 10**8
else:
    nK = nK - len(list3)

if len(list4) >= nK:
    ans = list4[nK-1]
    nK = 10**8
else:
    nK = nK - len(list4)

if len(list5) >= nK:
    ans = list5[nK-1]
    nK = 10**8
else:
    nK = nK - len(list5)

if len(list6) >= nK:
    ans = list6[nK-1]
    nK = 10**8
else:
    nK = nK - len(list6)
    
if len(list7) >= nK:
    ans = list7[nK-1]
    nK = 10**8
else:
    nK = nK - len(list7)

if len(list8) >= nK:
    ans = list8[nK-1]
    nK = 10**8
else:
    nK = nK - len(list8)

if len(list9) >= nK:
    ans = list9[nK-1]
    nK = 10**8
else:
    nK = nK - len(list9)
    
    
print(int(ans))

Solution (Python):
K=int(input())
x=[0]*11
p=0
def f(p):
    if x[p]<9:
        x[p]+=1
        g(p)
    else:
        p+=1
        x[:p+1]=[0]*p+[1]
    return p
def g(p):
    y=x[p]
    for i in range(p-1,-1,-1):
        y=max(y-1,0)
        x[i]=y
for i in range(K):
    z=0
    if p==0:
        p=f(p)
    else:
        for q in range(p):
            if x[q]<x[q+1]+1 and x[q]<9:
                x[q]+=1
                g(q)
                z=1
                break
        if z==0:
            p=f(p)
while x[-1]==0:
    x.pop()
print("".join(reversed([str(n) for n in x])))

Solution (Python):
k = int(input())
num = {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]}
lun = [[1,2,3,4,5,6,7,8,9]]
lun_len = sum([len(l) for l in lun])
while lun_len < k:
    new_lun=[]
    for l in lun[-1]:
        for n in num[int(str(l)[-1])]:
            a=int(str(l)+str(n))
            new_lun.append(a)
    lun.append(new_lun)
    lun_len = sum([len(l) for l in lun])

for l in lun:
    if len(l)>k:
        print(l[k-1])
    else:
        k-=len(l)

Solution (Python):
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

K=one_int()



def solve(start, goal, lists):
    ret_lists=[]
    
    for i in lists:
        str_i = str(i)
        t = int(str_i[-1])
        
        if t==0:
            ret_lists.append(i*10)
            start+=1
            if start==goal:
                return ret_lists, start
            
            ret_lists.append(i*10+1)
            start+=1
            if start==goal:
                return ret_lists, start

        elif t==9:
            ret_lists.append(i*10+8)
            start+=1
            if start==goal:
                return ret_lists, start
            
            ret_lists.append(i*10+9)
            start+=1
            if start==goal:
                return ret_lists, start
        
        else:
            for s in range(-1,2):
                ret_lists.append(i*10+int(t)+s)
                start+=1
                if start==goal:
                    return ret_lists, start
  
    return ret_lists, start

if K>9:
    lists = [i for i in range(1,10)]
    start = 9
    while True:
        lists, start = solve(start, K, lists)
        if K<=start:
            print(lists[-1])
            break
else:
    print(K)

Solution (Python):
n = int(input())
if n < 10:
    print(n)
else:
    n -= 10
    num = [1, 0]
    while n:
        i = len(num)-1
        while i > 0 and (num[i] == 9 or num[i] > num[i-1]):
            i -= 1
        if i == 0 and num[0] == 9:
            num = [1] + [0]*len(num)
        else:
            num[i] += 1
            for j in range(i+1, len(num)):
                num[j] = max(num[j-1] - 1, 0)
        n -= 1
        
    print(''.join(map(str, num)))

Solution (Python):
c = 0
K = int(input())
for i in range(1,10):
    c += 1
    if c == K:
        print(i)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        c += 1
        if c == K:
            print(10*i+j)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            c += 1
            if c == K:
                print(100*i+10*j+k)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                c += 1
                if c == K:
                    print(1000*i+100*j+10*k+l)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                for m in range(max(l-1,0),min(l+2,10)):
                    c += 1
                    if c == K:
                        print(10000*i+1000*j+100*k+10*l+m)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                for m in range(max(l-1,0),min(l+2,10)):
                    for n in range(max(m-1,0),min(m+2,10)):
                        c += 1
                        if c == K:
                            print(100000*i+10000*j+1000*k+100*l+10*m+n)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                for m in range(max(l-1,0),min(l+2,10)):
                    for n in range(max(m-1,0),min(m+2,10)):
                        for o in range(max(n-1,0),min(n+2,10)):
                            c += 1
                            if c == K:
                                print(1000000*i+100000*j+10000*k+1000*l+100*m+10*n+o)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                for m in range(max(l-1,0),min(l+2,10)):
                    for n in range(max(m-1,0),min(m+2,10)):
                        for o in range(max(n-1,0),min(n+2,10)):
                            for q in range(max(o-1,0),min(o+2,10)):
                                c += 1
                                if c == K:
                                    print(10000000*i+1000000*j+100000*k+10000*l+1000*m+100*n+10*o+q)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                for m in range(max(l-1,0),min(l+2,10)):
                    for n in range(max(m-1,0),min(m+2,10)):
                        for o in range(max(n-1,0),min(n+2,10)):
                            for q in range(max(o-1,0),min(o+2,10)):
                                for t in range(max(q-1,0),min(q+2,10)):
                                    c += 1
                                    if c == K:
                                        print(100000000*i+10000000*j+1000000*k+100000*l+10000*m+1000*n+100*o+10*q+t)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                for m in range(max(l-1,0),min(l+2,10)):
                    for n in range(max(m-1,0),min(m+2,10)):
                        for o in range(max(n-1,0),min(n+2,10)):
                            for q in range(max(o-1,0),min(o+2,10)):
                                for t in range(max(q-1,0),min(q+2,10)):
                                    for y in range(max(t-1,0),min(t+2,10)):
                                        c += 1
                                        if c == K:
                                            print(1000000000*i+100000000*j+10000000*k+1000000*l+100000*m+10000*n+1000*o+100*q+10*t+y)

Solution (Python):
K=int(input())
A=["1","2","3","4","5","6","7","8","9"]
B=[]
C=A[:]
count=9
if(K<10):
  print(K)
else:
  while(count<K):
    B=[]
    for i in range(len(C)):
      if(int(C[i][len(C[i])-1])==0):
        B.append(C[i]+str(0))
        B.append(C[i]+str(1))
        count+=2
      elif(int(C[i][len(C[i])-1])>0 and int(C[i][len(C[i])-1])<9):
        B.append(C[i]+str(int(C[i][len(C[i])-1])-1))
        B.append(C[i]+str(int(C[i][len(C[i])-1])))
        B.append(C[i]+str(int(C[i][len(C[i])-1])+1))
        count+=3
      else:
        B.append(C[i]+str(8))
        B.append(C[i]+str(9))
        count+=2
    C=B[:]
    A.extend(B)
  print(A[K-1])

Solution (Python):
z = int(input())
l = []
for i in range(1,10):
    l.append(i)
    for j in range(max(0,i-1),min(10,i+2)):
        l.append(int(str(i)+str(j)))
        for k in range(max(j-1,0),min(10,j+2)):
            l.append(int(str(i)+str(j)+str(k)))
            for m in range(max(k-1,0),min(10,k+2)):
                l.append(int(str(i)+str(j)+str(k)+str(m)))
                for n in range(max(m-1,0),min(10,m+2)):
                    l.append(int(str(i)+str(j)+str(k)+str(m)+str(n)))
                    for o in range(max(n-1,0),min(10,n+2)):
                        l.append(int(str(i)+str(j)+str(k)+str(m)+str(n)+str(o)))
                        for p in range(max(o-1,0),min(10,o+2)):
                            l.append(int(str(i)+str(j)+str(k)+str(m)+str(n)+str(o)+str(p)))
                            for q in range(max(p-1,0),min(10,p+2)):
                                l.append(int(str(i)+str(j)+str(k)+str(m)+str(n)+str(o)+str(p)+str(q)))
                                for r in range(max(q-1,0),min(10,q+2)):
                                    l.append(int(str(i)+str(j)+str(k)+str(m)+str(n)+str(o)+str(p)+str(q)+str(r)))
                                    for s in range(max(r-1,0),min(10,r+2)):
                                        l.append(int(str(i)+str(j)+str(k)+str(m)+str(n)+str(o)+str(p)+str(q)+str(r)+str(s)))

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

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

if K <= 9 :
    print(lun[K])
else :
    def dfs(digit, max_digit, cur, K) :
        if digit == max_digit :
            lun.append( "".join(cur) )
            if len(lun) == K :
                return True
            return False
        elif digit > max_digit :
            return False

        c = int(cur[-1])
        for i in [-1,0,1] :
            if c+i < 0 or c+i > 9 :
                continue
            cur.append(str(c+i) )
            if dfs(digit+1, max_digit, cur, K) :
                return True
            cur.pop()
        return False

    max_digit = 2
    stop = False
    while True :
        for i in range(1, 10) :
            cur = [str(i)]
            if dfs(1, max_digit, cur, K+1) :
                stop = True
                break 
        if stop :
            break 
        max_digit += 1

    print(lun[-1])

Solution (Python):
K = int(input())
last_ind = 0
li =[1,2,3,4,5,6,7,8,9]
length =0
while K>len(li):
    new_li = li[length:len(li)]
    length = len(li)
    for l in new_li:
        matsubi = int(list(str(l))[-1])
        if matsubi == 0:
            li.append(int(str(l)+str(matsubi)))
            li.append(int(str(l)+str(matsubi+1)))
        elif matsubi == 9:
            li.append(int(str(l)+str(matsubi-1)))
            li.append(int(str(l)+str(matsubi)))
        else:
            li.append(int(str(l)+str(matsubi-1)))
            li.append(int(str(l)+str(matsubi)))
            li.append(int(str(l)+str(matsubi+1)))
        if len(li)>K:
            break
        
print(li[K-1])

Solution (Python):
def main():
    K=int(input())
    total=[9, 35, 110, 327, 956, 2782, 8089, 23527, 68468, 199368]
    if K<10:
        print(K)
    else:
        for i in range(9):
            if total[i]<K and total[i+1]>=K:
                a=[1,2,3,4,5,6,7,8,9]
                for j in range(i+1):
                    b=[]
                    for k in range(len(a)):
                        if a[k]%10==0:
                            b.append(10*a[k])
                            b.append(10*a[k]+1)
                        elif a[k]%10==9:
                            b.append(10*a[k]+8)
                            b.append(10*a[k]+9)
                        else:
                            b.append(10*a[k]+a[k]%10-1)
                            b.append(10*a[k]+a[k]%10)
                            b.append(10*a[k]+a[k]%10+1)
                    a,b=b,a
                print(a[K-total[i]-1])
if __name__=="__main__":
    main()

Solution (Python):
import itertools
def addLunLun(str_num):
    last_digit = int(str_num[len(str_num)-1:])
    if last_digit == 0:
        return [str_num+"0",str_num+"1"]
    elif last_digit == 9:
        return [str_num+"8",str_num+"9"]
    else:
        return [str_num + str(last_digit-1),str_num + str(last_digit),str_num + str(last_digit+1)]
    
digits1 = [str(i) for i in range(1,10)]
digits2 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits1]))
digits3 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits2]))
digits4 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits3]))
digits5 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits4]))
digits6 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits5]))
digits7 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits6]))
digits8 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits7]))
digits9 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits8]))
digits10 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits9]))
index = digits1 + digits2 + digits3 + digits4 + digits5 + digits6 + digits7 + digits8 + digits9 + digits10
K = int(input())
print(index[K-1])

Solution (Python):
k=int(input())
if k<9:print(k);exit()
t=[i for i in range(1,10)]
c=9
while c<k:
  a=t.pop(0)
  for i in range(max(0,a%10-1),min(10,a%10+2)):
    t.append(a*10+i)
    c+=1
print(t[-1-c+k])

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

    MAX = 10

    def search(base):
        if len(base) == MAX:
            
            return [base]
        else:
            result = [base]
            last = base[-1]
            if last != '9':
                
                result.extend(search(base + str(int(last) + 1)))
            if last != '0':
                
                result.extend(search(base + str(int(last) - 1)))
            
            result.extend(search(base + last))
            return result

    runrun = []

    for i in range(0, 10):
        el = search(str(i))
        
        runrun.extend(el)

    runrun_i = list(map(int, list(map(lambda x: x[::-1], runrun))))
    runrun_u = list(set(runrun_i))
    runrun_s = sorted(runrun_u)

    

    print(runrun_s[K])


if __name__ == '__main__':
    main()

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




base = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
result = [1, 2, 3, 4, 5, 6, 7, 8, 9]


def make_lun_lun(tempresult, n):
    stemp = []
    itemp = []
    if n == 0:
        return
    for r in tempresult:
        sa = r[len(r) - 1]
        ia = int(r[len(r) - 1])
        
        if ia - 1 > -1:
            stemp.append(r + str(ia - 1))
            itemp.append(int(r + str(ia - 1)))
        if ia + 1 < 10:
            stemp.append(r + str(ia + 1))
            itemp.append(int(r + str(ia + 1)))
        stemp.append(r + sa)
        itemp.append(int(r + sa))
    result.extend(itemp)
    make_lun_lun(stemp, n - 1)


make_lun_lun(base, 9)

print(sorted(result)[K - 1])

Solution (Python):
K = int(raw_input())
L = []

def dfs(n, m, s):
    if n <= s and s <= m:
        L.append(s)

    if s == 0 or s > m:
        return

    ld = s % 10
    s0 = s*10 + ld-1
    s1 = s*10 + ld
    s2 = s*10 + ld+1

    if ld == 0:
        dfs(n, m, s1)
        dfs(n, m, s2)
    elif ld == 9:
        dfs(n, m, s0)
        dfs(n, m, s1)
    else:
        dfs(n, m, s0)
        dfs(n, m, s1)
        dfs(n, m, s2)

for i in range(10):
    dfs(0, 10**10, i)

A = sorted(L)
print A[K]

Solution (Python):
kk = int(input())
if kk < 10:
    print(kk)
    exit()


dp = [[0] * 10 for _ in range(15)]
dp[0] = [1] * 10
for i in range(14):
    
    for j in range(10):
        for k in range(-1, 2):
            if not (0 <= j + k < 10):
                continue
            dp[i + 1][j + k] += dp[i][j]

a = 0
for i in range(15):
    if a+sum(dp[i][1:]) >= kk:
        break
    a += sum(dp[i][1:])

ii = i


for j in range(1, 10):
    if a + dp[i][j] >= kk:
        kk -= a
        break
    a += dp[i][j]

ans = j
for i in reversed(range(ii)):
    a = 0
    for k in range(-1, 2):
        if not (0 <= j + k < 10):
            continue
        if a + dp[i][j + k] >= kk:
            kk -= a
            j = j + k
            ans = ans * 10 + j

            break
        a += dp[i][j + k]


print(ans)

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

def calc(keta, num):
    global count
    if keta == 0:
        if num[-1] == "9":
            count += 1
            if count == K:
                print(num + str(int(num[-1]) - 1))
                quit()
            count += 1
            if count == K:
                print(num + str(int(num[-1])))
                quit()
        elif num[-1] == "0":
            count += 1
            if count == K:
                print(num + str(int(num[-1])))
                quit()
            count += 1
            if count == K:
                print(num + str(int(num[-1]) + 1))
                quit()
        else:
            count += 1
            if count == K:
                print(num + str(int(num[-1]) - 1))
                quit()
            count += 1
            if count == K:
                print(num + str(int(num[-1])))
                quit()
            count += 1
            if count == K:
                print(num + str(int(num[-1]) + 1))
                quit()
    else:
        if num[-1] == "9":
            calc(keta-1,num+str(int(num[-1]) - 1))
            calc(keta-1,num+str(int(num[-1])))
        elif num[-1] == "0":
            calc(keta-1,num+str(int(num[-1])))
            calc(keta-1,num+str(int(num[-1]) + 1))
        else:
            calc(keta-1,num+str(int(num[-1]) - 1))
            calc(keta-1,num+str(int(num[-1])))
            calc(keta-1,num+str(int(num[-1]) + 1))

if K < 10:
    print(K)
    quit()

while(True):
    for i in range(10000):
        for k in range(1,10):
            calc(i, str(k))

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def foo(l,m):
    if m==0:
        return 1
    sm = foo(l,m-1)
    if l<9:
        sm += foo(l+1,m-1)
    if l>0:
        sm += foo(l-1,m-1)
    return sm

d = [[0]*10 for i in range(11)]
for m in range(11):
    for l in range(10):
        d[m][l] = foo(l,m)




k = inn()
sm = 0
ans = []
for m in range(11):
    for l in range(1,10):
        sm += d[m][l]
        if sm>=k:
            break
    if sm>=k:
        break

ans.append(l)
sm -= d[m][l]
for n in range(m-1,-1,-1):
    for ll in range(max(0,l-1), min(9,l+1)+1):
        sm += d[n][ll]
        if sm>=k:
            break
    sm -= d[n][ll]
    ans.append(ll)
    l = ll

print(''.join([str(x) for x in ans]))

Solution (Python):
k=int(input())
l=[1,2,3,4,5,6,7,8,9]
t=[1,2,3,4,5,6,7,8,9]

while len(l)<k:
    t2=[]
    for i in t:
        m=i%10
        if m != 0:
            t2.append(i*10+(m-1))
        t2.append(i*10 + m)
        if m != 9:
            t2.append(i*10+(m+1))
    l.extend(t2)
    t=t2
print(l[k-1])

Solution (Python):
k = int(input())
lunluns = list(map(str, range(1,10)))
new = list(map(str, range(1,10)))
new_fueta = 9
end = False
while len(lunluns) < k:
  new_new_fueta = 0
  for x in lunluns[-new_fueta:]:
    str_x = str(x)
    if str_x[-1] == '0':
      lunluns += [int(str_x+'0'),int(str_x+'1')]
      new_new_fueta += 2
    elif str_x[-1] == '9':
      lunluns += [int(str_x+'8'),int(str_x+'9')]
      new_new_fueta += 2
    else:
      l = int(str_x[-1])
      lunluns += [int(str_x+str(l-1)), int(str_x+str(l)), int(str_x+str(l+1))]
      new_new_fueta += 3
  if end:
    break
  new_fueta = new_new_fueta
print(lunluns[k-1])

Solution (Python):
count = 0


def dfs(num):
    global count
    if len(str(num)) == 10:
        return
    else:
        tmp = int(str(num)[len(str(num))-1])
        for j in range(tmp-1, tmp+2):
            if 0 <= j <= 9:
                out = int(str(num) + str(j))
                ans.append(out)
                count += 1
                dfs(out)


if __name__ == "__main__":
    k = int(input())

    

    ans = list()

    for i in range(1, 10):
        ans.append(i)
        count += 1
        dfs(i)

    ans.sort()

    print(ans[k-1])

Solution (Python):
k=int(input())
if k==1:
  print(1)
  exit()
if k==10:
  print(10)
  exit()
if k==36:
  print(100)
  exit()
if k==111:
  print(1000)
  exit()
if k==328:
  print(10000)
  exit()
if k==957:
  print(100000)
  exit()
if k==2783:
  print(1000000)
  exit()
if k==8090:
  print(10000000)
  exit()
if k==23528:
  print(100000000)
  exit()
if k==68469:
  print(1000000000)
  exit()
k=k-1
A=[[[1],[2],[3],[4],[5],[6],[7],[8],[9]]]+[[] for i in range(10)]
a=[-1,0,1]
B=[0]
for i in range(10):
  for j in A[i]:
    for s in range(3):
      if j[-1]==0 and s==0:
        continue
      if j[-1]==9 and s==2:
        continue
      A[i+1].append(j+[j[-1]+a[s]])
  B.append(B[-1]+len(A[i]))
i=0
while k>B[i]:
  i=i+1
for t in range(len(A[i-1][k-B[i-1]])):
  print(A[i-1][k-B[i-1]][t],end="")