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.



Sample input:
15


Sample output:
23

Submission status: Accepted

Solution code:
import collections
k = int(input())
count = 0
queue = collections.deque(['1','2','3','4','5','6','7','8','9'])
if k <= 12:
    print(k)
else:
    for i in range(k):
        t = queue.popleft()
        s = int(t[-1])
        if(s == 0):
            queue.extend([t + str(s),t + str(s + 1)])
            count+=1
        elif(s == 9):
            queue.extend([t + str(s-1),t + str(s)])
        else:
            queue.extend([t + str(s-1),t + str(s),t + str(s+1)])
            count += 1
    print(int(t))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

k = int(readline())
q = deque(list(map(str, list(range(1, 10)))))
for i in range(k - 1):
    x = q.popleft()
    y = int(x[-1])
    if y != 0:
        q.append(x + str(y - 1))
    q.append(x + x[-1])
    if y != 9:
        q.append(x + str(y + 1))
print(q[0])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

d = deque()
for i in range(1,10):
  d.append(i)
for j in range(k):
  a = d.popleft()
  b = a%10
  if b != 0:
    d.append(10*a+b-1)
  d.append(10*a+b)
  if b != 9:
    d.append(10*a+b+1)
print(a)

Submission status: Accepted

Solution code:
# d: 現在のケタ数
# val: 現在の値
# all: ここに格納していく(参照型にしておく)


def rec(d: int, val: int, all):
    all.append(val)

    if d == 10:
        return

    for i in range(-1, 2):
        add = (val % 10) + i
        if add >= 0 and add <= 9:
            rec(d+1, val*10+add, all)


def main():
    K = int(input())
    all = []
    for v in range(1, 10):
        rec(1, v, all)
    all.sort()
    print(all[K-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K = int(input())

from collections import deque

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

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)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

k = int(input())
l = ["1", "2", "3", "4", "5", "6", "7",  "8", "9"]
m =  ["1", "2", "3", "4", "5", "6", "7",  "8", "9"]
queue = deque(["1", "2", "3", "4", "5", "6", "7",  "8", "9"])
while len(l)<k+1:
    i = queue.popleft()
    if i[-1] == "0":
        l.append(i+"0")
        l.append(i+"1")
        queue.append(i+"0")
        queue.append(i+"1")
    
    elif i[-1] == "9":
        l.append(i+"8")
        l.append(i+"9")
        queue.append(i+"8")
        queue.append(i+"9")
    else:
        l.append(i+str(int(i[-1])-1))
        l.append(i+str(int(i[-1])))
        l.append(i+str(int(i[-1])+1))
        queue.append(i+str(int(i[-1])-1))
        queue.append(i+str(int(i[-1])))
        queue.append(i+str(int(i[-1])+1))

print(l[k-1])

Submission status: Accepted

Solution code:
from queue import Queue

K = int(input())

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

for k in range(K-1):
    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(q.get())

Submission status: Accepted

Solution code:
from sys import stdin,stdout
from queue import Queue

def solve(K):
    if K < 10: return K
    q = Queue()
    cnt = 0
    for i in range(1,10):
        q.put(i)

    while not q.empty():
        u = q.get()
        cnt += 1
        if cnt == K: return u

        r = u % 10
        if r != 0:
            q.put(10*u + r - 1)

        q.put(10*u + r)
        if r < 9:
            q.put(10*u + r +1)





K = int(stdin.readline())

stdout.write(str(solve(K)))

Submission status: Accepted

Solution code:
import queue 
q=queue.Queue() 
n=int(input()) 
q.put(1)
q.put(2)
q.put(3)
q.put(4)
q.put(5)
q.put(6)
q.put(7)
q.put(8)
q.put(9) 
j=1 
while j<n:
    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 )
    j+=1 
print(q.get())

Submission status: Accepted

Solution code:
from collections import deque

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

cnt = 0
while cnt < K-1:
    n = q.popleft()
    d = int(str(n)[-1])
    cnt += 1
    for i in [d-1, d, d+1]:
        if(i < 0 or 10 <= i):
            continue
        q.append(10*n+i)
print(q.popleft())

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n, = map(int, input().split())
    # print(n)
    q = list(range(1, 10))
    count = 0
    while True:
      a = q.pop(0)
      count += 1
      if count == n:
        print(a)
        break
      end = a % 10
      end_1 = end - 1
      end_2 = end + 1
      if end_1 >= 0:
        q.append(10*a + end_1)
      q.append(10*a + end)
      if end_2 <= 9:
        q.append(10*a + end_2)

Submission status: Accepted

Solution code:
# coding: utf-8
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()
que = deque(range(1, 10))
count = 0
while count < K-1:
    count += 1
    x = que.popleft()
    remain = x % 10
    if remain > 0:
        que.append(10*x + remain - 1)
    que.append(10*x + remain)
    if remain < 9:
        que.append((10*x + remain + 1))

answer = que.popleft()
print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(10 ** 7)

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

K = ir()
num = -1

def dfs(A, i, bl):
    global num
    if i == 11:
        num += 1
        if num == K:
            ans = ''.join(map(str, A))
            ans = int(ans)
            print(ans)
            exit()
        return
    last = A[-1]
    if bl:
        dfs([0], i+1, True)
        for j in range(1, 10):
            dfs([j], i+1, False)
    else:
        if last > 0:
            dfs(A+[last-1], i+1, False)
        dfs(A+[last], i+1, False)
        if last < 9:
            dfs(A+[last+1], i+1, False)

dfs([0], 0, True)

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def myappend(n):
    sn = str(n)
    nlast = n%10
    if nlast == 0:
        d.append(10*n + nlast)
        d.append(10*n + nlast + 1)
    elif nlast == 9:
        d.append(10*n + nlast - 1)
        d.append(10*n + nlast)
    else:
        d.append(10*n + nlast - 1)
        d.append(10*n + nlast)
        d.append(10*n + nlast + 1)

cnt = 0
while d:
    val = d.popleft()
    cnt += 1
    if cnt == K:
        print(val)
        exit()
    myappend(val)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque 
def main():
    K = int(readline())
    dq = deque() 
    cnd = []
    for i in range(1, 10):
        dq.append(i)
        cnd.append(i)
    
    while len(dq)>0:
        v = dq.popleft()
        r = v%10 
        if r == 0:
            nx = v*10
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+1
            dq.append(nx)
            cnd.append(nx)
        elif r == 9:
            nx = v*10+8
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+9
            dq.append(nx)
            cnd.append(nx)
        else:
            nx = v*10+(r-1)
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+r
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+(r+1)
            dq.append(nx)
            cnd.append(nx)
        if len(cnd) > K: 
            break
    print(cnd[K-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque 
def main():
    K = int(readline())
    dq = deque() 
    cnd = []
    for i in range(1, 10):
        dq.append(i)
        cnd.append(i)
    
    while len(dq)>0:
        v = dq.popleft()
        r = v%10 
        if r == 0:
            nx = v*10
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+1
            dq.append(nx)
            cnd.append(nx)
        elif r == 9:
            nx = v*10+8
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+9
            dq.append(nx)
            cnd.append(nx)
        else:
            nx = v*10+(r-1)
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+r
            dq.append(nx)
            cnd.append(nx)
            nx = v*10+(r+1)
            dq.append(nx)
            cnd.append(nx)
        if len(cnd) > K: 
            break
    print(cnd[K-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k = int(input())
ans = [[i for i in range(1, 10)]]
d = 9
while d < k:
    ans.append([])
    for i in ans[-2]:
        x = str(i)
        z = int(x[-1])
        ans[-1].append(x + str(z))
        if z <= 8:
            ans[-1].append(x + str(z + 1))
        if z >= 1:
            ans[-1].append(x + str(z - 1))
    d += len(ans[-1])
ans[-1].sort()
print(ans[-1][k - d - 1])

Submission status: Accepted

Solution code:
import math
K = int(input().split()[0])

s = [[0 for _ in range(10)] for _ in range(20)]

for i in range(10):
    s[0][i] = 1

for n in range(1,20):
    for i in range(10):
        if i == 0:
            s[n][i] = s[n-1][i]+s[n-1][i+1]
        elif i == 9:
            s[n][i] = s[n-1][i-1]+s[n-1][i]
        else:
            s[n][i] = s[n-1][i-1]+s[n-1][i]+s[n-1][i+1]

i = -1
Sm = 0
SmOld = 0
while True:
    i += 1
    Sm += sum(s[i][1:])
    if Sm > K:
        Sm = SmOld
        break
    SmOld = Sm

k = 10**i
while True:
    a = list(map(int,str(k)))
    flag = True
    for h in range(i,0,-1):
        if abs(a[h-1]-a[h]) < 2:
            continue
        else:
            flag = False
            k = k-k%(10**(i-h))+10**(i-h)
            break
    if not flag:
        continue
    Sm += 1
    if Sm == K:
        print(k)
        break
    k += 1

Submission status: Accepted

Solution code:
from collections import deque


k = int(input())
if k<=9:
    print(k)
    exit()

run = deque([int(i) for i in range(1,10)])
rli = [int(i) for i in range(1,10)]
i=0
while len(rli)<=k:
    
    p = run.popleft()
    j=p%10
    if p%10 == 9:
        for h in range(-1,1):
            n = p*10+j+h
            rli.append(n)
            run.append(n)
    elif p%10 == 0:
        for h in range(0,2):
            n = p*10+j+h
            rli.append(n)
            run.append(n)
    else:
        
        for h in range(-1,2):
            n = p*10+j+h
            rli.append(n)
            run.append(n)
    
print(rli[k-1])

Submission status: Accepted

Solution code:
import heapq

k = int(input())

num_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
mae = 0

if k <= 9:
    print(k)
else:
    k -= 9
    q = []
    heapq.heapify(q)
    for i in range(1, 10):
        heapq.heappush(q, i)
    temp = 0
    while temp < 9:
        temp += 1
        num = heapq.heappop(q)
        if temp == 9:
            heapq.heappush(q, num*10 + num_list[(num%10)-1])
            heapq.heappush(q, num*10 + num_list[(num%10)])
        else:
            heapq.heappush(q, num*10 + num_list[(num%10)-1])
            heapq.heappush(q, num*10 + num_list[(num%10)])
            heapq.heappush(q, num*10 + num_list[(num%10)+1])
    while k > 0:
        k -= 1
        num = heapq.heappop(q)
        if num == mae:
            k += 1
            continue
        elif num%10 == 0:
            heapq.heappush(q, num*10 + num_list[(num%10)])
            heapq.heappush(q, num*10 + num_list[(num%10)+1])
        elif num%10 == 9:
            heapq.heappush(q, num*10 + num_list[(num%10)-1])
            heapq.heappush(q, num*10 + num_list[(num%10)])
        else:
            heapq.heappush(q, num*10 + num_list[(num%10)-1])
            heapq.heappush(q, num*10 + num_list[(num%10)])
            heapq.heappush(q, num*10 + num_list[(num%10)+1])
        mae = num
    print(num)

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
que = deque()
que.extend([i for i in range(1,10)])

for k in range(K-1):
    out = que.popleft()
    div = out%10
    if div==0:
        que.extend([out*10,out*10+1])
    elif out%10==9:
        que.extend([out*10+8,out*10+9])
    else:
        que.extend([out*10-1+div,out*10+div,out*10+1+div])
print(que.popleft())

Submission status: Accepted

Solution code:
from collections import deque
num=deque([1,2,3,4,5,6,7,8,9])
cnt=0
K=int(input())
while(True):
    a=num.popleft()
    cnt+=1
    if cnt==K:
        print(a)
        exit()
    if a%10==0:
        a1=a*10
        a2=a1+1
        num.append(a1)
        num.append(a2)
    elif a%10==9:
        a1=a*10+(a%10)-1
        a2=a*10+(a%10)
        num.append(a1)
        num.append(a2)
    else:
        a1 = a * 10 + (a % 10) - 1
        a2 = a * 10 + (a % 10)
        a3 = a * 10 + (a % 10) + 1
        num.append(a1)
        num.append(a2)
        num.append(a3)

Submission status: Accepted

Solution code:
from collections import deque


k = int(input())
queue = deque([i for i in range(1, 10)])

ans = 1
for _ in range(k):
    ans = queue.popleft()
    right_digit = ans % 10
    if right_digit == 0:
        queue.append(ans * 10 + right_digit)
        queue.append(ans * 10 + right_digit + 1)
    elif right_digit == 9:
        queue.append(ans * 10 + right_digit - 1)
        queue.append(ans * 10 + right_digit)
    else:
        queue.append(ans * 10 + right_digit - 1)
        queue.append(ans * 10 + right_digit)
        queue.append(ans * 10 + right_digit + 1)
print(ans)

Submission status: Accepted

Solution code:
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(10 * x + (x % 10) - 1)
    q.put(10 * x + (x % 10))
    if x % 10 != 9:
        q.put(10 * x + (x % 10) + 1)

print(x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
k = int(input())
lun = []

def dfs(a, last):
    if len(a) > 0:
        lun.append(int(a))
    if len(a) > 11:
        return
    if len(a) == 0:
        for i in range(1, 10):
            a += str(i)
            dfs(a, i)
            a = a[:-1]
    else:
        if last == 0:
            candidates = [last, last + 1]
        elif last == 9:
            candidates = [last - 1, last]
        else:
            candidates = [last - 1, last, last + 1]
        for j in candidates:
            a += str(j)
            dfs(a, j)
            a = a[:-1]

dfs('', 0)
lun.sort()
print(lun[k - 1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
q = deque([i for i in range(1, 10)])

cnt = 0
while cnt < K-1:
    n = q.popleft()
    d = int(str(n)[-1])
    cnt += 1
    for i in [d-1, d, d+1]:
        if i < 0 or 10 <= i:
            continue
        q.append(10*n+i)
print(q.popleft())

Submission status: Accepted

Solution code:
def f(k):
    if 1 <= k <= 9:
        print(k)
    else:
        nxt = [[0,1], [0,1,2], [1,2,3], [2,3,4], [3,4,5], [4,5,6], [5,6,7], [6,7,8], [7,8,9], [8,9]]
        cum_npi = [0, 9, 35, 110, 327, 956, 2782, 8089, 23527, 68468, 199368]
        for length, begin in enumerate(cum_npi):
            if k < begin:
                found = cum_npi[length - 1]
                break
        begin = 10 ** (length - 1)
        # length, begin, found
        k -= found
        x = [[]] * (length + 1)
        x[1] = list(range(1, 10))
        # x

        terminate = False
        i = 1
        while True:
            #print(f"a) i = {i}  x = {x}")
            if len(x[i]): # len(x[i])
                digit = x[i][0]
                if i < length: # i, length
                    i += 1
                    x[i] = nxt[digit].copy()
                    #print(f"x) digit = {digit}  nxt[digit] = {nxt[digit]}  i = {i}  x[i] = {x[i]}")
                    #print(f"b) i = {i}  x = {x}")
                    if i == length: # i, length
                        while len(x[i]): # i, x[i]
                            k -= 1
                            #print(f"c) i = {i}  x = {x}, k = {k}")
                            if k == 0:
                                x.pop(0)
                                #print("answer =", x)
                                ans = "".join([str(j.pop(0)) for j in x])
                                print(ans)
                                terminate = True
                                break
                            else:
                                x[i].pop(0)
                            #print(f"d) i = {i}  x = {x}")
                        else:
                            #print(f"e) i = {i}  x = {x}")
                            while len(x[i]) == 0:
                                i -= 1
                                x[i].pop(0)
                        if terminate:
                            break

f(int(input()))

Submission status: Accepted

Solution code:
import copy
K = int(input())
# N, K = [int(_) for _ in input().split()]
L = [str(i) for i in range(1, 10)]
a = [str(i) for i in range(1, 10)]
for i in range(10):
    new_l = []
    for l in L:
        if l[-1] == '0':
            new_l.append(l + l[-1])
            new_l.append(l + str(int(l[-1]) + 1))
        elif l[-1] == '9':
            new_l.append(l + l[-1])
            new_l.append(l + str(int(l[-1]) - 1))
        else:
            new_l.append(l + l[-1])
            new_l.append(l + str(int(l[-1]) + 1))
            new_l.append(l + str(int(l[-1]) - 1))
    a.extend(new_l)
    L = copy.deepcopy(new_l)

a_int = [int(x) for x in a]
a_int.sort()
print(a_int[K-1])

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())

que=deque([1,2,3,4,5,6,7,8,9])
for _ in range(k):
    x=que.popleft()
    if x%10!=0:
        que.append(x*10+x%10-1)
    que.append(x*10+x%10)
    if x%10!=9:
        que.append(x*10+x%10+1)
print(x)

Submission status: Accepted

Solution code:
K=int(input())
ANS=[i for i in range(1,10)]
i=0
while len(ANS)<=10**5:
  last=str(ANS[i])[-1]
  if last=="0":
    ANS+=[ANS[i]*10,ANS[i]*10+1]
  elif last=="9":
    ANS+=[ANS[i]*10+8,ANS[i]*10+9]
  else:
    ANS+=[ANS[i]*10+int(last)-1,ANS[i]*10+int(last),ANS[i]*10+int(last)+1]
  i+=1  
ans=ANS[K-1]
print(ans)

Submission status: Accepted

Solution code:
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()
    cand = x%10
    if(cand != 0):
        d.append(10*x+cand-1)
    d.append(10*x+cand)
    if(cand != 9):
        d.append(10*x+cand+1)

print(x)

Submission status: Accepted

Solution code:
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()
  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)

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
limit = 10#最大桁数

start = [i for i in range(1, 10)]#最初にスタートする数
ans = []
q=deque(start)
while q:
	num=q.popleft()
	if len(str(num))>11:#処理終了
		continue#次のQへ
	ans.append(num)
	last=str(num)[-1]
	if last == "0":
		add = ['0', '1']
	elif last == '9':
		add = ['8',"9"] 
	else:
		add = [str(int(last) - 1), str(int(last)), str(int(last) + 1)]
	for i in add:
		q.append(int(str(num)+i))

ans = sorted(ans)
print(ans[k - 1])#k番目の答えを創出

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
limit = 10

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

while q:
    cur = q.popleft()
    if len(str(cur)) > 11:
        continue
    ans.append(cur)
    r = str(cur)[-1]
    if r == '0':
        add = ['0', '1']
    elif r == '9':
        add = ['8', '9']
    else:
        add = [str(int(r) - 1), str(int(r)), str(int(r) + 1)]

    for i in add:
        q.append(int(str(cur) + i))

ans = sorted(ans)
print(ans[k - 1])

Submission status: Accepted

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

print(x)

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
limit = 10#最大桁数

start = [i for i in range(1, 10)]#最初にスタートする数
ans = []
def DFS(num):
	if len(str(num))>11:#処理終了
		return 1
	ans.append(num)
	last=str(num)[-1]
	if last == "0":
		add = ['0', '1']
	elif last == '9':
		add = ['8',"9"] 
	else:
		add = [str(int(last) - 1), str(int(last)), str(int(last) + 1)]
	for i in add:
		DFS(int(str(num)+i))

for j in start:
	DFS(j)

ans = sorted(ans)
print(ans[k - 1])#k番目の答えを創出

Submission status: Accepted

Solution code:
K = int(input())
L = [list(range(1, 10))]
A = list(range(1, 10))
for _ in range(9):
    M = []
    for m in L[-1]:
        m = str(m)
        i = int(m[-1])
        cand = []
        if i == 0:
            cand = ['0', '1']
        elif i == 9:
            cand = ['8', '9']
        else:
            cand = [str(i - 1), str(i), str(i + 1)]
        for c in cand:
            M += [int(m + c)]
    L += [M]
    A += M
print(A[K - 1])

Submission status: Accepted

Solution code:
K=int(input())
nums=[i for i in range(1,10)]
for i in range(K):
    a=nums.pop(0)
    if a%10!=0:
        nums.append(a*10 + a%10 - 1)
    
    nums.append(a*10 + a%10)
    
    if a%10!=9:
        nums.append(a*10 + a%10 + 1)

print(a)

Submission status: Accepted

Solution code:
def main3():
        K = int(input())

        record = []

        def rec(d, val, record):
                # store
                record.append(val)
                # finish if val>10^10
                if d==10:
                        return
                # 末尾に適切な数をくっつけて桁をあげる
                for i in range(-1,2):
                        add = (val%10)+i
                        if add>=0 and add<=9:
                                rec(d+1,val*10+add,record)

        for v in range(1,10):
                rec(1, v, record)

        record.sort()

        print("{}".format(record[K-1]))



if __name__=="__main__":
        main3()

Submission status: Accepted

Solution code:
k=int(input())

from collections import deque

cnt=1
q=deque([1,2,3,4,5,6,7,8,9])
while cnt<k:
    tmp=q.popleft()
    if tmp%10!=0:
        q.append(tmp*10+tmp%10-1)
    q.append(tmp*10+tmp%10)
    if tmp%10!=9:
        q.append(tmp*10+tmp%10+1)
    cnt+=1

print(q.popleft())

Submission status: Accepted

Solution code:
import collections
K = int(input())

que = collections.deque()
for i in range(1, 10, 1):
    que.append(i)
cnt = 0
for i in range(K):
    x = que.popleft()
    cnt += 1
    if cnt == K:
        print(x)
        exit()
    if x%10 == 0:
        que.append(10*x+0)
        que.append(10*x+1)
    elif x%10 == 9:
        que.append(10*x+8)
        que.append(10*x+9)
    else:
        que.append(10*x+(x%10)-1)
        que.append(10*x+(x%10)+0)
        que.append(10*x+(x%10)+1)

Submission status: Accepted

Solution code:
K = int(input())

lunlun_number_list = []

def dfs(N):
    lunlun_number_list.append(N)
    if len(str(N)) > 10:
        return
    now_int = int(str(N)[-1])
    if now_int == 0:
        for i in range(2):
            dfs(N*10 + i)
    elif now_int == 9:
        for i in range(8, 10, 1):
            dfs(N*10 + i)
    else:
        for i in range(now_int-1, now_int+2, 1):
            dfs(N*10 + i)

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

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

Submission status: Accepted

Solution code:
k = int(input())
l = 10
A = [str(i+1) for i in range(9)]
B= ["0"]+A
ans = []

def dfs(num):
    if len(num)>=l:
        ans.append(int(num))
    else:
        ans.append(int(num))
        for i in B:
            if abs(int(num[-1])-int(i))<2:
                dfs(num+i)
if k<=9:
    print(k)
else:
    for i in A:
        dfs(i)
    ans = sorted(ans)
    print(ans[k-1])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

def dfs(base, n):
    global K, cnt, ans, flag
    if flag:
        return
    if n == 0:
        cnt += 1
        if cnt == K:
            ans = int(base)
            flag = True
            return
    else:
        last = int(base[-1])
        for l in range(max(0, last-1), min(10, last+2)):
            nextbase = base + str(l)
            dfs(nextbase, n-1)


def main():
    global K, ans, cnt, flag
    K = int(input())
    if K < 10:
        print(K)
        return
    leftK = int(str(K)[0])
    cnt = 9; ans = 0
    flag = False
    for keta in range(1, 10):
        for i in range(1, 10):
            dfs(str(i), keta)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())

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

Submission status: Accepted

Solution code:
k = int(input())

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

k = int(input())
l = 10
A = [str(i+1) for i in range(9)]
B = ["0"] + A
ans = []
#print(l)

def dfs(num,l):
    if len(num) >= l:
        ans.append(int(num))
    else:
        ans.append(int(num))
        for i in B:
            if abs(int(num[-1])-int(i)) < 2:
                dfs(num + i,l)
if k <= 9:
    print(k)
else:
    for i in A:
        dfs(i,l)
    ans = sorted(ans)
    #print(ans)
    print(ans[k-1])

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    k = int(input())
    count = 0
    q = deque()
    for i in range(1, 10):
        q.append(str(i))
    while True:
        qi = q.popleft()
        last = int(qi[-1])
        if last != 0:
            q.append(qi + str(last - 1))
        q.append(qi + str(last))
        if last != 9:
            q.append(qi + str(last + 1))
        count += 1
        if count == k:
            print(qi)
            break


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
ans = []

def dfs(keta, value):
    ans.append(value)
    if keta == 10:
        return

    for j in range(-1, 2):
        add = (value % 10) + j
        if add >= 0 and add <= 9:
            dfs(keta+1, value * 10 + add)

def solve_D():
    k = int(input())
    for i in range(1, 10):
        dfs(1, i)
    ans.sort()
    return ans[k-1]


print(solve_D())

Submission status: Accepted

Solution code:
N = int(input())
R=[["1","2","3","4","5","6","7","8","9"]]
count=9
temp=[]
for i in range(N):
  if count>=N:
    break
  else:
    temp=[]
    for r in R[i]:
      if r[-1]=="9":
        temp.append(str(r)+str(int(r[-1])-1))
        temp.append(str(r)+str(int(r[-1])))
      elif r[-1]=="0":
        temp.append(str(r)+str(int(r[-1])))
        temp.append(str(r)+str(int(r[-1])+1))
      else:
        temp.append(str(r)+str(int(r[-1])-1))
        temp.append(str(r)+str(int(r[-1])))
        temp.append(str(r)+str(int(r[-1])+1))
    R.append(temp)
    count+=len(temp)
N=N-(count-len(temp))
print(R[-1][N-1])

Submission status: Accepted

Solution code:
k = int(input())
q = [1,2,3,4,5,6,7,8,9]
count = 0
if k <= 9:
    print(k)
else:
    while not count == k:
        count += 1
        x = q.pop(0)
        if x % 10 == 9:
            q.append(x * 10 + x % 10 -1)
            q.append(x * 10 + x % 10)
        elif x % 10 == 0:
            q.append(x * 10 + x % 10)
            q.append(x * 10 + x % 10 + 1)
        else:
            q.append(x * 10 + x % 10 - 1)
            q.append(x * 10 + x % 10)
            q.append(x * 10 + x % 10 + 1)
    print(x)

Submission status: Accepted

Solution code:
from queue import Queue

n = int(input())
if n <= 10:
    print(n)
    exit()
n -= 9
que = Queue()
for i in range(1, 10):
    que.put(i)

while True:
    i = str(que.get())
    last = int(i[-1])
    if last != 0:
        if n == 1:
            print(int(i+str(last-1)))
            break
        que.put(int(i+str(last-1)))
        n -= 1
    if n == 1:
        print(int(i+str(last)))
        break
    que.put(int(i+str(last)))
    n -= 1
    if last != 9:
        if n == 1:
            print(int(i+str(last+1)))
            break
        que.put(int(i+str(last+1)))
        n -= 1

Submission status: Accepted

Solution code:
def LunLun(k, count, base):
    nx = []
    n = len(base)
    if count + n >= k:
        ans = base[k - count - 1]
        print(ans)
        exit()

    for x in base:
        count += 1
        p = x % 10
        x *= 10
        a = x + p - 1
        b = a + 1
        c = b + 1
        n = 3
        if p == 0:
            n -= 1
            nx.extend([b, c])
        elif p == 9:
            n -= 1
            nx.extend([a, b])
        else:
            nx.extend([a, b, c])

    LunLun(k, count, nx)


def main():
    k = int(input())
    base = range(1, 10)
    LunLun(k, 0, base)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def LunLun(k, count, base):
    nx = []
    n = len(base)
    if count + n >= k:
        ans = base[k - count - 1]
        print(ans)
        exit()

    for x in base:
        count += 1
        p = x % 10
        x *= 10
        a = x + p - 1
        b = a + 1
        c = b + 1
        n = 3
        if p == 0:
            n -= 1
            nx.extend([b, c])
        elif p == 9:
            n -= 1
            nx.extend([a, b])
        else:
            nx.extend([a, b, c])

    return LunLun(k, count, nx)


def main():
    k = int(input())
    base = range(1, 10)
    LunLun(k, 0, base)
    

if __name__ == '__main__':
    main()