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

base_runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
test_num = max(base_runrun) + 1

def check_runrun(num):
    runrun_flg = True
    str_num = str(num)
    for i in range(len(str_num)-1):
        if abs(int(str_num[i]) - int(str_num[i+1]))>1:
            runrun_flg = False
            break
    return runrun_flg

def check_ceil(num):
    str_num = str(num)
    ceil_digit = None
    for i in range(len(str_num)-1):
        tmp = int(str_num[i]) - int(str_num[i+1])
        if tmp >1:
            ceil_digit = i + 1 
            nine = False
        elif tmp < -1:
            ceil_digit = i + 1 
            nine = True
            break
    if ceil_digit is not None:
        if nine:
            num_seq = ''
            for _ in range(len(str_num)-ceil_digit):
                num_seq = num_seq + '9'
            str_num = str_num[:ceil_digit] + num_seq
            str_num = str(int(str_num)+1)
        else:
            num_seq = str(int(str_num[ceil_digit-1])-1)
            for _ in range(len(str_num)-ceil_digit-1):
                num_seq = num_seq + '0'
            str_num = str_num[:ceil_digit] + num_seq
    return int(str_num)


while K > len(base_runrun):
    runrun_flg = check_runrun(test_num)
    if runrun_flg:
        base_runrun.append(test_num)
        test_num += 1
    else:
        test_num = check_ceil(test_num)
print(base_runrun[K-1])

Solution (Python):
from collections import deque
k=int(input())
nums=[1,2,3,4,5,6,7,8,9]
lst=deque()
for j in nums:
  d=deque()
  d.append(j)
  while len(d)<10**5:
    num=d.popleft()
    lst.append(num)
    s=str(num)
    l=len(s)
    t=int(s[l-1])
    if 1<=t<=8:
      d.append(s+str(t-1))
      d.append(s+str(t))
      d.append(s+str(t+1))
    if t==0:
      d.append(s+str(0))
      d.append(s+str(1))
    if t==9:
      d.append(s+str(8))
      d.append(s+str(9))

Lst=list(lst)
Lst=list(map(int,Lst))
Lst.sort()
print(Lst[k-1])

Solution (Python):

ans = [0] * 10
ans[1] = '1'
for i in range(2, 10):
    ans[i] = str(i)
alpha = "0123456789"
def dfs(s):
    if len(s) == N:
        ans.append(s)
        if len(ans) >= 100001:
            return
    else:
        for c in range(int(s[-1])-1,int(s[-1])+2):
            if c >= 0:
                dfs(s+str(c))
            if c == 9:
                break
K = int(input())
N = 2
while len(ans) < 100001:
    for i in range(1, 10):
        dfs(str(i))
        if len(ans) >= 100001:
            break
    N+=1

print(ans[K])

Solution (Python):
N=int(input())
list = []

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

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

print(list[N-1])

Solution (Python):
from collections import deque
li=[i for i in range(1,10)]
def bfs(K):
    d=deque()
    for i in range(1,10):
        d.append(str(i))
    while(len(li)<K):
        s=d[0]
        d.popleft()
        now=[int(s+s[-1])]
        if(s[-1]!='0'):
            now.append(int(s+str(int(s[-1])-1)))
        if(s[-1]!='9'):
            now.append(int(s+str(int(s[-1])+1)))
        now.sort()
        for i in range(len(now)):
            li.append(now[i])
            d.append(str(now[i]))
K=int(input())
bfs(K)
print(li[K-1])

Solution (Python):
import numpy as np
K=int(input())

n=np.zeros((10,11),dtype=int)
for i in range(9):
	n[i+1,1]=1
	n[i+1,2]=3
n[9,2]=2

for i in range(3,11):
	n[1,i]=n[2,i-1]+np.sum(n[1,:])+1
	n[2,i]=n[1,i-1]+n[2,i-1]+n[3,i-1]
	n[3,i]=n[4,i-1]+n[2,i-1]+n[3,i-1]
	n[4,i]=n[4,i-1]+n[5,i-1]+n[3,i-1]
	n[5,i]=n[4,i-1]+n[5,i-1]+n[6,i-1]
	n[6,i]=n[5,i-1]+n[6,i-1]+n[7,i-1]
	n[7,i]=n[7,i-1]+n[8,i-1]+n[6,i-1]
	n[8,i]=n[7,i-1]+n[8,i-1]+n[9,i-1]
	n[9,i]=n[8,i-1]+n[9,i-1]

i=1
j=1

def ninecheck(i,j,K,ans):
	for k in range(2):
		K-=n[i-1+k,j]
		if K<=0:
			K+=n[i-1+k,j]
			ans+=(i-1+k)*(10**(j-1))
			if j==1:
				a=ans
				return a
			j-=1
			i=i-1+k
			if i==1:
				a=onecheck(i,j,K,ans)
				return a
			elif i==9:
				a=ninecheck(i,j,K,ans)
				return a
			else:
				a=normalcheck(i,j,K,ans)
				return a

def onecheck(i,j,K,ans):
	K-=1
	if K==0:
		a=ans
		return a
	for k in range(1,j+1):
		K-=n[1,k]
		if K<=0:
			K+=n[1,k]
			ans+=10**(k-1)
			j=k
			if j==1:
				a=ans
				return a
			j-=1
			a=onecheck(i,j,K,ans)
			return a
	i=2
	ans+=i*(10**(j-1))
	j-=1
	a=normalcheck(i,j,K,ans)
	return a

def normalcheck(i,j,K,ans):
	for k in range(3):
		K-=n[i-1+k,j]
		if K<=0:
			K+=n[i-1+k,j]
			ans+=(i-1+k)*(10**(j-1))
			if j==1:
				a=ans
				return a
			j-=1
			i=i-1+k
			if i==1:
				a=onecheck(i,j,K,ans)
				return a
			elif i==9:
				a=ninecheck(i,j,K,ans)
				return a
			else:
				a=normalcheck(i,j,K,ans)
				return a



ans=0
while True:
	K-=n[i,j]
	if K<=0:
		ans+=i*(10**(j-1))
		K+=n[i,j]
		if j==1:
			b=ans
			break
		j-=1
		if i==1:
			b=onecheck(i,j,K,ans)
			break
		elif i==9:
			b=ninecheck(i,j,K,ans)
			break
		else:
			b=normalcheck(i,j,K,ans)
			break
	if i==9:
		i=1
		j+=1
	else:
		i+=1
		continue




print(b)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    base = [i+1 for i in range(9)]
    m = 3234566667+10000
    
    while len(base) < N:
        use = base
        for num in base:
            st = str(num)
            if st[-1] == "0":
                if int(st+"0") <= m:
                    use.append(int(st+"0")) 
                if int(st+"1") <= m:
                    use.append(int(st+"1"))
            elif st[-1] == "9":
                if int(st+"8") <= m:
                    use.append(int(st+"8"))
                if int(st+"9") <= m:
                    use.append(int(st+"9"))
            else:
                s = int(st[-1])
                st = int(st)
                if st*10+s-1 <= m:
                    use.append(st*10+s-1)
                if st*10+s <= m:
                    use.append(st*10+s)
                if st*10+s+1 <= m:
                    use.append(st*10+s+1)
        base = use
        
    print(base[N-1])
    
if __name__ == "__main__":
    main()

Solution (Python):
k = int(input())
a = []

def lun(x,y,z): 
  if z == 1:
    if x != 0:
      a.append(y+x-1)
    a.append(y+x)
    if x != 9:
      a.append(y+x+1)
  else:
    if x != 0: 
      b = y + (x-1)*(10**(z-1))
      lun(x-1,b,z-1)
    b = y + x*(10**(z-1))
    lun(x,b,z-1)
    if x!= 9:
      b = y + (x+1)*(10**(z-1))
      lun(x+1,b,z-1)


for i in range(1,10):
  a.append(i)

for j in range(2,11):
  for i in range(1,10):
    lun(i,i*(10**(j-1)),j-1)

print(a[k-1])

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

table = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in table:
	if len(table) > K:
		break
	x = i % 10
	for j in range(max(0, x - 1), min(x + 2, 10)):
		table.append(i * 10 + j)

print(table[K - 1])

Solution (Python):
import itertools

K = int(input())

keta_list = [['1', '2', '3', '4', '5', '6', '7', '8', '9']]
keta = 1
count = len(keta_list[0])

def create_lunlun():
    global keta
    global keta_list
    global count

    base_num = keta_list[keta - 1]

    new_keta_list = []

    for num in base_num:
        if num[-1] >= '1' and num[-1] <= '8':
            new_keta_list.append(num + str(int(num[-1])-1))
            new_keta_list.append(num + num[-1])
            new_keta_list.append(num + str(int(num[-1])+1))
        elif num[-1] == '0':
            new_keta_list.append(num + num[-1])
            new_keta_list.append(num + str(int(num[-1])+1))
        else:
            new_keta_list.append(num + str(int(num[-1])-1))
            new_keta_list.append(num + num[-1])

    keta_list.append(new_keta_list)
    keta += 1

    count += len(new_keta_list)
    if count >= 10**5:
        return
    
    create_lunlun()


create_lunlun()

keta_list = list(itertools.chain.from_iterable(keta_list))

print(keta_list[K-1])

Solution (Python):
k = int(input())
if k <= 12:
    print(k)
    exit()

cnt = []
cnt.append([[0]*10 for i in range(10)])
cnt.append([[1 if i == j else 0 for j in range(10)] for i in range(10)])


total = 9

loop = True
x = 1
head = 1
while loop:
    x += 1
    cnt.append([[0] * 10 for _ in range(10)])
    for h in range(0, 10):
        head_total = 0
        head = h
        cnt[x][h][0] = cnt[x - 1][h][0] + cnt[x - 1][h][1]
        head_total += cnt[x][h][0]
        for i in range(1, 9):
            cnt[x][h][i] = cnt[x - 1][h][i - 1] + \
                cnt[x - 1][h][i] + cnt[x - 1][h][i + 1]
            head_total += cnt[x][h][i]

        cnt[x][h][9] = cnt[x - 1][h][8] + cnt[x - 1][h][9]
        head_total += cnt[x][h][9]
        if h == 0:
            continue

        if total + head_total >= k:
            loop = False
            break
        else:
            total += head_total


result = head

for i in range(x - 1, 0, -1):

    for h in [head - 1, head, head + 1]:
        if h < 0 or 9 < h:
            continue
        t = sum(cnt[i][h])
        if total+t < k:
            total += t
        else:
            result = result * 10 + h
            head = h
            break
print(result)

Solution (Python):
import collections
k = int(input())
n = 10**10

li = list(range(1,10))
num_li = li[:]
q = collections.deque(li)
count = 0

for i in range(1,n):
    num = str(q.popleft())
    go = int(num[-1])
    if go != 0:
        numa = num + str(go - 1)
        num_li.append(int(numa))
        q.append(int(numa))
        count += 1
    numa = num + str(go)
    num_li.append(int(numa))
    q.append(int(numa))
    count += 1
    if go != 9:
        numa = num + str(go + 1)
        num_li.append(int(numa))
        q.append(int(numa))
        count += 1

    if count > k+1:
        break

print(num_li[k-1])

Solution (Python):
n=int(input())
if n<10: print(n); exit()
r=range
l=[[[] for _ in r(10)] for _ in r(10)]
l[0]=[[i] for i in r(10)]
c=9
for i in r(9):
  for j in r(10):
    for k in r(-1,2):
      if 0<=j+k<=9:
        for h in l[i][j+k]:
          if j: c+=1
          t=j*10**(i+1)+h
          l[i+1][j]+=[t]
          if c==n: print(t); exit()

Solution (Python):
import sys
k=int(input())
ans=[""]
for i in range(1,13):
    ans.append(i)
for i in range(1,8):
    a=10*(i+1)+(i)
    for j in range(3):
        ans.append(a)
        a+=1
ans.append(98)
ans.append(99)


if k<=35:
    print(ans[k])
else:
    def search(i,j):
        total=0
        if i==1:
            
            return 1
        for m in range(10):
            if abs(j-m)<=1:
                total+=search(i-1,m)
        return total
    def search2(i,j,anss):
        global plus,aaa
        if i==1:
            plus+=1
            
            
            
            if k==aaa+plus:
                
                print(anss)
            return 
        for m in range(10):
            if abs(j-m)<=1:
                search2(i-1,m,anss+str(m))
    num=[35] 
    for i in range(3,11): 
        for j in range(1,10): 
            count=search(i,j)
            num.append(num[-1]+count)
    
    ab=0
    while num[ab]<k:
        ab+=1
    
    rank=ab//9
    sento=ab%9
    if sento==0:
        sento=9
    
    
    aaa=num[ab-1]
    plus=0
    search2(3+rank,sento,str(sento))

Solution (Python):
k = int(input())
ok = 10**18
ng = 0
while ok-ng>1:
    mid = (ok+ng)//2
    s = list(map(int, list(str(mid))))
    n = len(s)
    dp = [[[0]*2 for i in range(10)] for j in range(n)]
    for i in range(1, s[0]):
        dp[0][i][0] = 1

    dp[0][s[0]][1] = 1
    for i in range(n-1):
        for d in range(1, 10):
            dp[i+1][d][0]+=1
        for d in range(10):
            if d+1 < 10:
                dp[i+1][d+1][0] += dp[i][d][0]
            if d-1 >= 0:
                dp[i+1][d-1][0] += dp[i][d][0]
            dp[i+1][d][0] += dp[i][d][0]
        if s[i]>0:
            if s[i+1] == s[i]-1:
                dp[i+1][s[i]-1][1]+=dp[i][s[i]][1]
            elif s[i+1]>s[i]-1:
                dp[i+1][s[i]-1][0]+=dp[i][s[i]][1]
        if s[i]<9:
            if s[i+1] == s[i]+1:
                dp[i+1][s[i]+1][1]+=dp[i][s[i]][1]
            elif s[i+1]>s[i]+1:
                dp[i+1][s[i]+1][0]+=dp[i][s[i]][1]
        if s[i+1] == s[i]:
            dp[i+1][s[i]][1]+=dp[i][s[i]][1]
        elif s[i+1]>s[i]:
            dp[i+1][s[i]][0]+=dp[i][s[i]][1]
    res = 0
    for d in range(10):
        res+=dp[n-1][d][0]+dp[n-1][d][1]
    if res>=k:
        ok = mid
    else:
        ng = mid

print(ok)

Solution (Python):
k = int(input())
n = 1
cnt = 0
flg = 0
while True:
  if flg == 1:
    n += 1
  flg = 0
  strn = str(n)
  if len(strn) == 1:
    cnt += 1
    flg = 1
  else:
    for s in range(len(strn)):
      if s == len(strn) - 1:
        cnt += 1
        flg = 1
      else:
        if abs(int(strn[s]) - int(strn[s+1])) > 1:
          if int(strn[s]) - int(strn[s+1]) > 1:
            new = ''
            for ss in range(len(strn)):
              if s+1 == ss:
                new += str(int(strn[s]) - 1)
              else:
                new += strn[ss]
            n = int(new)
          else:
            new = ''
            for ss in range(len(strn)):
              if s == ss:
                new += str(int(strn[s]) + 1)
              elif s+1 == ss:
                new += '0'
              else:
                new += strn[ss]
            n = int(new)
          break
          
    
  if cnt == k:
    print(n)
    break

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

def ff(s, i):
    for j in range(i+1, len(s)):
        
        if s[j-1] > 0:
            s[j] = s[j-1] - 1
        else:
            s[j] = 0
    return s

def next(s):
    ls = len(s)
    for i in range(ls-1, 0, -1):
        if s[i-1] >= s[i] and s[i] != 9:
            s[i] += 1
            
            return ff(s, i)
    if s[0] == 9:
        return [1] + ([0] * ls)
    else:
        s[0] += 1
        return ff(s, 0)

if k < 10:
    print(k)
    exit()

ans = [1,0]
for i in range(k - 10):
    ans = next(ans)

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

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




def construct(lunnum: str, depth: int, flag: bool):
    global l
    if depth == 0:
        l.add(int(lunnum))
        return
    
    m = int(lunnum[-1])
    if flag:
        
        for i in range(0, 10):
            construct(lunnum + str(i), depth - 1, i == 0)
    else:
        
        for i in set([max(0, m - 1), m, min(9, m + 1)]):
            construct(lunnum + str(i), depth - 1, False)



construct("0", 10, True)
ls = sorted(list(l))
print(ls[k])

Solution (Python):


def up(nums):
    if len(nums) == nums.count(9):
        nums = [1] + [0] * len(nums)
        return nums
    
    for i in list(reversed(range(len(nums)))):
        if nums[i] > nums[i-1] or nums[i] == 9:
            continue
        else:
            nums[i] += 1
            for j in range(i+1, len(nums)):
                if j == len(nums) - 1:
                    nums[j] = max(nums[j-1]-1, 0)
                else:
                    nums[j] = max(nums[j-1] - 1, 0)
            return nums
          
  
def main():
    k = int(input())
    if k < 10:
        print(k)
        return
    cnt = 11
    nums = [1, 0]
    while cnt <= k:
        cnt += 1
        nums = up(nums)
        
        
    print(''.join([str(num) for num in nums]))
        
    
        
  
if __name__ == '__main__':
    main()

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

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

def Judge1(number):
    letter=str(number)
    judge=1
    if number==1:
        judge=0
    elif letter[0]!='1':
        judge=0
    else:
        for i in range(1,len(letter)):
            if letter[i]!='0':
                judge=0
                break 
    return judge

def Judge9(number):
    letter=str(number)
    judge=1
    for i in range(len(letter)):
        if letter[i]!='9':
            judge=0
            break
    return judge

def generate(number):
    if Judge1(number)==1:
        return [number*10,number*10+1]
    elif Judge9(number)==1:
        return [number*10+8,number*10+9]
    else:
        letter=str(number)
        newnumber=int(letter+letter[-1])
        return [newnumber-1,newnumber,newnumber+1]

def Generate(L):
    A=[]
    for i in range(len(L)):
        A.extend(generate(L[i]))
    return A

def check(number):
    letter=str(number)
    judge=1
    for i in range(len(letter)-1):
        if abs(int(letter[i])-int(letter[i+1]))>1:
            judge=0
            break
    return judge

Ans=[G]
ANS=[1,2,3,4,5,6,7,8,9]
for x in range(9):
    N=Generate(Ans[-1])
    NN=[]
    for y in range(len(N)):
        if check(N[y])==1:
            NN.append(N[y])
    Ans.append(NN)
    ANS.extend(NN)





print(ANS[K-1])

Solution (Python):
from collections import deque

k = int(input())
n = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
q = deque(['0'])
cnt = 0
ans = []
while len(q):
    v = q.pop()
    
    if k + 1 == cnt:
        print(ans[-1])
        
        exit()
    check = int(v[-1])

    

    for plus in n:
        st = str(v) + str(plus)

        if str(st)[0] == '0' and str(st)[1] == '0':
            continue

        if len(st) > 12:
            continue

        if abs(check - plus) > 1 and len(st) != 2:
            
            continue
        cnt += 1
        if k + 1 == cnt:
            ans_show = ans[-1]
            for g in range(len(ans_show)):
                if g == 0 and ans_show[0] == '0':
                    pass
                else:
                    print(ans_show[g], end='')
            exit()
        
        ans.append(str(v) + str(plus))
        q.appendleft(st)

Solution (Python):
from bisect import bisect

k = int(input())
A = list(range(10))

if k <= 9:
    print(A[k])
    exit()


def is_1_keta(i):
    return len(str(i)) == 1


kouho = list(map(str, range(1, 10)))
kouho2 = list(map(str, range(1, 10)))
while True:
    ll = []
    for i in kouho:
        su = list(filter(is_1_keta, [int(i[-1]) - 1, int(i[-1]), int(i[-1]) + 1]))
        l = [str(i) + str(x) for x in su]
        A.extend(l)
        ll.extend(l)
    kouho = ll
    kouho2.extend(ll)
    if len(kouho2) > k:
        break

print(sorted(list(map(int, kouho2)))[k - 1])

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

lunlun = list(range(1, 10))
last_lunlun = lunlun
for j in range(9):
    new = []
    for l in last_lunlun:
        last = int(str(l)[-1])
        for i in [-1, 0, 1]:
            if last + i >= 0 and last + i < 10:
                new.append(10 * l + last + i)
    last_lunlun = new
    lunlun.extend(new)

lunlun.sort()

print(lunlun[K-1])

Solution (Python):

def resolve():
    import sys
    input = sys.stdin.readline
    k = int(input().rstrip())

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

    def judge(number_list, index, total):
        if index == len(number_list) - 2:  
            num = number_list[index]
            add_num = 2 if num in (0, 9) else 3
            if (total + add_num) < k:
                total += add_num
                return total
            else:
                if num == 0:
                    right_nums = [num, num + 1]
                elif num == 9:
                    right_nums = [num-1,num]
                else:
                    right_nums = [num-1,num,num+1]
                number_list[-1] = right_nums[k-total-1]
                
                print(*number_list,sep="")
                sys.exit()
        else:  
            num = number_list[index]
            if num == 0:
                right_nums = [num, num + 1]
            elif num == 9:
                right_nums = [num - 1, num]
            else:
                right_nums = [num - 1, num, num + 1]

            for right_num in right_nums:
                number_list[index+1] = right_num
                total = judge(number_list, index+1, total)
            return total

    total = 9
    num_list = [9]
    while True:
        num_list = [0 for _ in range(len(num_list)+1)]
        for left in [1,2,3,4,5,6,7,8,9]:
            num_list[0] = left
            
            total = judge(num_list, 0, total)




if __name__ == "__main__":
    resolve()

Solution (Python):
k=int(input())
L=[1,2,3,4,5,6,7,8,9]
Sz=['0']
Tz=[]
Sn=[1,2,3,4,5,6,7,8,9]
Tn=[]

i=9
while i<=k:
    for z in Sz:
        L.append(int('1'+z))
        i+=1
        Tn.append(int('1'+z))
        Tz.append('0'+z)
    Sz=[]
    Sz=Tz[:]
    Tz=[]
    
        
    for n in Sn:
        if int(str(n)[0])==1:
            Sz.append(str(int(str(n)[0])-1)+str(n))
            L.append(int(str(n)[0]+str(n)))
            L.append(int(str(int(str(n)[0])+1)+str(n)))
            Tn.append(int(str(n)[0]+str(n)))
            Tn.append(int(str(int(str(n)[0])+1)+str(n)))
            i+=2
        elif 2<=int(str(n)[0])<=8:
            L.append(int(str(int(str(n)[0])-1)+str(n)))
            L.append(int(str(n)[0]+str(n)))
            L.append(int(str(int(str(n)[0])+1)+str(n)))
            Tn.append(int(str(int(str(n)[0])-1)+str(n)))
            Tn.append(int(str(n)[0]+str(n)))
            Tn.append(int(str(int(str(n)[0])+1)+str(n)))
            i+=3
        else:    
            L.append(int(str(int(str(n)[0])-1)+str(n)))
            L.append(int(str(n)[0]+str(n)))
            Tn.append(int(str(int(str(n)[0])-1)+str(n)))
            Tn.append(int(str(n)[0]+str(n)))
            i+=2
    Sn=[]
    Sn=Tn[:]
    Tn=[]

LS=sorted(L)
print(LS[k-1])

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

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

for i in table:
	if len(table) > K:
		break
	x = i % 10
	if x != 0 and x != 9:
		for j in range(x - 1, x + 2):
			table.append(i * 10 + j)
	elif x == 0:
		for j in range(x, x + 2):
			table.append(i * 10 + j)
	else:
		for j in range(x - 1, x + 1):
				table.append(i * 10 + j)

print(table[K - 1])

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

def get_below(a):
    s = str(a)
    if len(s) == 1:
        return a
    else:
        ret = 0
        for i in range(len(s)):
            ret += sum(nums[i][1:])

        for i in range(1, int(s[0])):
            ret += nums[len(s)][i]

        def dfs(ss):
            
            if len(ss) == 1:
                return 1
            if int(ss[0]) > int(ss[1]) + 1:
                return 0
            elif int(ss[0]) == int(ss[1]) + 1:
                return dfs(ss[1:])
            elif int(ss[0]) == int(ss[1]):
                ret = 0
                if int(ss[1]) != 0:
                    ret += nums[len(ss) - 1][int(ss[1]) - 1]
                return ret + dfs(ss[1:])
            elif int(ss[0]) + 1 == int(ss[1]):
                ret = 0
                if int(ss[1]) >= 1:
                    ret += nums[len(ss) - 1][int(ss[1]) - 1]
                if int(ss[1]) >= 2:
                    ret += nums[len(ss) - 1][int(ss[1]) - 2]
                return ret + dfs(ss[1:])
            else:
                return nums[len(ss)][int(ss[0])]

        return ret + dfs(str(a))

if k <= 10:
    print(k)
else:
    nums = [[0] * 10 for _ in range(11)]
    nums[1] = [1] * 10

    for i in range(11):
        for j in range(10):
            if j != 0:
                nums[i][j] += nums[i-1][j-1]
            if j != 9:
                nums[i][j] += nums[i-1][j+1]
            nums[i][j] += nums[i-1][j]

    lo = 0
    hi = 10 ** 10
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if get_below(mid) - k >= 0:
            hi = mid
        else:
            lo = mid

    print(hi)

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

def count(idx, n):
    if idx==0:
        return 1
    if n==0:
        return count(idx-1, 1)+count(idx-1, 0)
    elif n==9:
        return count(idx-1, 9)+count(idx-1, 8)
    else:
        return count(idx-1, n-1)+count(idx-1, n)+count(idx-1, n+1)

lists = []
def count_2(idx, n, list_b):
    lis = list_b[:]
    lis.append(str(n))
    if idx==0:
        lists.append(int(''.join(lis)))
        return 1
    if n==0:
        count_2(idx-1, 1, lis)
        count_2(idx-1, 0, lis)
    elif n==9:
        count_2(idx-1, 9, lis)
        count_2(idx-1, 8, lis)
    else:
        count_2(idx-1, n-1, lis)
        count_2(idx-1, n, lis)
        count_2(idx-1, n+1, lis)

d = 0
now = 0
while 1:
    p = sum([count(d, i) for i in range(1, 10)])
    now += p
    if now>K:
        now -= p
        break
    d += 1

sump = 0
for i in range(1, 10):
    sump_old = sump
    sump += count(d, i)
    if sump+now>=K:
        break
count_2(d, i, [])
lists.sort()
if K<10:
    print(K)
else:
    print(lists[K-now-sump_old-1])

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

D=[0]*12
kt=0

def up(i):
    global kt
    u = 1
    while u:
        kt = max(kt, i)
        D[i] += u
        if D[i] >= 10:
            D[i] = 0
            u = 1
        else: u = 0
        i += 1

def down(i,d):
    for j in range(i, -1, -1):
        if d >= 1: d -= 1
        D[j] = d

for i in range(K):
    up(0)
    j = 0
    while j < kt:
        if abs(D[j] - D[j+1]) > 1:
            if D[j+1] < D[j]: up(j+1)
            D[j] = D[j+1] - 1
            if j > 0: down(j-1, D[j])
        j += 1

f = True
for d in reversed(D):
    if f and d==0: continue
    f = False
    print(d, end='')

Solution (Python):
from collections import deque

def generate():
    global que, cnt1, cnt2
    for i in range(cnt2):
        num = que.popleft()
        if 0 < int(num[-1]) < 9:
            for j in range(int(num[-1])-1, int(num[-1])+2, 1):
                que.append(num + str(j))
        elif int(num[-1]) == 0:
            que.append(num + '0')
            que.append(num + '1')
        else:
            que.append(num + '8')
            que.append(num + '9')
    cnt1 = cnt1 + cnt2
    cnt2 = len(que)

K = int(input())
cnt1 = 0
cnt2 = 9
que = deque(['1', '2', '3', '4', '5', '6', '7', '8', '9'])

if K <= 9:
    print(que[K-1])
    exit()

while True:
    generate()
    if K <= cnt1 + cnt2:
        print(que[K - cnt1 - 1])
        exit()

Solution (Python):
K = int(input())
global cnt
cnt = 9
def func(cur, d):
    global cnt
    c = cur % 10
    for i in range(0 if c==0 else c-1, 10 if c==9 else c+2):
        if d == 1:
            cnt += 1 
            if cnt == K:
                print(cur*10+i)
                exit()
        else:
            func(cur*10+i, d-1)

if K <= 9:
    print(K)
else:
    for d in range(2, 11):
        for i in range(1, 10):
            func(i, d-1)

Solution (Python):
def dp():
    cnt = []
    for i in range(10):
        cnt.append([0] * 10)
    for i in range(10):
        cnt[0][i] = 1
    for i in range(1, 10):
        for j in range(10):
            cnt[i][j] = 0
            for k in range(-1, 2):
                if 0 <= j+k and j+k < 10:
                    cnt[i][j] += cnt[i-1][j+k]
    return cnt


def main():
    k = int(input())
    cnt = dp()
    tot = [0] * 10
    for i in range(10):
        tot[i] = sum(cnt[i][1:])
    
    

    res = 0
    length = -1
    digit = -1
    for i in range(10):
        if tot[i] < k:
            k -= tot[i]
        else:
            length = i
            for j in range(1, 10):
                if k > cnt[i][j]:
                    k -= cnt[i][j]
                else:
                    digit = j
                    break
            break

    length -= 1
    res = digit
    while length >= 0:
        
        for i in range(-1, 2):
            
            if 0 <= digit + i and digit + i <= 9:
                if cnt[length][digit + i] >= k:
                    digit = digit + i
                    break
                else:
                    k -= cnt[length][digit + i]
        length -= 1
        
        res = res * 10 + digit
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
lunluns = []

def dfs(n, cur):
    global lunluns
    lunluns.append(int(n))
    if cur > 8:
        return
    if n[-1] == '0':
        dfs(n+'0', cur+1)
        dfs(n+'1', cur+1)
    elif n[-1] == '9':
        dfs(n+'8', cur+1)
        dfs(n+'9', cur+1)
    else:
        last = int(n[-1])
        dfs(n + str(last-1), cur+1)
        dfs(n + str(last), cur+1)
        dfs(n + str(last+1), cur+1)

for i in range(1,10):
    dfs(str(i), 0)

K = int(input())
lunluns.sort()
print(lunluns[K-1])

Solution (Python):
import collections
k = int(input())
que = collections.deque()
cnt = 9
for i in range(1, 10):
    que.append(str(i))
Lun = []
while True:
    if len(Lun) >= 10**5:
        
        break
    now = que.popleft()
    Lun.append(now)
    
    if now[-1] == '0':
        que.append(now + '0')
        que.append(now + '1')
        cnt += 2
    elif now[-1] == '9':
        que.append(now + '8')
        que.append(now + '9')
        cnt += 2
    else:
        que.append(now + str(int(now[-1]) - 1))
        que.append(now + str(int(now[-1])))
        que.append(now + str(int(now[-1]) + 1))
        cnt += 3

    

print(Lun[k-1])

Solution (Python):
def main():
    k = int(input())
    dp = [[1] * 10]
    count = 9
    while k > count:
        dp.append([])
        dp[-1].append(dp[-2][0] + dp[-2][1])
        for i in range(1, 9):
            dp[-1].append(dp[-2][i - 1] + dp[-2][i] + dp[-2][i + 1])
        dp[-1].append(dp[-2][8] + dp[-2][9])
        count += sum(dp[-1][1:])
    ans = []
    li = [count - sum(dp[-1][i:]) for i in range(11)]
    for i in range(1, 10):
        if li[i + 1] >= k:
            ans.append(i)
            c = li[i]
            break
    for li in reversed(dp[:-1]):
        for i in range(max(0, ans[-1] - 1), min(9, ans[-1] + 1) + 1):
            if c + li[i] >= k:
                ans.append(i)
                break
            c += li[i]

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


if __name__ == '__main__':
    main()

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

k = int(input())
S = []
def dfs(s):
  if len(s)<10:
    for i in range(-1, 2, 1):
      a = str(min(9, max(0, int(s[0])+i)))+s
      S.append(a)
      dfs(a)

for i in range(10):
  S.append(i)
  dfs(str(i))
S = sorted(set([int(s) for s in S]))
print(S[k])

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)

from collections import deque

def main():
    k = int(input())
    lst = []
    bfs("",k,lst)
    print(lst[k-1])


def bfs(s,k,lst=[]):
    d = deque()
    for c in "0123456789":
        d.append(c)
    while d:
        if len(lst) > k:
            return
        now = d.popleft()
        if now=="0":
            continue
        lst.append(now)
        for nxt in [int(now[-1])-1,int(now[-1]),int(now[-1])+1]:
            if nxt < 0 or nxt > 9:
                continue
            d.append(now+str(nxt))









if __name__ == '__main__':
    main()