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 sys import stdin,setrecursionlimit
k = int(stdin.readline().rstrip())
li = [i for i in range(1,10)]

def runrun(before,kazu):
    if before == 0:
        li.append(int(kazu+str(before+1)))
        li.append(int(kazu+str(before)))
    elif before == 9:
        li.append(int(kazu+str(before-1)))
        li.append(int(kazu+str(before)))
    else:
        li.append(int(kazu+str(before+1)))
        li.append(int(kazu+str(before-1)))
        li.append(int(kazu+str(before)))
    if len(kazu)+1 >= 10:
        return
    else:
        if before == 0:
            return runrun(before+1,kazu+str(before+1)),runrun(before,kazu+str(before))
        elif before == 9:
            return runrun(before-1,kazu+str(before-1)),runrun(before,kazu+str(before))
        else:
            return runrun(before+1,kazu+str(before+1)),runrun(before-1,kazu+str(before-1)),runrun(before,kazu+str(before))
for i in range(1,10):
    runrun(i,str(i))
li.sort()
print(li[k-1])

Solution (Python):
import sys
from string import digits

k = int(sys.stdin.readline().rstrip())

def main():
    r = k
    if r <= 9:
        print(digits[r])
        return
    res = list(digits[1:])
    r -= 9
    d = set(digits)
    while True:
        nex = []
        for n in res:
            o = ord(n[-1])
            for i in range(-1, 2):
                tail = chr(o+i)
                if tail in d:
                    nex.append(n+tail)
                    r -= 1
                    if r == 0:
                        print(nex[-1])
                        return
        res = nex.copy()    

if __name__ ==  '__main__':
    main()

Solution (Python):
n = int(input())
a = [0,1,2,3,4,5,6,7,8,9]
count = 9
idx = 1
while count < n:
  pick = a[idx]
  if pick % 10 == 0:
    a.extend([pick*10+0, pick*10+1])
    count += 2
  elif pick % 10 == 9:
    a.extend([pick*10+8, pick*10+9])
    count += 2
  else:
    lsn = pick % 10
    a.extend([pick*10+lsn-1, pick*10+lsn, pick*10+lsn+1])
    count += 3
  idx += 1
print(a[n])

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

while len(a)<=100000:
    past=len(a)
    for i in range(now,len(a)):
        if a[i]%10==0:
            a.append(a[i]*10+0)
            a.append(a[i]*10+1)
        elif a[i]%10==9:
            a.append(a[i]*10+8)
            a.append(a[i]*10+9)
        else:
            a.append(a[i]*10+a[i]%10-1)
            a.append(a[i]*10+a[i]%10)
            a.append(a[i]*10+a[i]%10+1)
    now=past

print(a[k-1])

Solution (Python):
import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    K = int(input())
    
    q = queue.Queue()
    for i in range(1, 10):
        q.put(i)

    r = 9
    for k in range(K):
        a = q.get()
        l = max(0, a % 10 - 1)
        ll = min(10, a % 10 + 2)
        for b in range(l, ll):
            q.put(a * 10 + b)
            r += 1
    print(a)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

retsu = int(input())

def dfs( s , n ):
    i = 0
    if len(s) == n:
        ans.append(s)
        return
    else:
        a = int(s[len(s)-1])
        for j in range(3):
            if a+j-1 >= 0 and a+j-1 <= 9:
                dfs( s + str(a+j-1) , n )
                
ans = []
for i in range(1,11):
    for j in range(10):
        a = str(j)
        dfs( a , i )
        
ans2 = []
for i in ans:
    if i[0] != "0":
        ans2.append(int(i))
        
print(ans2[retsu-1])

Solution (Python):


def main():
    korg = int(input())
    ranran = {(1, 0): ["0"],
        (1, 1): ["1"],
        (1, 2): ["2"],
        (1, 3): ["3"],
        (1, 4): ["4"],
        (1, 5): ["5"],
        (1, 6): ["6"],
        (1, 7): ["7"],
        (1, 8): ["8"],
        (1, 9): ["9"],
        }  
    for d in range(2, 11):
        for k in range(10):
            ranran[(d, k)] = []
            d2 = d - 1
            for k2 in [k - 1, k, k + 1]:
                if not 0 <= k2 <= 9:
                    continue
                for s in ranran[(d2, k2)]:
                    ranran[(d, k)].append(str(k) + s)
    ranran_f = []
    for key, v in ranran.items():
        ranran_f += v
    runrun = sorted(list({int(x) for x in ranran_f}))
    print(runrun[korg])

if __name__ == "__main__":
    main()

Solution (Python):
def func(n):
    s = str(n)
    L = len(s)
    for i in reversed(range(L-1)):
        x = int(s[i])
        y = int(s[i+1])
        if abs(x-y) > 1:
            buf = 10**(L-(i+1)-1)
            if x > y:
                return int(s[:i] + str(x) + str(x-1)) * buf
            else:
                return (int(s[:i+1]) + 1)*(buf*10)
    return -1

def main():
    k = int(input())
    target = 1
    while k > 0:
        buf = func(target)
        if buf == -1:
            k -= 1
            if k == 0:
                break
            target += 1
        else:
            target = buf

    print(target)

if __name__ == "__main__":
    main()

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

from collections import defaultdict

num = 0

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

for i in range(1, 10):
    dp[0].append(i)

for k in range(9):
    for j in range(len(dp[k])):
        s = str(dp[k][j])
        n = int(s[-1])
        if 0 < n:
            dp[k + 1].append(int(s + str(n - 1)))
        dp[k + 1].append(int(s + str(n)))
        if n < 9:
            dp[k + 1].append(int(s + str(n + 1)))

for i in range(10):
    dp[i].sort()
    for j in range(len(dp[i])):
        num += 1
        if num == K:
            print(dp[i][j])

Solution (Python):
from collections import deque
K = int(input())

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

count = 0
lunlun = []

queue = deque([1,2,3,4,5,6,7,8,9])


while count < K:
  now = queue.popleft()
  diff = [-1,0,1]
  for i in range(3):
    tmp = now % 10 + diff[i]
    if 0<= tmp <= 9:
      queue.append(now*10 + tmp)
      lunlun.append(now*10 + tmp)
      count += 1

print(lunlun[K-10])

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

runrun = []
def check(N):
    global runrun
    n = str(N)
    runrun.append(int(n))
    if len(n) == 10:
        return 0
    if n[-1] == "9":
        check(int(n+"8"))
        check(int(n+"9"))
        return
    elif n[-1] == "0":
        check(int(n+"0"))
        check(int(n+"1"))
        return
    else:
        c = int(n[-1]) - 2
        for i in range(3):
            c += 1
            cc = str(c)
            check(int(n+cc))
        return

for i in range(1,10):
    check(i)

runrun.sort()
print(runrun[K-1])

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

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

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

while len(todo) != 0:
    now = todo.pop()
    if now > 3234566668:
        
        continue
    if str(now)[-1] == '0':
        lunlun.append(int(str(now) + '0'))
        lunlun.append(int(str(now) + '1'))
        todo.append(int(str(now) + '0'))
        todo.append(int(str(now) + '1'))
    elif str(now)[-1] == '9':
        lunlun.append(int(str(now) + '8'))
        lunlun.append(int(str(now) + '9'))
        todo.append(int(str(now) + '8'))
        todo.append(int(str(now) + '9'))
    else:
        temp = int(str(now)[-1])
        lunlun.append(int(str(now) + str(temp - 1)))
        lunlun.append(int(str(now) + str(temp)))
        lunlun.append(int(str(now) + str(temp + 1)))
        todo.append(int(str(now) + str(temp - 1)))
        todo.append(int(str(now) + str(temp)))
        todo.append(int(str(now) + str(temp + 1)))

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

Solution (Python):
def main():
    K = int(input())
    used = [1,2,3,4,5,6,7,8,9]
    ans = used
    k = 9
    now = 0
    add = [-1,0,1]
    while True:
        if k >= K :
            break
        else:
            keep = []
            for i in used:
                if (i % 10 == 0 ) :
                    keep.append(i * 10 + 0)
                    keep.append(i * 10 + 1)
                    continue
                if (i % 10 == 9):
                    keep.append(i * 10 + 8)
                    keep.append(i * 10 + 9)
                    continue
                p = (i % 10)
                for j in range(3):
                    keep.append(i * 10 + p + add[j])
            k += len(keep)
            ans += keep
            used = keep
    print(ans[K-1])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
limit = 3234566667
K = int(input())
ans = []

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)
q.append(5)
q.append(6)
q.append(7)
q.append(8)
q.append(9)


ans = []
while len(q):
    num = q.popleft()
    ans.append(num)
    last_num = str(num)[-1]
    if last_num == "9":
        next_num = num * 10 + 8
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
        next_num = num * 10 + 9
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
    elif last_num == "0":
        next_num = num * 10
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
        next_num = num * 10 + 1
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
    else:
        next_num = num * 10 + int(last_num)
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
        next_num = num * 10 + int(last_num) + 1
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
        next_num = num * 10 + int(last_num) - 1
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
ans = list(set(ans))
ans.sort()
print(ans[K-1])

Solution (Python):
k = int(input())
val = [0]
for _ in range(k):
    if len(val) == 1:
        if val[0] != 9:
            val[0] += 1
        else:
            val.insert(0, 1)
            val[-1] = 0
    else:
        accept = False
        for i in range(1, len(val)):
            if val[-1*(i+1)] >= val[-1*i] and val[-1*i] != 9:
                val[-1*i] += 1
                for r in range(1,i):
                    val[-1*(i-r)] = max(0, val[-1*(i-r+1)]-1)
                accept = True
                break
        if not accept:
            if val[0] != 9:
                val[0] += 1
                for i in range(1, len(val)):
                    val[i] = max(val[i-1] - 1, 0)
            else:
                val.insert(0,1)
                for i in range(1, len(val)):
                    val[i] = 0

op = ""
for v in val:
    op += str(v)
print(op)

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

K = int(input())

l = []
cnt = 0
q = deque()

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

while len(q) > 0:
    (n, prev) = q.popleft()
    l.append(int(n))
    cnt += 1
    if cnt > 100000:
        break
    if prev == 0:
        q.append((n + "0", 0))
        q.append((n + "1", 1))
    elif 1 <= prev <= 8:
        q.append((n + str(prev - 1), prev-1))
        q.append((n + str(prev), prev))
        q.append((n + str(prev + 1), prev+1))
    else:
        q.append((n + "8", 8))
        q.append((n + "9", 9))

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

Solution (Python):
from sys import exit
from collections import deque

K = int(input())
l = 0


def f(l):
    global D, K
    if l == 0:
        K -= 1
        if K == 0:
            print(''.join(map(str, D)))
            exit()
        D.pop()
        return
    d = D[-1]
    for i in (d - 1, d, d + 1):
        if i < 0 or i > 9:
            continue
        D.append(i)
        f(l - 1)
    D.pop()


while True:
    for i in range(1, 10):
        D = deque([i])
        f(l)
    l += 1

Solution (Python):
from itertools import product
K = int(input())
ans = []

for l in range(10):
    for s in range(1, 10):
        for pattern in product([0, 1, 2], repeat=l):  
            X = [s]
            for p in pattern:
                if X[-1] == 0 and p == 2:
                    break
                if X[-1] == 9 and p == 1:
                    break

                if p == 0:
                    X.append(X[-1])

                if p == 1:
                    X.append(X[-1] + 1)

                if p == 2:
                    X.append(X[-1] - 1)
            else:
                ans.append(int(''.join(map(str, X))))

ans.sort()
print(ans[K - 1])

Solution (Python):
K = int(input())
kouho = []


def rec(d, n):
    if d == 12:
        return
    kouho.append(n)

    r = n % 10
    if r == 0:
        rec(d + 1, n * 10 + r)
        rec(d + 1, n * 10 + r + 1)
    elif r == 9:
        rec(d + 1, n * 10 + r)
        rec(d + 1, n * 10 + r - 1)
    else:
        rec(d + 1, n * 10 + r)
        rec(d + 1, n * 10 + r - 1)
        rec(d + 1, n * 10 + r + 1)



















for i in range(1, 10):
    rec(1, i)

kouho.sort()

print(kouho[K - 1])

Solution (Python):
K = int(input()) - 1
nums = [str(i) for i in range(1,10)]
while True:
    
    if K < len(nums):
        print(nums[K])
        break
    else:
        K -= len(nums)

    que = []
    for n in nums:
        if n[-1] > "0":
            que.append(n + str(int(n[-1]) - 1))
        if n[-1] < "9":
            que.append(n + str(int(n[-1]) + 1))
        que.append(n + n[-1])
    que.sort()
    nums = que

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


X = int(input())


def check(mid): 
    s = str(mid)
    L = len(s)    
    dp = [[0]*10 for _ in range(2)] 
    for num,i in enumerate(s):
        ni = int(i)
        ndp = [[0]*10 for _ in range(2)] 
        for is_less in range(2):
            for d in range(10 if is_less else ni+1):
                if d: ndp[is_less or d < ni][d] += dp[is_less][d-1]            
                ndp[is_less or d < ni][d] += dp[is_less][d]            
                if d<9: ndp[is_less or d < ni][d] += dp[is_less][d+1]            
        for j in range(1,10):
            if num == 0:
                if j==ni: ndp[0][j] += 1
                elif j<=ni: ndp[1][j] += 1
            else: ndp[1][j] += 1 
        dp = ndp
        
    return sum(dp[1])+sum(dp[0]) >= X

ng = 0
ok = 3234566668
while ok-ng > 1:
    mid = (ok+ng)//2
    if check(mid): ok = mid
    else: ng = mid

print(ok)

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

def dfs(n,f,l,s):
  global K
  if l==0:
    K-=1
    if K==0:
      print(n)
      exit()
  elif s==1:
    for i in range(0,10):
      if i==0:
        dfs(10*n+i,i,l-1,1)
      else:
        dfs(10*n+i,i,l-1,0)
  else:
    if f==0:
      for i in range(0,2):
        dfs(10*n+i,i,l-1,0)
    elif f==9:
      for i in range(8,10):
        dfs(10*n+i,i,l-1,0)
    else:
      for i in range(f-1,f+2):
        dfs(10*n+i,i,l-1,0)
      
dfs(0,0,10,1)

Solution (Python):
def runrun(K,S):
    if K <= len(S):
        S.sort()
        
        print(S[K-1])
        return 
    else:
        for i in range(len(S)):
            tmp = S[i]%10
            if tmp == 9:
                S.append(S[i]*10+8)
                S.append(S[i]*10+9)
            elif tmp == 0:
                S.append(S[i]*10+1)
                S.append(S[i]*10)
            else:
                S.append(S[i]*10+tmp-1)
                S.append(S[i]*10+tmp)
                S.append(S[i]*10+tmp+1)
        S = list(set(S))
        runrun(K,S)

if __name__ == "__main__":
    K = int(input())
    S = []
    for i in range(1,10):
        S.append(i)
    runrun(K,S)

Solution (Python):
def Lun(ume,gen,start):
    global keta
    if(ume==keta):
        global ans
        temp=0
        for i in range(ume):
            temp+=gen[i]*(10**(keta-i-1))
        ans.append(temp)
        
        return
    ima=gen[ume-1]
    send=gen[:]
    if(start):
        if(ima>0):
            send[ume]=ima-1
            Lun(ume+1,send,start)
        send[ume]=ima
        Lun(ume+1,send,start)
        if(ima<9):
            send[ume]=ima+1
            Lun(ume+1,send,start)
    else:
        Lun(ume+1,send,False)
        for i in range(1,10):
            send[ume]=i
            Lun(ume+1,send,True)




ans=[]
keta=10
hajime=[0]*keta
Lun(1,hajime,False)
for i in range(1,4):
    hajime[0]=i
    Lun(1,hajime,True)

print(ans[int(input())])

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

def dfs(n,s,ans):
    if n == 10:
        return
    
    for i in range(10):

        tmp = s + str(i)
        if check(tmp):
            ans.append(int(tmp))
            dfs(n+1,tmp,ans)


def check(s):
    if abs(int(s[-1])-int(s[-2])) > 1:
        return False
    return True 

def main():
    K = int(input())
    ans = [1,2,3,4,5,6,7,8,9]
    for i in range(1,10):
        dfs(1,str(i),ans)
    ans.sort()
    print(ans[K-1])

    


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
k = int(input())
ans = []

def rec(s, dig):
    if dig >= 10:
        ans.append(int("".join(map(str, s))))
        return
    
    if sum(s) == 0:
        for i in range(10):
            rec(s + [i], dig+1)
        return

    p = s[-1]
    if p != 0: rec(s + [p-1], dig+1)
    rec(s + [p], dig+1)
    if p != 9: rec(s + [p+1], dig+1)

rec([0], 0)
print(ans[k])

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

dp = [[0]*10 for _ in range(10)]
d = [-1,0,1]
for i in range(10):
    for j in range(10):
        if i == 0:
            dp[i][j] = 1
        else:
            for dj in d:
                pj = j + dj
                if 0<=pj<10:
                    dp[i][j] += dp[i-1][pj]
cnt = 0
for n in range(10):
    s = sum(dp[n][1:])
    if cnt + s < k:
        cnt += s
    else:
        break
ans = ''
for j in range(1,10):
    if cnt + dp[n][j] < k:
        cnt += dp[n][j]
    else:
        ans += str(j)
        break

for i in range(n)[::-1]:
    for dj in d:
        nj = j + dj
        if 0<=nj<10:
            if cnt + dp[i][nj] < k:
                cnt += dp[i][nj]
            else:
                j = nj
                ans += str(nj)
                break
print(ans)

Solution (Python):
k = int(input())
num = 1
anss=[i for i in range(1,10)]
ans=[i for i in range(0,10)]
j=1
while(len(anss)<100001):
  j*=10
  ans_=[]
  for i in ans:
    i_=i//(j//10)
    if i_==9:
      ans_.append(i_*j+i)
      ans_.append((i_-1)*j+i)
    elif i_==0:
      ans_.append(i_*j+i)      
      ans_.append((i_+1)*j+i)
    else:
      ans_.append(i_*j+i)
      ans_.append((i_+1)*j+i)
      ans_.append((i_-1)*j+i)
  anss.extend(ans_)
  anss=list(set(anss))
  ans=[x for x in ans_]
anss.sort()
print(anss[k])

Solution (Python):
from collections import deque
k = int(input())
if k < 10:
  print(k)
else:
  queue = deque([[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7],[8,8],[9,9]])
  n = 9
  while n!=k:
    num,last_n = queue.popleft()
    if last_n-1 > -1:
      new_n = num*10+(last_n-1)
      queue.append([new_n,last_n-1])
      n += 1
    if n >= k:
      ans,_ = queue[-1]
      print(ans)
      break
    new_n = num*10+(last_n)
    queue.append([new_n,last_n])
    n += 1
    if n >= k:
      ans,_ = queue[-1]
      print(ans)
      break
    if last_n+1 < 10:
      new_n = num*10+(last_n+1)
      queue.append([new_n,last_n+1])
      n += 1
    if n >= k:
      ans, _ = queue[-1]
      print(ans)
      break

Solution (Python):

import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import os
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)

alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s

All=[]

@lru_cache(maxsize=None)
def f(s):
    if(s!=""):All.append(int(s))
    if(len(s)>=10):return
    if len(s)==0:
        for a in range(1,10):
            f(s+str(a))
    else:
        for a in range(0,10):
            ch=ord("0")+a
            if abs(ord(s[-1])-ch)<=1:
                f(s+str(a))
K=int(input())
f("")
All.sort()
print(All[K-1])

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

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

def a(b):
    if b > 3234566667:
        return
    sb = str(b)
    h = int(sb[-1])
    for i in range(0, 10):
        if abs(i-h) <= 1:
            k = int(str(b) + str(i))
            L.append(k)
            a(k)

for i in range(1, 10):
    a(i)
L = sorted(L)

print(L[K-1])

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

ls = []

def dfs(n):
    if len(n) >= 12:
        return
    ls.append(int(n))
    lastNum = int(n[-1])
    for i in range(max(0, lastNum-1), min(lastNum + 2, 10)):
        dfs(n + str(i))

dfs("1")
dfs("2")
dfs("3")
dfs("4")
dfs("5")
dfs("6")
dfs("7")
dfs("8")
dfs("9")

ls = list(ls)
ls = sorted(ls)
print(ls[k-1])

Solution (Python):

import sys
import math
import numpy as np
import itertools



k = int(input())

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

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

for i in range(20):
    k -= len(a)
    b = []
    for j in a:
        r = j % 10 
        if r == 0:
            b.append(j*10)
            b.append(j*10+1)
        elif r == 9:
            b.append(j*10+8)
            b.append(j*10+9)
        else:
            b.append(j*10+r-1)
            b.append(j*10+r)
            b.append(j*10+r+1)

    if k <= len(b):
        print(b[k-1])
        exit()
    a = b

Solution (Python):
import sys
sys.setrecursionlimit(20000000)
k = int(input())

def dfs(l, lim):
    if lim == 10:
        return l
    new_l = []
    for num in l:
        last = num % 10
        base = num * 10
        if 1 <= last <= 8:
            for i in [last-1, last, last+1]:
                if base + i <= 3234566667:
                    new_l.append(base + i)
        elif last == 0:
            for i in [0, 1]:
                if base + i <= 3234566667:
                    new_l.append(base + i)
        else:
            for i in [8, 9]:
                if base + i <= 3234566667:
                    new_l.append(base + i)
    return l + new_l + dfs(new_l, lim+1)

ans = list(set(dfs([1, 2, 3, 4, 5, 6, 7, 8, 9], 0)))
ans.sort()

print(ans[k-1])

Solution (Python):
def main():

    K = int(input())
    cur = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    if K <= len(cur):
        return cur[K-1]
    K -= 9
    
    while True:
        temp = []
        for v in cur:
            if v % 10 == 0:
                temp.append(v*10 + v % 10)
                temp.append(v*10 + 1)
            elif v % 10 == 9:
                temp.append(v*10 + 8)
                temp.append(v*10 + v % 10)
            else:
                temp.append(v * 10 + v % 10 - 1)
                temp.append(v * 10 + v % 10)
                temp.append(v * 10 + v % 10 + 1)
        
        if len(temp) >= K:
            
            return temp[K-1]
        cur = temp
        K -= len(temp)
    return -1

if __name__ == '__main__':
    print(main())

Solution (Python):



def input_multiple_number():
    return map(int, input().split())

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


K = int(input())

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

for i in range(100000):
	for j in range(3):
		if ans[i]%10 == 0 and j ==0:
			continue
		elif ans[i]%10 == 9 and j ==2:
			continue
		ans.append(ans[i]*10+j-1+ans[i]%10)

print(ans[K-1])

Solution (Python):
import sys
input=sys.stdin.readline
k=int(input())
l=[[1,2,3,4,5,6,7,8,9]]
c=9
i=1
l0=[0]
while c<k:
    temp=[]
    for j in l0:
        temp.append(1*10*i+j)
    for j in l[-1]:
        t=j//i
        if t==1:
            temp.append(1 * 10 *i + j)
            temp.append(2*10*i+j)
            l0.append(j)
        elif t==9:
            temp.append(8*10*i+j)
            temp.append(9 * 10 *i + j)
        else:
            temp.append((t+1) * 10 *i+ j)
            temp.append(t * 10 *i + j)
            temp.append((t-1) * 10 *i + j)
    i=i*10
    c+=len(temp)
    l.append(temp)
all=[]
for i in l:
    for j in i:
        all.append(j)
all.sort()
print(all[k-1])

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

a = [i for i in range(1, 10)]
heapq.heapify(a)
ans = 0
while ans < k:
    r = heapq.heappop(a)
    ans += 1
    if ans == k:
        print(r)
        break
    for i in [-1, 0, 1]:
        if r % 10 + i < 0 or 9 < r % 10 + i:
            pass
        else:
            heapq.heappush(a, int("{}{}".format(r, r % 10 + i)))

Solution (Python):
K = int(input().strip())
if K <= 10:
  print(K)
  exit()

def extend_lunlun(prev):
  prev_digit = int(str(prev)[-1])
  if prev_digit == 0:
    add_list = [0, 1]
  elif prev_digit == 9:
    add_list = [8, 9]
  else:
    add_list = [prev_digit-1, prev_digit, prev_digit+1]
  return [int('{}{}'.format(prev, ad)) for ad in add_list]
  

lunlun_numbers = list(range(1,10))
i_pos = 0
while True:
  lunlun_numbers += extend_lunlun(lunlun_numbers[i_pos])
  if len(lunlun_numbers) >= K:
    print(lunlun_numbers[K-1])
    break
  i_pos += 1

Solution (Python):
from collections import deque
k = int(input())
lst = []
cnt = 0
Q = deque()
for i in range(1,10):
    Q.append(str(i))
while cnt < k:
    s = Q.popleft()
    x = int(s[-1])
    lst.append(int(s))
    cnt += 1
    if x != 0:
        Q.append(s+str(x-1))
    Q.append(s+str(x))
    if x != 9:
        Q.append(s+str(x+1))

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

Solution (Python):
P = int(input())
A = []
for i in range(1, 10):
    A.append(str(i))

keta = 1
for i in range(9):
    ap = []
    for j in range(len(A)):
        a = A[j]
        if len(a)<keta:
            continue
        l = int(a[-1])
        for k in range(max(0, l-1), min(10, l+2)):
            ap.append(a+str(k))
    keta += 1
    for j in ap:
        A.append(j)
for i in range(len(A)):
    A[i] = int(A[i])
A.sort()
print(A[P-1])

Solution (Python):
import collections


def go_next(digits):
    if all(x==9 for x in digits):
        return [0]*len(digits) + [1]

    digits[0] += 1

    maxInc = -1
    
    for i in range(1, len(digits)):
        if digits[i-1] >= 10 or abs(digits[i]-digits[i-1]) >= 2:
            digits[i] += 1
            maxInc = i
        else:
            break
    
    if maxInc > 0:
        for i in range(maxInc, 0, -1):
            digits[i-1] = max(0, digits[i]-1)
    return digits





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

    digits = [0]
    for _ in range(K):
        digits = go_next(digits)

    print("".join(map(str, reversed(digits))))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    k = int(input())
    xl = [[] for i in range(11)]
    xl[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    if k < 10:
        print(xl[0][k-1])
        return 
    k -= 9
    for i in range(1, 11):
        pl = []
        for x in xl[i-1]:
            m = x%10
            if m == 0:
                for mi in range(m, m+2):
                    pl.append(10*x+mi)
                k -= 2
            elif m == 9:
                for mi in range(m-1, m+1):
                    pl.append(10*x+mi)
                k -= 2
            else:
                for mi in range(m-1, m+2):
                    pl.append(10*x+mi)
                k -= 3
            if k <= 0:
                print(pl[k-1])
                return
        xl[i] = pl

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
anss = ["1","2","3","4","5","6","7","8","9"]
cot  = 0

cot = 9
while cot < n:
    for temp in anss: 
        temp_int = int(temp[-1])
        start = max(0,temp_int - 1)
        end = min(10, temp_int + 2)
        for i in range(start,end):
            anss.append(temp + str(i))
            cot += 1
        if cot > n:
            break




anss = list(map(int,anss))
anss.sort()
print(anss[n -1])

Solution (Python):
K=int(input())
b=[[i] for i in range(1,10)]
l=[0,9, 35, 110, 327, 956, 2782, 8089, 23527, 68468,200000]
for i in range(11):
    if K<=l[i]:
        N=i
        K-=l[i-1]
        break
for i in range(N-1):
    a=[]
    for j in b:
        if j[-1]!=0:
            a.append(j+[j[-1]-1])
        a.append(j+[j[-1]])
        if j[-1]!=9:
            a.append(j+[j[-1]+1])
    b=a
print(*b[K-1],sep="")