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

Solution (Python):
from collections import deque
k = int(input())
Q = deque(range(1, 10))
for _ in range(k):
  x = Q.popleft()
  y = x % 10
  z = 10*x + y
  if y != 0:
    Q += [z-1]
  Q += [z]
  if y != 9:
    Q += [z+1]
print(x)

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

queue = deque()
for i in range(1, 10):
    queue.appendleft(i)

for _ in range(K-1):
    p = queue.pop()
    if p%10!=0:
        queue.appendleft(p*10+p%10-1)
    queue.appendleft(p*10+p%10)
    if p%10!=9:
        queue.appendleft(p*10+p%10+1)

print(queue.pop())

Solution (Python):
import sys
from _collections import deque

K = int(input())
c = 9
A = [1,2,3,4,5,6,7,8,9]
q = deque(A)

if K <= 9:
    print(K)
else:
    while(True):
        a = q.popleft()
        if a % 10 == 0:
            c += 1
            if c == K:
                print(a*10)
                sys.exit()
            q.append(a*10)
            c += 1
            if c == K:
                print(a*10+1)
                sys.exit()
            q.append(a*10+1)
        elif a % 10 == 9:
            c += 1
            if c == K:
                print(a*10+9-1)
                sys.exit()
            q.append(a*10+9-1)
            c += 1
            if c == K:
                print(a*10+9)
                sys.exit()
            q.append(a*10+9)
        else:
            c += 1
            if c == K:
                print(a*10+a%10-1)
                sys.exit()
            q.append(a*10+a%10-1)
            c += 1
            if c == K:
                print(a*10+a%10)
                sys.exit()
            q.append(a*10+a%10)
            c += 1
            if c == K:
                print(a*10+a%10+1)
                sys.exit()
            q.append(a*10+a%10+1)

Solution (Python):
X = []
for a in range(1, 10):
    X.append(a)
    for b in range(10):
        if abs(b-a) > 1: continue
        X.append(a * 10 + b)
        for c in range(10):
            if abs(c-b) > 1: continue
            X.append(a * 10 ** 2 + b * 10 + c)
            for d in range(10):
                if abs(d-c) > 1: continue
                X.append(a * 10 ** 3 + b * 10 ** 2 + c * 10 + d)
                for e in range(10):
                    if abs(e-d) > 1: continue
                    X.append(a * 10 ** 4 + b * 10 ** 3 + c * 10 ** 2 + d * 10 + e)
                    for f in range(10):
                        if abs(f-e) > 1: continue
                        X.append(a * 10 ** 5 + b * 10 ** 4 + c * 10 ** 3 + d * 10 ** 2 + e * 10 + f)
                        for g in range(10):
                            if abs(g-f) > 1: continue
                            X.append(a * 10 ** 6 + b * 10 ** 5 + c * 10 ** 4 + d * 10 ** 3 + e * 10 ** 2 + f * 10 + g)
                            for h in range(10):
                                if abs(h-g) > 1: continue
                                X.append(a * 10 ** 7 + b * 10 ** 6 + c * 10 ** 5 + d * 10 ** 4 + e * 10 ** 3 + f * 10 ** 2 + g * 10 + h)
                                for i in range(10):
                                    if abs(i-h) > 1: continue
                                    X.append(a * 10 ** 8 + b * 10 ** 7 + c * 10 ** 6 + d * 10 ** 5 + e * 10 ** 4 + f * 10 ** 3 + g * 10 ** 2 + h * 10 + i)
                                    for j in range(10):
                                        if abs(j-i) > 1: continue
                                        X.append(a * 10 ** 9 + b * 10 ** 8 + c * 10 ** 7 + d * 10 ** 6 + e * 10 ** 5 + f * 10 ** 4 + g * 10 ** 3 + h * 10 ** 2 + i * 10 + j)

print(sorted(X)[int(input()) - 1])

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

     runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     count = 0
     while(len(runrun) < k):
          target = runrun[count]
          num = target % 10
          if num != 0:
               runrun.append(target * 10 + num - 1)
          runrun.append(target * 10 + num)
          if num != 9:
               runrun.append(target * 10 + num + 1)

          count += 1

     print(runrun[k-1])

if __name__ == "__main__":
    main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

k = ni()
que = deque()
for i in range(1, 10):
    que.append(i)
ct = 0
for i in range(k):
    x = que.popleft()
    if x % 10 != 0:
        que.append(10*x+x%10-1)
    que.append(10*x+x%10)
    if x % 10 != 9:
        que.append(10*x+x%10+1)
print(x)

Solution (Python):

k=int(input())

from collections import deque
todo = deque([i for i in range(1, 10)])
count = 0

while len(todo) > 0:
    value = todo.popleft()
    value_digit1 = value % 10
    count += 1
    if count == k:
        print(value)
        break
    if value_digit1==0:
        todo.append(10*value)
        todo.append(10*value+1)
    elif value_digit1==9:
        todo.append(10*value+8)
        todo.append(10*value+9)
    else:
        todo.append(10*value+value_digit1-1)
        todo.append(10*value+value_digit1)
        todo.append(10*value+value_digit1+1)

Solution (Python):
import queue

K = int(input())

q=queue.Queue()
for i in range(1,10):
    q.put(i)

for _ in range(K):
    x = q.get(0)
    
    if x % 10 != 0:
        q.put(x*10 + x%10 - 1)
    q.put(x*10 + x%10)
    if x % 10 != 9:
        q.put(x*10 + x%10 + 1)
print(x)

Solution (Python):
a = []

def dfs(n):
    if n > 3234566667:
        return

    a.append(n)
    for i in range(10):
        if abs(n%10 - i) <= 1:
            dfs(n*10+i)

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

k = int(input())
a = sorted(a)
print(a[k-1])

Solution (Python):
from collections import deque

K = int(input())

tree = deque([[-1, i] for i in range(1, 10)])
i = 0
cnt = 9

while cnt <= K:
    n = tree[i][1]
    if n > 0:
        tree.append([i, n - 1])
        cnt += 1
    tree.append([i, n])
    cnt += 1
    if n < 9:
        tree.append([i, n + 1])
        cnt += 1
    i += 1

ans = ""
j = K - 1

while True:
    j, b = tree[j]
    ans = str(b) + ans
    if j == -1:
        break

print(ans)

Solution (Python):
from collections import deque

q = deque(range(1,10))
K = int(input())

for i in range(K):
    x = q.popleft()
    r =  x % 10
    if r != 0:
        q.append((10 * x) + (r - 1))
    q.append((10 * x) + r)
    if r != 9:
        q.append((10 * x) + (r + 1))

print(x)

Solution (Python):
K=int(input())
u12 = [i for i in range(1,10)]
ans = 0
for i in range(K):
    if ans <=11:
        ans += 1
        continue
    flg = True
    l = len(str(ans))
    for j in range(l-1,-1,-1):
        if 0<j<l-1:
            x,y,z = map(int,str(ans)[j-1:j+2])
            if y!=9 and abs(x-(y+1))<=1 and abs((y+1)-z)<=1:
                ans = int(str(ans)[:j]+''.join([str(max(0,y+1-i)) for i in range(l-j)]))
                flg = False
                break
        elif j==0:
            x,y = map(int,str(ans)[:2])
            if x != 9 and abs(x+1-y) <=1:
                ans = int(''.join([str(max(0,x+1-i))for i in range(l)]))
                flg = False
                break
        else:
            x,y = map(int,str(ans)[-2:])
            if y != 9 and abs(x-(y+1))<=1:
                ans += 1
                flg = False
                break
    if flg:
        ans = 10**l
print(ans)

Solution (Python):
from collections import deque

k = int(input())

q = deque(range(1, 10))
for _ in range(k):
    x = q.popleft()
    if x % 10 != 0:
        q.append(x*10 + x%10 - 1)
    q.append(x*10 + x%10)
    if x % 10 != 9:
        q.append(x*10 + x%10 + 1)

print(x)

Solution (Python):
from collections import deque
K=int(input())
lun=deque([1,2,3,4,5,6,7,8,9])
for i in range(K):
    x=lun.popleft()
    if x%10!=0:
        lun.append(10*x+x%10-1)
    lun.append(10*x+x%10)
    if x%10!=9:
        lun.append(10*x+x%10+1)
print(x)

Solution (Python):
from collections import deque

K = int(input())

list = deque(range(1,10))
i = 0
for i in range(K):
    v = list.popleft()

    t = v%10

    if t != 0:
        list.append(10*v + (t-1))

    list.append(10*v + t)

    if t != 9:
        list.append(10*v + (t+1))


print(v)

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

que = deque(range(1, 10))
for _ in range(K):
    x = que.popleft()
    target = x%10
    num = x*10 + target
    if target != 0:
        que.append(num-1)
    que.append(num)
    if target != 9:
        que.append(num+1)
print(x)

Solution (Python):
def lower(upper):
    if upper==9:
        return [8,9]
    elif upper==0:
        return [0,1]
    else:
        return [upper-1,upper,upper+1]

def numerize(a):
    return sum([a[i]*(10**i) for i in range(len(a))])

def getRunruns(digit):
    if digit==1:
        return [(i,) for i in range(10)]
    elif digit==2:
        return [(k,i) for i in range(1,10) for k in lower(i)]
    else:
        runruns=getRunruns(2)
        for i in range(digit-2):
            runruns=[(k,)+i for i in runruns for k in lower(i[0])]
        return runruns

A1=[(i,) for i in range(10)]
A2=[(k,i) for i in range(1,10) for k in lower(i)]
A=A1+A2
Aprev=A2
K=int(input())
while len(A)<K+1:
    Aprev=[(k,)+i for i in Aprev for k in lower(i[0])]
    A+=Aprev
print(numerize(A[K]))

Solution (Python):
from collections import deque
K = int(input())
q = deque(list(range(1,10)))
x = 0
for i in range(1, K+1):
    x = q.popleft()
    xs = str(x)
    if xs[-1] != '0':
        add_n = int(xs + str(int(xs[-1]) - 1))
        q.append(add_n)
    add_n = int(xs + str(int(xs[-1])))
    q.append(add_n)
    if xs[-1] != '9':
        add_n = int(xs + str(int(xs[-1]) + 1))
        q.append(add_n)
print(x)

Solution (Python):
from collections import deque

K=int(input())

M=0
L=9
tmp=deque([1,2,3,4,5,6,7,8,9])
while L<K:
    k=str(tmp.popleft())
    if int(k[-1])-1>=0:
        tmp.append(int(k+str(int(k[-1])-1)))
        L+=1
    tmp.append(int(k+k[-1]))
    L+=1
    if int(k[-1])+1<10:
        tmp.append(int(k+str(int(k[-1])+1)))
        L+=1
    M+=1

print(tmp[K-1-M])

Solution (Python):
import queue

K = int(input())
L = queue.Queue()

for i in range(1,10):
  L.put(i)
for i in range(K-1):
  x = L.get()
  p = 10*x
  m = x%10
  if m != 0:
    L.put(p+m-1)
  L.put(p+m)
  if x%10 != 9:
    L.put(p+m+1)
print(L.get())

Solution (Python):
from collections import deque
k = int(input())
q = deque(list(range(1, 10)))
for _ in range(k-1):
	d = q.popleft()
	if d%10 > 0:
		q.append(d*10 + d%10 - 1)
	q.append(d*10 + d%10)
	if d%10 < 9:
		q.append(d*10 + d%10 + 1)
print(q.popleft())

Solution (Python):
from collections import deque

k = int(input())

ans = deque([i for i in range(1, 10)])

for i in range(k):
    x = ans.popleft()
    modx = x%10
    if modx != 0:
        ans.append(x*10 + modx - 1)
    ans.append(x*10 + modx)
    if modx != 9:
        ans.append(x*10 + modx + 1)
print(x)

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


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

count = 100000

while K > 0:
    a = q.popleft()

    if count > 0:
        if a % 10 == 0:
            q.append(10 * a)
            q.append(10 * a + 1)
            count -= 2
        elif a % 10 == 9:
            q.append(10*a + 8)
            q.append(10*a + 9)
            count -= 2
        else:
            b = a % 10
            q.append(10*a + b-1)
            q.append(10*a + b)
            q.append(10*a + b+1)
            count -= 3
    K -= 1
print(a)

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

    queue = deque(range(1, 10))
    ans = -1
    for _ in range(K):
        ans = queue.popleft()
        lsd = ans % 10  
        if lsd != 0:
            queue.append(10 * ans + (lsd - 1))
        queue.append(10 * ans + lsd)
        if ans % 10 != 9:
            queue.append(10 * ans + (lsd + 1))
    return ans

print(d_lunlun_number())

Solution (Python):
k=int(input())
t=[2]+[3]*8+[2]
g=[[1]+[0for i in range(9)]for j in range(100)]
def f(x,y):
    if g[x][y]!=0:
        return g[x][y]
    else:
        p=0
        for i in range(x-1,x+2):
            if 0<=i<10:
                p+=f(i,y-1)
        g[x][y]=p
        return p
c=0
for i in range(10):
    for j in range(1,10):
        if c+f(j,i)>=k:
            p=str(j)
            po=j
            for h in range(i-1,-1,-1):
                for w in range(po-1,po+2):
                    if 0<=w<10:
                        if c+f(w,h)>=k:
                            p+=str(w)
                            po=w
                            break
                        c+=f(w,h)
            print(p)
            exit()
        c+=f(j,i)

Solution (Python):
from queue import Queue

k = int(input())

q = Queue()
for i in range(1, 10):
    q.put(i)

for _ in range(k):
    x = q.get()
    if x % 10 != 0:
        q.put(x*10 + x%10 - 1)
    q.put(x*10 + x%10)
    if x % 10 != 9:
        q.put(x*10 + x%10 + 1)

print(x)

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

a = ["1","2","3","4","5","6","7","8","9"]
i = 0
while len(a)<=k:
  b = a[i]
  c = int(b[-1])
  i += 1
  for j in range(-1,2):
    if 0<=c+j<10:
      a.append(b+str(c+j))

print(a[k-1])

Solution (Python):
k=int(input())
cand=[[1,2,3,4,5,6,7,8,9]]
for _ in range(9):
  tmp=[]
  for val in cand[-1]:
    if val%10!=0:
      tmp.append(val*10+(val%10-1))
    tmp.append(val*10+(val%10))
    if val%10!=9:
      tmp.append(val*10+(val%10+1))
  cand.append(tmp)
ans=[]
for i in range(len(cand)):
  for val in cand[i]:
    ans.append(val)
ans=sorted(ans)
print(ans[k-1])

Solution (Python):
def main():
    from collections import deque

    K = int(input())
    q = deque(range(1, 10))
    for _ in range(K):
        x = q.popleft()
        lastdigit = x%10
        base = x*10 + lastdigit
        if lastdigit != 0:
            q.append(base-1)
        q.append(base)
        if lastdigit != 9:
            q.append(base+1)
    print(x)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

k = int(input())
d = deque([1,2,3,4,5,6,7,8,9])

for i in range(k):
    x = d.popleft()
    if x % 10 != 0:
        d.append(10 * x + x % 10 - 1)

    d.append(10 * x + x % 10)
    
    if x % 10 != 9:
        d.append(10 * x + x % 10 + 1)

print(x)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





k=ii()
ans=0
arr=deque([1,2,3,4,5,6,7,8,9])
while k>ans:
    n=int(arr.popleft())
    if n%10==9:
        arr.append(n*10 + n%10 -1)
        arr.append(n*10 + n%10 )
    elif n%10==0:
        arr.append(n*10 + n%10)
        arr.append(n*10 + n%10+1)
    else:
        arr.append(n*10 + n%10 -1)
        arr.append(n*10 + n%10)
        arr.append(n*10 + n%10 +1)
    ans+=1
print(n)

Solution (Python):
from collections import deque
def main():
    k=int(input())
    if k<=9:
        return k
    q=deque()
    for i in range(1,10):
        q.append(i)
    Ans=list(range(1,10))
    cnt=9
    while cnt<k:
        s=q.popleft()
        d=s%10
        s*=10
        if d==0:
            q.append(s)
            q.append(s+1)
            Ans.append(s)
            Ans.append(s+1)
            cnt+=2
        elif d==9:
            q.append(s+8)
            q.append(s+9)
            Ans.append(s+8)
            Ans.append(s+9)
            cnt+=2
        else:
            V=[d-1,d,d+1]
            for v in V:
                q.append(s+v)
                Ans.append(s+v)
            cnt+=3
    return Ans[k-1]
    
if __name__=='__main__':
    print(main())

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

def nextrun(A):
    bflag = 1
    for i in range(len(A)-1):
        if A[-i-1] != 9 and A[-i-1] <= A[-i-2]:
            A[-i-1] += 1
            for k in range(i):
                A[-i-1+k+1] = max(A[-i-1+k] - 1,0)
            bflag = 0
            return A
    
    if bflag:
        if A[0] != 9:
            A[0] += 1
            for k in range(len(A)-1):
                A[-i-1-1+k+1] = max(A[-i-1-1+k] - 1,0)    
        else:
            B = [0]*(len(A)+1)
            B[0] = 1
            A = B
        return A
            
A = [0]
for i in range(K):
    A = nextrun(A)
print(''.join(map(str, A)))

Solution (Python):
import queue

k = int(input())

q = queue.Queue()
for i in range(1,10):
    q.put(i)

for i in range(k):
    x = q.get()

    p = 10 * x  
    m = x % 10
    if not m == 0:
        q.put(p + m - 1)

    q.put(p + m)

    if not m == 9:
        q.put(p + m + 1)
    
print(x)

Solution (Python):
K = int(input())
ans = [0]
def f(n):
    tmp = str(n)
    if int(n) > 3234566667:
        return
    else:
        ans.append(int(n))
    f(str(tmp)+tmp[-1])
    if int(tmp[-1])-1 >= 0:
        f(str(tmp)+str(int(tmp[-1])-1))
    if int(tmp[-1])+1 <= 9:
        f(str(tmp)+str(int(tmp[-1])+1))
for i in range(1,10):
    f(i)
ans.sort()
print(ans[K])

Solution (Python):

import sys
import queue

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

i = 1
while True:
    r = q.get()
    if ( r % 10 != 0 ):
        q.put(10 * r + int(str(r)[-1]) -1)
    q.put(10*r + int(str(r)[-1]))
    if ( r % 10 != 9 ):
        q.put(10 * r + int(str(r)[-1]) + 1)

    if (i == K):
        print(r)
        break
    i += 1

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

q = queue.Queue()
for i in range(1, 10):
    q.put(i)

for i in range(k):
    x = q.get()
    if (x % 10) > 0:
        q.put((10 * x) + (x % 10) - 1)
    q.put(10 * x + (x % 10))
    if (x % 10) < 9:
        q.put((10 * x) + (x % 10) + 1)
print(x)

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    K = int(input())
    q = deque([1,2,3,4,5,6,7,8,9])
    for _ in range(K - 1):
        n = q.popleft()
        
        if n % 10 == 0:
            q.append(n * 10)
            q.append(n * 10 + 1)
        elif n % 10 == 9:
            q.append(n * 10 + 8)
            q.append(n * 10 + 9)
        else:
            k = n % 10
            q.append(n * 10 + k - 1)
            q.append(n * 10 + k)
            q.append(n * 10 + k + 1)
    print(q[0])


    

if __name__ == "__main__":
    main()

Solution (Python):
lunlun = [[1,2,3,4,5,6,7,8,9],[],[],[],[],[],[],[],[],[],[]]
for i in range(1,10):
    for x in lunlun[i-1]:
        unit_digit = x % 10
        if unit_digit == 0:
            lunlun[i].append(x*10)
            lunlun[i].append(x*10 + 1)
        elif unit_digit == 9:
            lunlun[i].append(x*10 + 9)
            lunlun[i].append(x*10+8)
        else:
            lunlun[i].append(x*10+unit_digit)
            lunlun[i].append(x*10+unit_digit - 1)
            lunlun[i].append(x*10+unit_digit+1)
        
temp = []
for row in lunlun:
    temp = temp + row
temp.sort()
k = int(input())
print(temp[k-1])

Solution (Python):


from collections import deque

k = int(input())

que = deque(reversed([i for i in range(1, 10)]))

x = -1
for _ in range(k):
    
    
    x = que.pop()
    
    if x % 10 != 0:
        que.appendleft(x * 10 + x % 10 - 1)
    que.appendleft(x * 10 + x % 10)
    if x % 10 != 9:
        que.appendleft(x * 10 + x % 10 + 1)

print(x)

Solution (Python):
import queue
q = queue.Queue()
for i in range(9):
    q.put(i+1)
    
N = int(input())
for _ in range(N):
    x = q.get()
    y = x%10
    if x%10 != 0:
        q.put(10*x + y-1)
    q.put(10*x + y)
    if x%10 != 9:
        q.put(10*x + y+1)

        
print(x)

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

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

print(ok)

Solution (Python):
from collections import deque
import sys

K = int(input())
q = deque()
if K < 10:
    print(K)
    sys.exit()

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

counta = 9
while K > counta:
    x = q.popleft()
    
    if x % 10 != 0:
        q.append(10 * x + (x % 10) - 1)
        counta += 1
        if K == counta:
            break
    if True:
        q.append(10 * x + (x%10))
        counta += 1
        if K == counta:
            break
    if x % 10 != 9:
        q.append(10 * x + (x%10) + 1)
        counta += 1
        if K == counta:
            break
print(q.pop())

Solution (Python):
from collections import deque
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


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

    queue = deque([])
    for i in range(1,10):
        queue.append(i)
    
    for i in range(K):
        x = queue.popleft()
        r = x % 10
        if r != 0:
            queue.append(10*x + r - 1)
        queue.append(10*x + r)
        if x % 10 != 9:
            queue.append(10*x + r + 1)
    
    print(x)


if __name__ == "__main__":
    main()

Solution (Python):
dic_ref = {k:[k-1,k,k+1] for k in range(10)}
dic_ref = {str(k):''.join([str(x) for x in v if -1<x<10]) for k,v in dic_ref.items()}
k = int(input())
lst = list('123456789')

def generate(lst):
    res = []
    for i in lst:
        for j in dic_ref[i[-1]]:
            res.append(i + j)
    return res
            
while True:
    if k <= len(lst):
        print(int(lst[k-1]))
        break
    else:
        k -= len(lst)
        lst = generate(lst)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

k = inp()
if k < 10:
    print(k)
    quit()

q = deque()
for i in range(9):
    q.append(i+1)
cnt = 10
while True:
    x = q.popleft()
    xx = int(str(x)[-1])
    for i in [-1,0,1]:
        if 0 <= xx+i < 10:
            tmp = x * 10 + xx+i
            if cnt == k:
                print(tmp)
                quit()
            q.append(tmp)
            cnt += 1

Solution (Python):
from collections import deque
k = int(input())
q = deque(list(range(1, 10)))
for _ in range(k-1):
	d = q.popleft()
	if d%10 > 0:
		q.append(d*10 + d%10 - 1)
	q.append(d*10 + d%10)
	if d%10 < 9:
		q.append(d*10 + d%10 + 1)
print(q.popleft())

Solution (Python):
import sys
from collections import deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

K = int(read())

cnt = 0

que = deque([i for i in range(1, 10)])

while len(que) != 0:
    acc = que.popleft()
    cnt += 1

    if cnt == K:
        ans = acc
        break
    acc_ = acc % 10
    if acc_ != 0:
        que.append(acc * 10 + acc_ - 1)
    que.append(acc * 10 + acc_)
    if acc_ != 9:
        que.append(acc * 10 + acc_ + 1)

print(ans)

Solution (Python):
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

K = ir()
A = deque([x for x in range(1, 10)])
count = 0
while True:
    cur = A.popleft()
    count += 1
    if count == K:
        answer = cur
        break
    next = 10 * cur + (cur % 10)
    if cur % 10 != 0:
        A.append(next-1)
    A.append(next)
    if cur % 10 != 9:
        A.append(next+1)

print(answer)

Solution (Python):
import queue
k = int(input())
q = queue.Queue()
for i in range(1,10):
    q.put(i)
for i in range(k):
    x = q.get()

    if x%10 != 0:
        q.put(10*x+x%10-1)
    q.put(10*x+x%10)
    if x%10 != 9:
        q.put(10*x+x%10+1)
print(x)

Solution (Python):
import numpy as np

k = int(input())



def check(n):
    digits = []
    while n:
        n, m = divmod(n, 10)
        digits.append(m)
    digits.reverse()

    dp = np.zeros(10, dtype=np.int64)
    dp[1:digits[0]] = 1
    edge = digits[0]
    for d in digits[1:]:
        odp = dp.copy()
        dp[:-1] += odp[1:]
        dp[1:] += odp[:-1]
        dp[1:] += 1
        if edge != -1:
            if edge - 1 > d:
                edge = -1
            elif edge + 1 >= d:
                dp[max(0, edge - 1):d] += 1
                edge = d
            else:
                dp[max(0, edge - 1):edge + 2] += 1
                edge = -1
    result = dp.sum()
    if edge != -1:
        result += 1
    return result >= k


l = 0
r = 3234566667
while l + 1 < r:
    m = (l + r) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)

Solution (Python):

from collections import deque
K=int(input())
L=deque([1,2,3,4,5,6,7,8,9])
cnt=0
x=0
for _ in range(K):
	cnt+=1
	x=L.popleft()
	if x%10 !=0:
		L.append(10*x+x%10-1)
	L.append(10*x+x%10)
	if x%10!=9:
		L.append(10*x+x%10+1)

print(x)

Solution (Python):
def main():
    k = int(input())
    lun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    cnt = 0
    
    while(len(lun) < k):
        target = lun[cnt]
        mod = target % 10
        if mod != 0:
            lun.append(target*10 + mod - 1)
            
        lun.append(target*10 + mod)
        
        if mod != 9:
            lun.append(target*10 + mod + 1)
        cnt += 1
        
    print(lun[k-1])
    
if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
import heapq
def main():

    input = stdin.readline

    K = int(input())

    h = []

    for i in range(1,10):
        h.append(i)
    
    for i in range(K):
        ans = h[i]

        if ans % 10 != 0:
            h.append(ans * 10 + (ans % 10 - 1))
        h.append(ans*10 + (ans%10))
        if ans % 10 != 9:
            h.append(ans * 10 + (ans % 10 + 1))
    
    print(ans)

    
    
    
    
    

    
    
    
    
    
    
    

if __name__ == "__main__":
    main()

Solution (Python):
def resolve():
    K = int(input())
    from collections import deque
    cnt = 0
    q = deque()
    for i in range(1, 10):
        q.append(i)
    while q:
        num = q.popleft()
        cnt += 1
        if cnt == K:
            ans = num
            break
        mod10 = num % 10
        if mod10 != 0:
            q.append(10*num + mod10 - 1)
        q.append(10*num+mod10)
        if mod10 != 9:
            q.append(10*num + mod10 + 1)
    print(ans)

resolve()

Solution (Python):
import numpy as np

k = int(input())



def check(n):
    digits = []
    while n:
        n, m = divmod(n, 10)
        digits.append(m)
    digits.reverse()

    dp = np.zeros(10, dtype=np.int64)
    dp[1:digits[0]] = 1
    edge = digits[0]
    for d in digits[1:]:
        odp = dp.copy()
        dp[:-1] += odp[1:]
        dp[1:] += odp[:-1]
        dp[1:] += 1
        if edge != -1:
            if edge - 1 > d:
                edge = -1
            elif edge + 1 >= d:
                dp[max(0, edge - 1):d] += 1
                edge = d
            else:
                dp[max(0, edge - 1):edge + 2] += 1
                edge = -1
    result = dp.sum()
    if edge != -1:
        result += 1
    return result >= k


l = 0
r = 3234566667
while l + 1 < r:
    m = (l + r) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)

Solution (Python):

import heapq
que = [i for i in range(1, 10)]
cnt = 0
k = int(input())

for i in range(k):
    x = heapq.heappop(que)
    if (x % 10) > 0:
        heapq.heappush(que, x * 10 + (x % 10) - 1)
    if (x % 10) < 9:
        heapq.heappush(que, x * 10 + (x % 10) + 1)
    heapq.heappush(que, x * 10 + (x % 10))
    
print(x)

Solution (Python):


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

     runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     count = 0
     while(len(runrun) < k):
          target = runrun[count]
          runrun.extend(make(target))
          count += 1
          

     print(runrun[k-1])

def make(n):
     num = n % 10
     if num == 0:
          return [n * 10 + num, n * 10 + num + 1]
     elif num == 9:
          return [n * 10 + num - 1, n * 10 + num]
     else:
          return [n * 10 + num - 1, n * 10 + num, n * 10 + num + 1]

if __name__ == "__main__":
    main()

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

start = 0
end = 9
while k > len(X):
    for i in range(end-start):
        n = str(X[start+i])
        
        if int(n[-1])-1 >= 0:
            X.append(int(n+str(int(n[-1])-1)))
        X.append(int(n+str(n[-1])))
        if int(n[-1])+1 <= 9:
            X.append(int(n+str(int(n[-1])+1)))
    start = end
    end = len(X)
    
print(X[k-1])

Solution (Python):
from collections import deque
k=int(input())
deq=deque(range(1,10))
append=deq.append
popleft=deq.popleft
for _ in range(k):
	c=popleft()
	if c%10==0:
		append(c*10)
		append(c*10+1)
	elif c%10==9:
		append(c*10+8)
		append(c*10+9)
	else:
		append(c*10+c%10-1)
		append(c*10+c%10)
		append(c*10+c%10+1)
print(c)