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):
import collections
k = int(input())
li = [str(i) for i in range(1,10)]
st_li = li[:]

q = collections.deque(li)
count = 0
n = 10 ** 10

for i in range(1,n):
    
    a = q.popleft()
    num = int(a[-1])
    
    if num != 0:
        aa = a + str(num-1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    aa = a + str(num)
    st_li.append(aa)
    q.append(aa)
    count += 1
    if num != 9:
        aa = a + str(num+1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    if count > k:
        print(st_li[k-1])
        exit(0)

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

from collections import deque
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):
K = int(input())
if K < 13:
    print(K)
    quit()

now = list(range(1, 10))

count = 9
while True:
    nxt = []
    for l in now:
        tail = l % 10
        for t in range(max(0, tail - 1), min(10, tail + 2)):
            nxt.append(l * 10 + t)
            count += 1
            if count == K:
                print(l * 10 + t)
                quit()
    now = nxt

Solution (Python):
from collections import deque

K = int(input())

lunlun = deque()

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

for i in range(K - 1):
    x = lunlun[0]
    lunlun.popleft()
    if x % 10 != 0:
        res = 10 * x + x % 10 - 1
        lunlun.append(res)
        
    res = 10 * x + x % 10
    lunlun.append(res)

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

print(lunlun[0])

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

for i in range(k):
    if a[i] % 10 != 0:
        a.append(10*a[i] + a[i] % 10 - 1)
    a.append(10*a[i] + a[i] % 10)
    if a[i] % 10 != 9:
        a.append(10*a[i] + a[i] % 10 + 1)

print(a[k - 1])

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


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


ans = 0
for i in range(K) :
  x = q.get()
  ans = x

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

Solution (Python):
import queue
N = int(input())
Q = [i for i in range(1, 10)]
q = queue.Queue()
for i in Q:
  q.put(i)
count = 0
while count < N:
  n = q.get()
  d = n%10
  for i in range(max([d-1, 0]), min([d+2 , 10])):
    q.put(n*10+i)
  count += 1
print(n)

Solution (Python):
def make_bigger_digit_runrunnum(srcNum):
    num_list = list()
    one_digit_num = srcNum % 10
    if one_digit_num == 9:
        num_list.append(srcNum*10 + one_digit_num - 1)
    elif one_digit_num == 0:
        num_list.append(srcNum*10 + one_digit_num + 1)
    else:
        num_list.append(srcNum*10 + one_digit_num - 1)
        num_list.append(srcNum*10 + one_digit_num + 1)
    num_list.append(srcNum * 10 + one_digit_num)
    return num_list


k = int(input())
count = 0
pre_num_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
if 0 < k < 10:
    print(k)
else:
    count = 9
    while True:
        new_num_list = []
        for num in pre_num_list:
            new_num_list += make_bigger_digit_runrunnum(num)
        if k <= (len(new_num_list) + count):
            print(sorted(new_num_list)[k-count-1])
            break
        pre_num_list = new_num_list
        count += len(pre_num_list)

Solution (Python):
from collections import deque
A = deque(range(1,10))
B = int(input())
for i in range(B):
    C = 0
    C = A.popleft()
    if C % 10 != 0:
        A.append(C * 10 + C%10-1)
    A.append(C * 10 + C%10)
    if C % 10 != 9:
        A.append(C * 10 + C%10+1)
print(C)

Solution (Python):
from collections import deque 
k=int(input())
dq=deque()
for i in range(1,10):
    dq.append(i)

cnt=1
while cnt<k:
    now=dq.popleft()
    if now%10>=1:
        dq.append(now*10+now%10-1)
    dq.append(now*10+now%10)
    if now%10<=8:
        dq.append(now*10+now%10+1)
    cnt+=1
print(dq.popleft())

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

for a in range(1,10):
    que.append(a)
nums = []
while len(nums) <= 1000000:
    if que:
        num = que.popleft()
    nums.append(num)
    for i in range(-1,2):
        plus = (num % 10) + i
        if 0 <= plus < 10:
            new = num*10 + plus
            if new <= 3234566667:
                que.append(new)
            else:
                continue

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

Solution (Python):
import queue

k=int(input())

q=queue.Queue()

for i in range(9):
    q.put(i+1)

c=1

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

print(c)

Solution (Python):
import queue
K = int(input()) -1
q = queue.Queue()
for i in range (1,10):
    q.put(i)
while K > 0:
    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)
    K -= 1
ans = q.get()
print(ans)

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

nums = []
def inc(num):
    if num > 3234566667:
        return None
    if num <= 3234566667:
      nums.append(num)

    end = str(num)[-1:]
    end_num = int(end)

    if end_num < 9:
        inc(num * 10 + end_num + 1)

    inc(num * 10 + end_num)

    if end_num > 0:
        inc(num * 10 + end_num - 1)

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

sort_nums = sorted(nums)
print(sorted(nums)[k - 1])

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

nums = []
def inc(num):
    if num > 3234566667:
        return None
    if num <= 3234566667:
      nums.append(num)

    num_str = str(num)
    end = num_str[-1:]
    end_num = int(end)

    if end_num < 9:
        inc(int(num_str + str(end_num + 1)))
   
    inc(int(num_str + end))
    
    if end_num > 0:
        inc(int(num_str + str(end_num - 1)))

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

sort_nums = sorted(nums)
print(sorted(nums)[k - 1])

Solution (Python):

import queue

k = int(input())

q = queue.Queue()
ans = 0

for i in [1,2,3,4,5,6,7,8,9]:
    q.put(i)

for i in range(k):
    x = q.get()
    if i == k-1:
        ans = x
        break
    
    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("{}".format(ans))

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

def fun(k):
    lun_luns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    index = 0
    while True:
        if len(lun_luns) >= k:
            break
        num = lun_luns[index]
        mod = num%10
        n = num*10
        if mod == 9:
            lun_luns.extend([n+mod-1, n+mod])
        elif mod == 0:
            lun_luns.extend([n, n+1])
        else:
            lun_luns.extend([n+mod-1, n+mod, n+mod+1])
        index += 1
    
    return lun_luns[k-1]

print(fun(k))

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

lis = []

lis.append(1)
lis.append(2)
lis.append(3)
lis.append(4)
lis.append(5)
lis.append(6)
lis.append(7)
lis.append(8)
lis.append(9)

keta = 1

while len(lis) <= k:
    for j in [i for i in lis if len(str(i)) == keta]:
        if j % 10 == 0:
            lis.append( j * 10 )
            lis.append( j * 10 + 1 )
        elif j % 10 == 9:
            lis.append( j * 10 + 9 )
            lis.append( j * 10 + 8 )
        else:
            last = j % 10
            lis.append( j * 10 + last - 1 )
            lis.append( j * 10 + last )
            lis.append( j * 10 + last + 1 )
    keta += 1

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

Solution (Python):


import math
import itertools
import collections








def main():
    K = int(input())
    print(next(itertools.islice(lunlun(), K - 1, None)))

def lunlun():
    q = collections.deque(range(1,10))
    while True:
        x = q.popleft()
        yield x
        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)

if __name__ == "__main__":
    main()

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

Solution (Python):
import queue
k=int(input())
q=queue.Queue()
for i in range(1,10):
    q.put(i)
for i in range(k):
    num=q.get()
    if num%10!=0:
        q.put(num*10+num%10-1)
    q.put(num*10+num%10)
    if num%10!=9:
        q.put(num*10+num%10+1)
        
print(num)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)


def input(): return sys.stdin.readline().rstrip()

K = int(input())
queue = deque(range(1, 10))
for _ in range(K):
    i = queue.popleft()
    if i % 10 >= 1:
        queue.append(i * 10 + (i % 10) - 1)
    queue.append(i * 10 + i % 10)
    if i % 10 <= 8:
        queue.append(i * 10 + (i % 10) + 1)
print(i)

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

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

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

print(ans)

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

Solution (Python):
a = []
 
def dfs(x):
    if x > 3234566667:
        return
    a.append(x)
    for i in range(10):
        if abs(x%10-i) <= 1:
            dfs(x*10+i)

for i in range(1, 10):
  dfs(i)
a = sorted(a)
k = int(input())
print(a[k-1])

Solution (Python):

import sys

def check(k=10):
    li = {'0':("0","1"), "1":("0","1","2"), "2":("1","2","3"),"3":("2","3","4"),
    "4":("3","4","5"),"5":("4","5","6"),"6":("5","6","7"),"7":("6","7","8"),"8":("7","8","9"),"9":("8","9")}
    if k == 1:
        res = set(['1','2','3','4','5','6','7','8','9'])
    else:
        s = check(k-1)
        res = s.copy()
        for i in s:
            for j in li[i[-1]]:
                res.add(i+j)
    return res

def solve(K: int):
    k = K
    s = list(map(int, check()))
    s = sorted(s)
    print(s[k-1])




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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    K = int(input())
    MAX = 20
    dp = [[0] * 10 for _ in range(MAX)]
    dp[1] = [1] * 10
    for i in range(2, MAX):
        for j in range(10):
            dp[i][j] = dp[i-1][j]
            if j >= 1:
                dp[i][j] += dp[i-1][j-1]
            if j < 9:
                dp[i][j] += dp[i-1][j+1]
    total = 0
    idx = 0
    for i in range(MAX):
        tmp = sum(dp[i][1:])
        if total + tmp < K:
            total += tmp
            continue
        idx = i
        break
    K -= total
    ans = [""] * idx
    rng = range(1, 10)
    while idx > 0:
        for i in rng:
            if K <= dp[idx][i]:
                ans[idx-1] = str(i)
                rng = range(max(0, i-1), min(9, i+1)+1)
                break
            K -= dp[idx][i]
        idx -= 1
    print("".join(ans[::-1]))


if __name__ == "__main__":
    main()

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

def block(d, digits, count):
    if d == 1:
        return (digits if count == 1 else None), (count-1)
    s = digits[-1]
    for i in range(max(s-1, 0), min(s+2, 10)):
        answer, count = block(d-1, digits + [i], count)
        if answer:
             return answer, count
    return None, count

def solve():
    if K <= 9:
        return [K]
    count = K - 9
    for d in range(2,10**9):
        for i in range(1,10):
            answer, count = block(d, [i], count)
            if answer:
                return answer

print(''.join(str(d) for d in solve()))

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

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

Solution (Python):
import queue

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

K=int(input())

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

Solution (Python):
N = int(input())
R = list(range(1, 10))
cnt = 0

while True:
    cnt += 1
    p = R[cnt - 1]

    if p % 10 != 0:
        R.append(10 * p + p % 10 - 1)
    R.append(10 * p + p % 10)
    if p % 10 != 9:
        R.append(10 * p + p % 10 + 1)
    if cnt == N:
        break

print(R[cnt - 1])

Solution (Python):
import queue

A = queue.Queue()

k = int(input())

if k < 9:
    print(k)

else:
    cou = 9
    for i in range(1, 10):
        A.put(i)

    while(cou < k):
        tmp = A.get()
        if (tmp % 10) == 0:
            cou += 2
            if cou == k:
                print(tmp * 10 + (tmp % 10) + 1)
                break
            elif k == cou - 1:
                print(tmp * 10 + (tmp % 10))
                break
            else:
                A.put(tmp * 10 + (tmp % 10))
                A.put(tmp * 10 + (tmp % 10) + 1)
            

        elif (tmp % 10) == 9:
            cou += 2
            if cou == k:
                print(tmp * 10 + (tmp % 10))
                break
            elif k == cou - 1:
                print(tmp * 10 + (tmp % 10) - 1)
                break
            else:
                A.put(tmp * 10 + (tmp % 10) - 1)
                A.put(tmp * 10 + (tmp % 10))

        else:
            cou += 3
            
            if cou == k:
                print(tmp*10 + (tmp % 10) + 1)
                break
            elif cou - 1 == k :
                print(tmp * 10 + (tmp % 10))
                break
            elif cou - 2 == k:
                print(tmp * 10 + (tmp % 10) - 1)
                break

            else:
                A.put(tmp * 10 + (tmp % 10) - 1)
                A.put(tmp * 10 + (tmp % 10))
                A.put(tmp * 10 + (tmp % 10) + 1)

Solution (Python):
import sys
def fin_then_output(i):
  if count==n:
    print(ll[i][-1])
    sys.exit()
    
n=int(input())
if n<10:
  print(n)
  sys.exit()
count=9
ll=[[] for _ in [0]*10]
ll[0]=[str(i) for i in range(1,10)] 
for i in range(1,10): 
  for j in range(len(ll[i-1])):
    
    
    
    m = int(ll[i-1][j][-1])
    if m!=0:
      ll[i].append(ll[i-1][j]+str(m-1))
      count+=1
      fin_then_output(i)
    ll[i].append(ll[i-1][j]+str(m))
    count+=1
    fin_then_output(i)
    if m!=9:
      ll[i].append(ll[i-1][j]+str(m+1))
      count+=1
      fin_then_output(i)

Solution (Python):
from collections import deque
k = int(input())
num = ["null"] 
for i in range(10):
    num.append(i)
catalog = [i for i in range(10)] 
q = deque([i for i in range(1, 10)]) 
def bfs(x: str)-> str:
    tmp = []
    ones = int(str(x)[-1]) 
    for i in range(3):
        try:
            tmp.append(int(num[ones+i]) + x*10)
        except:
            pass
    return tmp

while len(catalog) <= k:
    node = q.popleft()
    tmp = bfs(node)
    for i in tmp:
        q.append(i)
        catalog.append(i)

print(catalog[k])

Solution (Python):
K=int(input())
N=0 
lun=list(range(1,10))
while 1:
    N+=1
    x=lun[N-1]
    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)
    if N==K:
        break
print(lun[N-1])

Solution (Python):
import heapq

k = int(input())
l = list(range(1,10))
heapq.heapify(l)
for _ in range(k):
    leftpop = heapq.heappop(l)
    fp = leftpop % 10
    if fp == 0:
        heapq.heappush(l,leftpop * 10)
        heapq.heappush(l,leftpop * 10 + 1)
    elif fp == 9:
        heapq.heappush(l,leftpop * 10 + 9 - 1)
        heapq.heappush(l,leftpop * 10 + 9)
    else:
        heapq.heappush(l,leftpop * 10 + fp - 1)
        heapq.heappush(l,leftpop * 10 + fp)
        heapq.heappush(l,leftpop * 10 + fp + 1)

print(leftpop)

Solution (Python):
k = int(input())
 
n = [1, 2, 3, 4, 5, 6, 7, 8, 9]
if k < len(n):
    print(str(n[k-1]))
else:
    count = 9
    while 1:
        x = n.pop(0)
        if x % 10 != 0:
            n.append(10*x + x % 10 - 1)
            count += 1
        n.append(10*x + x % 10)
        count += 1
        if x % 10 != 9:
            n.append(10*x + x % 10 + 1)
            count += 1
        if count >= k:
            print(n[-(count-k)-1])
            break

Solution (Python):
from collections import deque

K = int(input())
Q = deque([i for i in range(1, min(9, K) + 1)])
ctr = 0

while Q:
    cur = Q.popleft()
    simo = cur % 10
    ctr += 1
    if ctr == K:
        print(cur)
        break
    for dx in [-1, 0, 1]:
        if 0 <= simo + dx <= 9:
            Q.extend([10 * cur + simo + dx])

Solution (Python):


import sys


from collections import deque                















def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    """
    この dp で x 桁までの整数で表現される LunLun number の数を sum([line[1:] for line in dp[:x]]) で計算できる
    1 桁まで考えると 9 個
    2 桁まで考えると 35 個
    3 桁まで考えると 110 個
    4 桁まで考えると 327 個
    5 桁まで考えると 956 個
    6 桁まで考えると 2782 個
    7 桁まで考えると 8089 個
    8 桁まで考えると 23527 個
    9 桁まで考えると 68468 個
    10 桁まで考えると 199368 個
    であることがわかる。 k 番目の LunLun number を求める (k = O(10^5)) ので、10 桁の数くらいにはなりうることがわかった。
    ( ˘-з-)ふーん。
    """

    k = ii()
    cnt = 0
    q = deque(list('123456789'))
    while True:
        top = q.popleft()
        cnt += 1
        if cnt == k:
            break
        last_digit = int(top[-1])
        if last_digit - 1 >= 0:
            q.append(top + str(last_digit - 1))
        q.append(top + str(last_digit))
        if last_digit + 1 <= 9:
            q.append(top + str(last_digit + 1))
    print(top)
    """
    Queue を使う！ (解説チラ見 AC)
    """
        

if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heapify, heappop, heappush


def next_num(n):
    if n == 0:
        return [0, 1]
    elif n == 9:
        return [8, 9]
    else:
        return [n-1, n, n+1]

K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]  
heapify(queue)

for _ in range(K-1):
    now = heappop(queue)  
    
    for next_i in next_num(now%10):
        heappush(queue, now*10 + next_i)

print(queue[0])

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

K1 = [x for x in range(1, 10)]


def add_2(Kn):
    K_ = []
    for i in Kn:
        
        K_.append(10*i + (i % 10 - 1))
        K_.append(10*i + i % 10)
        if i % 10 < 9:
            K_.append(10*i + (i % 10+ 1))

    return K_

def add_(Kn):
    K_ = []
    for i in Kn:
        if i%10 > 0:
            K_.append(10*i + (i % 10 - 1))
        K_.append(10*i + i % 10)
        if i % 10 < 9:
            K_.append(10*i + (i % 10+ 1))

    return K_

out = [K1, add_2(K1)]
for k in range(1, 9):
    out.append(add_(out[k]))

out = sum(out, [])
print(out[K-1])

Solution (Python):
from collections import deque
k = int(input())
q = deque([i for i in range(1, 10)])
if k <= 9:
    print(k)
    quit()

k -= 9

while k > 0:
    a = q.popleft()
    b = a % 10
    if b == 0:
        q.append(10*a)
        q.append(10*a + 1)
        k -= 2
    elif b != 0 and b != 9:
        q.append(10*a + b - 1)
        q.append(10*a + b)
        q.append(10*a + b + 1)
        k -= 3
    elif b == 9:
        q.append(10*a + b-1)
        q.append(10*a + b)
        k -= 2

if k == 0:
    print(q[-1])
elif k == -1:
    print(q[-2])
elif k == -2:
    print(q[-3])

Solution (Python):
from collections import deque
K = int(input())
d = deque(list(range(1, 10)))
for i in range(K - 1):
  a = d[0]
  b = 10 * a + a % 10
  if a % 10 != 0:
    d.append(b - 1)
  d.append(b)
  if a % 10 != 9:
    d.append(b + 1)
  d.popleft()
  
print(d[0])

Solution (Python):
K = int(input())
num = list(range(1, 10))
for i in range(K):
  a = num[i]
  b = 10 * a + a % 10
  if a % 10 != 0:
    num.append(b - 1)
  num.append(b)
  if a % 10 != 9:
    num.append(b + 1)
  if len(num) == K:
    break
print(num[K - 1])

Solution (Python):
K = int(input())
num = list(range(1, 10))
for i in range(K):
  a = num[i]
  b = 10 * a + a % 10
  if a % 10 != 0:
    num.append(b - 1)
  num.append(b)
  if a % 10 != 9:
    num.append(b + 1)
print(num[K - 1])

Solution (Python):
from collections import deque

K = int(input())

queue = deque([])
for i in range(1,9+1):
    queue.append(i)

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

Solution (Python):
L=[]
def search(x):
  if x>3234566667:
    return
  L.append(x)
  search(10*x+x%10)
  if x%10!=0:
    search(10*x+x%10-1)
  if x%10!=9:
    search(10*x+x%10+1)
for i in range(1,10):
  search(i)
L.sort()
k=int(input())
print(L[k-1])

Solution (Python):
import heapq

K = int(input())
Q=list(range(1,10))
heapq.heapify(Q)
for _ in range(K):
    q = heapq.heappop(Q)
    if q%10!=0:
        heapq.heappush(Q,q*10+(q%10)-1)
    if q%10!=9:
        heapq.heappush(Q,q*10+(q%10)+1)
    heapq.heappush(Q,q*10+(q%10))
print(q)

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

num = [1,2,3,4,5,6,7,8,9]
def lunlun(m):
    for i in range(10):
        if(abs((m%10) - i ) <=1):
            if(m*10+i > 3234566667):
                return
            num.append(m*10+i)
            lunlun(m*10+i)

for j in range(1,10):
    lunlun(j)

num = sorted(num)

print(num[k-1])

Solution (Python):
import sys
from collections import deque
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    k=int(input().rstrip())
    lunlun=deque([str(i) for i in range(1,10)])
    for _ in range(k-1):
        now=lunlun.popleft()
        last=now[-1]
        if last!="0":
            lunlun.append(now+str(int(last)-1))
        lunlun.append(now+last)
        if last!="9":
            lunlun.append(now+str(int(last)+1))
        
    print(lunlun[0])

if __name__=="__main__":
    main()

Solution (Python):

def inputlist(): return [int(k) for k in input().split()]

K = int(input())
li = [1,2,3,4,5,6,7,8,9]
from collections import deque
que = deque()
for i in range(1,10):
    que.append(str(i))
while len(li) < K:
    i = que.popleft()
    i0 = i[-1]
    i1 = int(i0)
    if i0 != '9' and i0 != '0':
        nm = [i1-1,i1,i1+1]
        for j in range(3):
            i2 = i + str(nm[j])
            li.append(int(i2))
            que.append(i2)
    if i0 == '9':
        nm = [8,9]
        for j in range(2):
            i2 = i + str(nm[j])
            li.append(int(i2))
            que.append(i2)
    if i0 == '0':
        nm = [0,1]
        for j in range(2):
            i2 = i+str(nm[j])
            li.append(int(i2))
            que.append(i2)
print(li[K-1])

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
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()
q = deque([i+1 for i in range(9)])
while k > 0:
    now = q.popleft()
    tail = int(str(now)[-1])
    for i in range(-1,2):
        if 0 <= tail + i <= 9:
            q.append(int(str(now) + str(tail+i)))
    k -= 1
print(now)

Solution (Python):
K=int(input())
lunlun=[i for i in range(1,10)]

p=0
def generate_lunlun(p):
  last=p%10
  if last!=0:
    yield p*10+last-1
  yield p*10+last
  if last!=9:
    yield p*10+last+1
    
while K>len(lunlun):
  for i in generate_lunlun(lunlun[p]):
    
    lunlun.append(i)
  p+=1
print(lunlun[K-1])

Solution (Python):
k = int(input())
li = [i + 1 for i in range(9)]

c = 0
while len(li) < k:
    if li[c] % 10 != 0:
        li.append(li[c] * 10 + li[c] % 10 - 1)
    li.append(li[c] * 10 + li[c] % 10)
    if li[c] % 10 != 9:
        li.append(li[c] * 10 + li[c] % 10 + 1)
    c += 1
print(li[k - 1])

Solution (Python):
from collections import deque
def runrun():
    count = 0
    while count <= k:
        run = quee.popleft()
        count += 1
        if count == k:
            print(run)
        last_digit = run%10
        if 0 < last_digit < 9:
            quee.extend([run * 10 + last_digit-1 , run * 10 + last_digit, run*10 + last_digit + 1])
        elif last_digit == 0:
            quee.extend([run * 10, run * 10 + 1])
        elif last_digit ==9:
            quee.extend([run*10 + 8, run*10 + 9])


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

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

    K = int(input())

    dq = deque()
    for x in range(1, 10):
        dq.append(x)

    idx = 0
    while dq:
        x = dq.popleft()
        idx += 1
        if idx == K:
            print(x)
            return

        r = x % 10
        if r > 0:
            dq.append(x * 10 + r - 1)
        dq.append(x * 10 + r)
        if r < 9:
            dq.append(x * 10 + r + 1)


if __name__ == '__main__':
    main()

Solution (Python):
k = int(input())
lunlun = list(range(1, 10))

for i in range(k - 1):
    a = lunlun[i]
    b = a * 10 + a % 10
    if a % 10 != 0:
        lunlun.append(b - 1)
    lunlun.append(b)
    if a % 10 != 9:
        lunlun.append(b + 1)
print(lunlun[k - 1])

Solution (Python):
k = int(input())
lunlun = list(range(1, 10))

for i in range(k - 1):
    a = lunlun[i]
    b = a * 10 + a % 10
    if a % 10 != 0:
        lunlun.append(b - 1)
    lunlun.append(b)
    if a % 10 != 9:
        lunlun.append(b + 1)
print(lunlun[k - 1])

Solution (Python):
k = int(input())
lunlun = list(range(1, 10))
 
for i in range(k-1):
    a = lunlun[i]
    b = a * 10 +  a % 10 
    if a % 10 != 0:
        lunlun.append(b - 1)
    lunlun.append(b)
    if a % 10 != 9:
        lunlun.append(b + 1)
 
print(lunlun[k-1])

Solution (Python):
def dfs(s,l):
  if s!="":
    if len(s)>10 or s[0]=="0":
      return
  if s!="":
    l.append(int(s))
  for c in "0123456789":
    if s!="":
      if abs(int(s[-1])-int(c))<=1:
        dfs(s+c,l)
    else:
      if c!="0":
        dfs(s+c,l)

k=int(input())
l=[]
dfs("",l)
l.sort()
print(l[k-1])

Solution (Python):
from collections import deque


K = int(input())

que = deque(["1","2","3","4","5","6","7","8","9"])
cnt = 0
while cnt < K:
    q = que.popleft()
    a = int(q[-1])
    q = int(q)
    cnt += 1 
    if a == 0:
        que.append(str(q*10+a))
        que.append(str(q*10+a+1))
    elif a == 9:
        que.append(str(q*10+a-1))
        que.append(str(q*10+a))
    else:
        que.append(str(q*10+a-1))
        que.append(str(q*10+a))
        que.append(str(q*10+a+1))
    ans = q

print(ans)

Solution (Python):
k = int(input())
pool = [i for i in range(1,10)]
i = 0
while len(pool) < k:
    n = int(str(pool[i]) + str(pool[i])[-1])
    if n%10 == 0:
        pool += [n, n+1]
    elif n%10 == 9:
        pool += [n-1, n]
    else:
        pool += [n-1, n, n+1]
    i += 1
print(pool[k-1])

Solution (Python):
k = int(input())
lunlun = list(range(1, 10))

for i in range(k-1):
    a = lunlun[i]
    b = a * 10 +  a % 10 
    if a % 10 != 0:
        lunlun.append(b - 1)
    lunlun.append(b)
    if a % 10 != 9:
        lunlun.append(b + 1)

print(lunlun[k-1])

Solution (Python):
from collections import deque

K = int(input())
d = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
pop = 0
now = 0
while K > pop:
    now = d.popleft()
    if now % 10 != 0:
        d.append(now * 10 + (now % 10 - 1))
    d.append(now * 10 + (now % 10))
    if now % 10 != 9:
        d.append(now * 10 + (now % 10 + 1))
    pop += 1
print(now)

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

DP = [[1 for i in range(10)] for j in range(12)]


for j in range(1, 12):
    
    for i in range(10):
        DP[j][i] = DP[j-1][i]
        if i != 0:
            DP[j][i] += DP[j-1][i-1]
        if i != 9:
            DP[j][i] += DP[j-1][i+1]
s = 0

res = ""
for j in range(12):
    for i in range(1, 10):
        prev = s
        s += DP[j][i]
        if s >= K:
            res += str(i)
            
            break
    if s >= K:
        break

top = i
keta = j
sa = K - prev
for k in range(keta-1, -1, -1):
    t = 0
    for j in range(max(0, top-1), min(9, top+1)+1):
        
        t_prev = t
        t += DP[k][j]
        if t >= sa:
            res += str(j)
            sa -= t_prev
            top = j
            break
print(res)

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

    def dfs(s):
        if 3234566667 < int(s):
            return
        c = int(s[-1])
        for p in range(-1, 2):
            if c+p < 0 or 9 < c+p:
                continue
            LL.add(int(s+str(c+p)))
            dfs(s+str(c+p))

    for s in "123456789":
        LL.add(int(s))
        dfs(s)

    ans = sorted(LL)
    print(ans[K-1])


if __name__ == '__main__':
    main()

Solution (Python):
def generate(num):
    n = int(str(num)[-1])
    if n != 0:
        yield num * 10 + n - 1
    yield num * 10 + n
    if n < 9:
        yield num * 10 + n + 1

k = int(input())
lunlun = [i for i  in range(1, 10)]
p = 0
while len(lunlun) < k:
    for l in generate(lunlun[p]):
        lunlun.append(l)
    p += 1
print(lunlun[k - 1])

Solution (Python):
import queue

k=int(input())

cnt=0
q=queue.Queue()

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

while True:
    dq=q.get()
    if dq%10!=0:
        q.put(10*dq+dq%10-1)
    q.put(10*dq+dq%10)
    if dq%10!=9:
        q.put(10*dq+dq%10+1)
    cnt+=1
    if cnt==k:
        print(dq)
        break