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 sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    k = int(input())
    queue = list(range(1, 10))
    cnt = 0
    for v in queue:
        cnt += 1
        if k == cnt:
            print(v)
            return
        r = v % 10
        for d in range(r - 1, r + 2):
            if 0 <= d <= 9:
                queue.append(v * 10 + d)
resolve()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import deque

K=int(input())
d = deque()

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

for i in range(1,K):
    s = d.popleft()
    v = s%10
    if v>0:
        d.append(10*s+v-1)
    d.append(10*s+v)
    if v<9:
        d.append(10*s+v+1)
print(d.popleft())

Submission status: Accepted

Solution code:
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 i == k-1:
        print(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)

Submission status: Accepted

Solution code:
K=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
  q.put(i)
for j in range(1,K+1):
  x=q.get(j)
  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:
def dfs(d:int, v:int, all:list):
    if d==11:
        return
    all.append(v)
    if list(str(v))[-1]=="0":
        dfs(d+1,10*v+int(list(str(v))[-1])+1,all)
        dfs(d+1,10*v+int(list(str(v))[-1]),all)
    elif list(str(v))[-1]=="9":
        dfs(d+1,10*v+int(list(str(v))[-1])-1,all)
        dfs(d+1,10*v+int(list(str(v))[-1]),all)
    else:
        dfs(d+1,10*v+int(list(str(v))[-1])+1,all)
        dfs(d+1,10*v+int(list(str(v))[-1]),all)
        dfs(d+1,10*v+int(list(str(v))[-1])-1,all)
k=int(input())
all=[]
for i in range(1,10):
    dfs(1,i,all)
all.sort()
print(all[k-1])

Submission status: Accepted

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

for i in range(k):
    x=que.popleft()
    if list(str(x))[-1]=="0":
        que.append(x*10+int(list(str(x))[-1]))
        que.append(x*10+int(list(str(x))[-1])+1)
    elif list(str(x))[-1]=="9":
        que.append(x*10+(int(list(str(x))[-1])-1))
        que.append(x*10+int(list(str(x))[-1]))
    else:
        que.append(x*10+int(list(str(x))[-1])-1)
        que.append(x*10+int(list(str(x))[-1]))
        que.append(x*10+int(list(str(x))[-1])+1)

print(x)

Submission status: Accepted

Solution code:
x=int(input())
next=[]
now=[1,2,3,4,5,6,7,8,9]

for _ in range(11):
  if x<=len(now):
    print(now[x-1])
    exit()
  else:
    x-=len(now)
    next=now
    now=[]
    for i in next:
      i=str(i)
      if i[-1]=='0':
        j=i+'0'
        k=i+'1'
        now+=[j]
        now+=[k]
      elif i[-1]=='9':
        j=i+'8'
        k=i+'9'
        now+=[j]
        now+=[k]
      else:
        j=i+str(int(i[-1])-1)
        k=i+str(int(i[-1]))
        l=i+str(int(i[-1])+1)
        now+=[j]
        now+=[k]
        now+=[l]

Submission status: Accepted

Solution code:
from queue import deque

k=int(input())
que=deque()
for i in range(1,10):
  que.append(i)
for i in range(k):
  now=que.popleft()
  too=now%10

  if too!=0:
    que.append(now*10+too-1)

  que.append(now*10+too)

  if too!=9:
    que.append(now*10+too+1)

print(now)

Submission status: Accepted

Solution code:
k=int(input())
que=[i for i in range(1,10)]
# print(que)
for i in range(k):
  now=que.pop(0)
  too=now%10

  if too!=0:
    que.append(now*10+too-1)

  que.append(now*10+too)

  if too!=9:
    que.append(now*10+too+1)

print(now)

Submission status: Accepted

Solution code:
k = int(input())

def make_lunlun(lunlun_lst):
    ret_lunlun = []
    for num in lunlun_lst:
        num_str = str(num)
        if num_str[-1] != "0":
            num_tmp = num_str + str(int(num_str[-1]) - 1)
            ret_lunlun.append(int(num_tmp))
        if num_str[-1] != "9":
            num_tmp = num_str + str(int(num_str[-1]) + 1)
            ret_lunlun.append(int(num_tmp))
        num_tmp = num_str + num_str[-1]
        ret_lunlun.append(int(num_tmp))
    return ret_lunlun

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

while 1:
    if len(lunlun_lst) < k:
        k -= len(lunlun_lst)
        lunlun_lst = make_lunlun(lunlun_lst)
    else:
        lunlun_lst.sort()
        print(lunlun_lst[k - 1])
        break

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
K = I()
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
queue = deque(A)
cnt = 0
while cnt != (K - 1):
    x = queue.popleft()
    mod = x % 10
    if mod != 0:
        queue.append(10 * x + mod - 1)
    queue.append(10 * x + mod)
    if mod != 9:
        queue.append(10 * x + mod + 1)
    cnt += 1
print(queue.popleft())

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


K = I()

B = []

#(i, j): iから始まるj桁のルンルン数の個数
lun = {(0, 1): 1, (1, 1): 1, (2, 1): 1, (3, 1): 1, (4, 1): 1, (5, 1): 1, (6, 1): 1, (7, 1): 1, (8, 1): 1, (9, 1): 1}
for j in range(2, 11):
    for i in range(10):
        if i == 0:
            lun[(i, j)] = lun[(i, j - 1)] + lun[(i + 1, j - 1)]
        elif i == 9 :
            lun[(i, j)] = lun[(i - 1, j - 1)] + lun[(i, j - 1)]
        else:
            lun[(i, j)] = lun[(i - 1, j - 1)] + lun[(i, j - 1)] + lun[(i + 1, j - 1)]

cnt = 0
for j in range(1, 10):
    for i in range(1, 10):
        cnt += lun[(i, j)]
    B.append(cnt)

b = bisect.bisect_right(B, K)

ans = []
if b == 0:
    print(K)
    exit()
if K == B[b - 1]:
    print(pow(10, b) - 1)
    exit()
else:
    K -= B[b - 1]
    i = 1
    while K > 0:
        K -= lun[(i, b + 1)]
        i += 1
    if K == 0:
        for j in range(b + 1):
            c = i - 1 + j
            if c <= 9:
                ans.append(c)
            else:
                ans.append(9)
    else:
        K += lun[(i - 1, b + 1)]
        ans.append(i - 1)
        for l in range(b):
            if ans[-1] == 0:
                k = 0
            else:
                k = ans[-1] - 1
            while K > 0:
                K -= lun[(k, b - l)]
                k += 1
            if K == 0:
                for j in range(b - l):
                    c = k - 1 + j
                    if c <= 9:
                        ans.append(c)
                    else:
                        ans.append(9)
                break
            else:
                K += lun[(k - 1, b - l)]
                ans.append(k - 1)
print(''.join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import deque

k=int(input())

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

Submission status: Accepted

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

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


while len(l) < k:
    seq = que.popleft()

    a = int(seq[-1])
    if a != 0:
        aa = seq + str(a-1)
        que.append(aa)
        l.append(aa)
    aa = seq + str(a)
    que.append(aa)
    l.append(aa)
    if a != 9:
        aa = seq + str(a+1)
        que.append(aa)
        l.append(aa)

print(l[k-1])

Submission status: Accepted

Solution code:
k=int(input())
L=[]
def f(d,now,L):
  L.append(now)
  
  if d==10:
    return
  
  for j in range(-1,2):
    v=now%10+j
    if 0<=v<=9:
      f(d+1,now*10+v,L)

for l in range(1,10):
  f(1,l,L)
L.sort()
print(L[k-1])

Submission status: Accepted

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    K=ii()
    L=list(range(10))

    if K <= 9:
        print(K)
        exit()
    
    # print(L)
    head_i = 1
    while len(L) < K+10:
        assert head_i < len(L)
        head = L[head_i]
        head_tail = head % 10
        for x in [head_tail-1,head_tail,head_tail+1]:
            if x < 0 or x >= 10: continue
            
            # print(head_i,head,head_tail)
            # assert not head * 10 + x in L
            L.append(head * 10 + x)
        
        head_i += 1

    # print(L)
    print(L[K])

    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()

    que = cl.deque(list(range(1, 10)))

    while N > 1:
        target = que.popleft()
        if target % 10 != 0:
            que.append(target*10 + (target % 10) - 1)

        que.append(target*10 + (target % 10))

        if target % 10 != 9:
            que.append(target*10 + (target % 10) + 1)
        N -= 1

    ans = que.popleft()

    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

for _ in range(N-1):
  i = q.popleft()
  if i % 10 == 0:
    q.append(i*10)
    q.append(i*10+1)
  elif i % 10 == 9:
    q.append(i*10+8)
    q.append(i*10+9)
  else:
    q.append(i*10+i%10-1)
    q.append(i*10+i%10)
    q.append(i*10+i%10+1)
    
print(q[0])

Submission status: Accepted

Solution code:
a=[str(i) for i in range(1,10)]
i=0
while len(a)<100000:
    if a[i][-1]!="0":
        a.append(a[i]+str(int(a[i][-1])-1))
    a.append(a[i]+str(int(a[i][-1])))
    if a[i][-1]!="9":
        a.append(a[i]+str(int(a[i][-1])+1))
    i+=1
# print(a[:30])
k=int(input())
print(a[k-1])

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
ans=deque([1,2,3,4,5,6,7,8,9])

for i in range(k):
    p=ans.popleft()
    if i==k-1:
        print(p)
    q=p%10
    if q==0:
        ans.append(10*p+0)
        ans.append(10*p+1)
    elif q==9:
        ans.append(10*p+8)
        ans.append(10*p+9)
    else:
        ans.append(10*p+q-1)
        ans.append(10*p+q)
        ans.append(10*p+q+1)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

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

print(x)

Submission status: Accepted

Solution code:
import itertools

K = int(input())

dp = [[0,1,1,1,1,1,1,1,1,1]]
lunlun_cnt = [9]

i = 1

while True:
    dp.append([0]*10)
    lunlun_cnt_tmp = 0

    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][j] + dp[i-1][j+1]
        elif j == 9:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]
        lunlun_cnt_tmp += dp[i][j]
    
    i += 1

    if lunlun_cnt[-1] + lunlun_cnt_tmp >= K:
        break
    else:
        lunlun_cnt.append(lunlun_cnt[-1] + lunlun_cnt_tmp)

if K <= 9:
    pos = K
    digit = 0
else:
    pos = K - lunlun_cnt[-1]
    digit = len(lunlun_cnt)

cnt = 0
flag = False

keta = [-1,0,1]

for i in range(9):
    for keta_shift in itertools.product(keta, repeat=digit):
        flag2 = False
        r = i+1
        for j in range(digit):
            r += keta_shift[j]
            if r < 0 or r > 9:
                flag2 = True
                break
        
        if flag2:
            continue

        cnt += 1
        if cnt == pos:
            flag = True
            break
    if flag:
        break

res = [i+1]
for i in range(digit):
    res.append(res[-1] + keta_shift[i])

print(''.join(list(map(str,res))))

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
q = deque([])
if K < 10:
    print(K)
    exit()
for i in range(1, 10):
    q.append(i)
counter = 9
while counter < K:
    tmp = q.popleft()
    f = tmp%10
    tmp = tmp * 10
    if f == 0:
        q.append(tmp)
        q.append(tmp+1)
        counter += 2
    elif f == 9:
        q.append(tmp+f-1)
        q.append(tmp+f)
        counter += 2
    else:
        q.append(tmp+f-1)
        q.append(tmp+f)
        q.append(tmp+f+1)
        counter += 3
for i in range(K, counter):
    q.pop()
print(q.pop())

Submission status: Accepted

Solution code:
# !/usr/bin/env python3
# from heapq import *
#
# a = [*range(1, 10)]
# heapify(a)
# i = 0
# k = int(input())
# c = 0
# while True:
#    t = str(heappop(a))
#    i += 1
#    if i == k:
#        break
#    if t[-1] != "0":
#        heappush(a, int(t + str(int(t[-1]) - 1)))
#    heappush(a, int(t + t[-1]))
#    if t[-1] != "9":
#        heappush(a, int(t + str(int(t[-1]) + 1)))
# print(t)

from collections import deque

a = deque(range(1, 10))
for _ in range(int(input())):
    i = a.popleft()
    m = i % 10
    i = 10 * i + m
    if m > 0:
        a.append(i - 1)
    a.append(i)
    if m < 9:
        a.append(i + 1)
print(i // 10)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from heapq import *

a = [*range(1, 10)]
heapify(a)
i = 0
k = int(input())
c = 0
while True:
    t = str(heappop(a))
    i += 1
    if i == k:
        break
    if t[-1] != "0":
        heappush(a, int(t + str(int(t[-1]) - 1)))
    heappush(a, int(t + t[-1]))
    if t[-1] != "9":
        heappush(a, int(t + str(int(t[-1]) + 1)))
print(t)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K = int(input())

from collections import deque
d = deque()
for i in range(1,10):
  d.append(str(i))

for _ in range(K):
  a = d.popleft()
  #print(a)
  if a[-1] != '0':
    d.append(a+str(int(a[-1])-1))
  d.append(a+a[-1])
  if a[-1] != '9':
    d.append(a+str(int(a[-1])+1))

ans = a
print(ans)
#print(*ans,sep=' ')

Submission status: Accepted

Solution code:
k = int(input())
# やっぱり一旦はglobalで書こ
total_ls = []
def dfs(A):
    if int(A) > 3234566667:
        return
    global total_ls
    total_ls.append(int(A))
    last = int(A[-1])
    if last == 0:
        nex = [1,0]
    elif last == 9:
        nex = [8,9]
    else:
        nex = [last-1,last,last+1]
    for n in nex:
        A += str(n)
        dfs(A)
        A = A[:-1]

for i in range(1,10):
    dfs(str(i))
total_ls.sort()
print(total_ls[k-1])

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
count = 0
todo = deque(range(1, 10))
while todo:
    x = todo.popleft()
    count += 1
    if count == K:
        print(x)
        break
    i = x % 10
    if 0 < i:
        todo.append(x * 10 + i - 1)
    todo.append(x * 10 + i)
    if i < 9:
        todo.append(x * 10 + i + 1)

Submission status: Accepted

Solution code:
N = int(input()) + 1
Ans = []
def dfs(depth, p):
    if depth==0:
        Ans.append(p)
        if len(Ans) == N:
            print(p)
            exit()
        return
    if p!=0:
        for digit in range(max(0, p%10-1), min(10, p%10+2)):
            dfs(depth-1, p*10+digit)
    else:
        for digit in range(10):
            dfs(depth-1, p*10+digit)
dfs(10, 0)

Submission status: Accepted

Solution code:
X = []
def dfs(k, L):
    global cnt
    if k:
        X.append(int("".join(map(str, L))))
    if k == K:
        return
    if k == 0:
        for i in range(1, 10):
            dfs(k + 1, L + [i])
    else:
        l = L[-1]
        for i in range(max(l-1, 0), min(l+2, 10)):
            dfs(k + 1, L + [i])

K = 10
dfs(0, [])
print(sorted(X)[int(input()) - 1])

Submission status: Accepted

Solution code:
def main():
    from queue import deque

    K = int(input())
    q = deque()
    for i in range(1, 10):
        q.append(i)
    for i in range(K - 1):
        s = q.popleft()
        for j in range(-1, 2):
            add = (s % 10) + j
            if add >= 0 and add <= 9:
                q.append(s * 10 + add)
    print(q.popleft())


main()

Submission status: Accepted

Solution code:
def main():
    from queue import deque

    K = int(input())
    q = deque()
    for i in range(1, 10):
        q.append(i)
    for i in range(K - 1):
        s = q.popleft()
        for j in range(-1, 2):
            add = (s % 10) + j
            if add >= 0 and add <= 9:
                q.append(s * 10 + add)
    print(q[0])


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    def rec(d: int, val: int, all: list):
        all.append(val)
        if d == 10:
            return
        for j in range(-1, 2):
            add = (val % 10) + j
            if add >= 0 and add <= 9:
                rec(d + 1, val * 10 + add, all)
    
    K = int(input())

    all = []
    for v in range(1, 10):
        rec(1, v, all)
    print(sorted(all)[K - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
q = deque(list(range(1,10)))

for i in range(k):
    x = q.popleft()
    if x%10:
        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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
k = I()
d = deque([1,2,3,4,5,6,7,8,9])
for i in range(k):
    num = d.popleft()
    if num%10 != 0:
        d.append(10*num + (num%10) -1)
    d.append(10*num + (num%10))
    if num%10 != 9:
        d.append(10*num + (num%10) + 1)
print(num)

Submission status: Accepted

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

queue = deque()


def main():
    k = int(input())
    queue.extend([1, 2, 3, 4, 5, 6, 7, 8, 9])

    for i in range(k-1):
        x = queue[0]
        queue.popleft()
        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(queue[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
    from collections import deque
    K = int(input())
    q = deque([])
    cnt = 1
    while cnt <= K:
        if cnt < 10:
            q.append(cnt)
            cnt += 1
        else:
            base = q.popleft()
            last_digit = base % 10
            for diff in [-1, 0, 1]:
                if cnt > K:
                    continue
                new_last_digit = last_digit + diff
                if 0 <= new_last_digit <= 9:
                    new_lunlun = base*10 + new_last_digit
                    q.append(new_lunlun)
                    cnt += 1
    print(q[-1])

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
k = int(input()) 
ls = [[] for _ in range(10**4)] 
i = 0
ls[0] = [e for e in range(1,10)]
di = [0]*(10**4)
di[0] = 9
if k <= 9:
    print(k)
    sys.exit()
while True:
    for j in ls[i]:
        p = str(j)[-1]
        q = int(p)
        if p == "0":
            ls[i+1].append(10*j)
            ls[i+1].append(10*j+1)
        elif p == "9":
            ls[i+1].append(10*j+8)
            ls[i+1].append(10*j+9)
        else:
            ls[i+1].append(10*j+q-1)
            ls[i+1].append(10*j+q)
            ls[i+1].append(10*j+q+1)
    di[i+1] = di[i] + len(ls[i+1])
    if di[i+1] >= k:
        print(ls[i+1][k-di[i]-1])
        break
    i += 1

Submission status: Accepted

Solution code:
k = int(input())
from collections import deque
queue = deque([i+1 for i in range(9)])
anses = [i+1 for i in range(9)]
while len(anses) < k:
    now = deque.popleft(queue)
    last = now%10
    if last == 0:
        look = [0, 1]
    elif last == 9:
        look = [8, 9]
    else:
        look = [last-1, last, last+1]
    for i in look:
        anses.append((10*now) + i)
        queue.append((10*now) + i)
print(anses[k-1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

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

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

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

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

if k < 10:
    print(k)
    
else:
    while True:
        x = num.popleft()
        if x % 10 != 0:
            num.append(10*x +(x % 10)-1)
            num0.append(10*x +(x % 10)-1)
            if len(num0) == k:
                break
        num.append(10*x +(x % 10))
        num0.append(10*x +(x % 10))
        if len(num0) == k:
            break
        if x % 10 != 9:
            num.append(10*x +(x % 10)+1)
            num0.append(10*x +(x % 10)+1)
            if len(num0)==k:
                break
    print(num0[-1])

Submission status: Accepted

Solution code:

#1,2,3,4,5,6,7,8,9
#10,11,12,21,22,23,32,33,34,43,44,45,54,55,56,....,98,99
#100,101,110,111,112,121,122,123
#210,211,212,221,222,223,232,233,234
#321,322,323,332,333,334,343,344,345
#1000,1001,1010,1011,1012,

from collections import deque

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

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

    for _ in range(K):
        n=lnln.popleft()
        if n%10!=0:
            lnln.append(n*10+(n%10)-1)
        lnln.append(n*10+(n%10))
        if n%10!=9:
            lnln.append(n*10+(n%10)+1)

    print(n)

if __name__=="__main__":
    main()

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-1):
    num = d.popleft()
    mod = num % 10
    if mod != 0:
        d.append(num*10+mod-1)
    d.append(num*10+mod)
    if mod != 9:
        d.append(num*10+mod+1)
print(d.popleft())

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

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

for idx in range(k):
    ret = deq.popleft()
    # retの右に1つ付け加えてできるルンルン数を追加
    residue = ret % 10
    if residue != 0:
        deq.append(ret * 10 + residue - 1)
    
    deq.append(ret * 10 + residue)

    if residue != 9:
        deq.append(ret * 10 + residue + 1)

print(ret)

Submission status: Accepted

Solution code:
k = int(input())

neighbors = {'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']}
queue = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
count = 0
#print(neighbors)
while True:
  num = queue.pop(0)
  count += 1
  if count == k:
    print(int(num))
    break
  else:
    num_last = num[-1]
    lst = neighbors[num_last]
    for ele in lst:
      num_add = num + ele
      queue.append(num_add)

Submission status: Accepted

Solution code:
K = int(input())
import sys
from queue import Queue
queue = Queue()
for i in range(1,10):
  queue.put(i)
if K <= 9:
  print(K)
  sys.exit()
count = 0
while True:
  j = queue.get()
  count += 1
  if count == K:
    print(j)
    break
  if j % 10 != 0:
    queue.put(10*j+(j%10)-1)
  queue.put(10*j+(j%10))
  if j % 10 != 9:
    queue.put(10*j+(j%10)+1)

Submission status: Accepted

Solution code:
k = int(input())

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

if k<10:
    print(num[k-1])
    exit()

ans=9

def hantei():
    global ans
    ans+=1
    if ans==k:
        print(num[-1])
        exit()

for i in range(10**10):

    hitoketa=num[0]%10

    if hitoketa==0:
        num.append(10*num[0]+0)
        hantei()
        num.append(10*num[0]+1)
        hantei()
        num.pop(0)

    elif hitoketa==9:
        num.append(10*num[0]+8)
        hantei()
        num.append(10*num[0]+9)
        hantei()
        num.pop(0)

    else:
        num.append(10*num[0]+(hitoketa-1))
        hantei()
        num.append(10*num[0]+(hitoketa))
        hantei()
        num.append(10*num[0]+(hitoketa+1))
        hantei()
        num.pop(0)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
q = deque()

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

k = 0
while True:
	n = q.popleft()
	k += 1
	if k == K:
		break
	if (n % 10) % 10 != 0:
		q.append(10 * n + (n % 10) - 1)
	q.append(n * 10 + (n % 10))
	if (n % 10) % 10 != 9:
		q.append(10 * n + (n % 10) + 1)
print(n)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import ceil, log
def main():
    k = int(input())
    k2 = int(log(ceil(k / 10), 3)) + 1
    def getlun(n, keta, last):
        lunluns.append(n)
        if keta > k2:
            pass
        else:
            l1 = n * 10 + last
            getlun(l1, keta + 1, last)
            if last > 0:
                l2 = n * 10 + last - 1
                getlun(l2, keta + 1, last - 1)
            if last < 9:
                l3 = n * 10 + last + 1
                getlun(l3, keta + 1, last + 1)
    lunluns = []
    for i1 in range(1, 10):
        getlun(i1, 0, i1)
    lunluns.sort()
    print(lunluns[k-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from collections import deque

K = int(input())
q = deque(list(range(1, 10)))
for _ in range(K - 1):
    u = q.popleft()
    n = u % 10
    for x in range(max(0, n - 1), min(9, n + 1) + 1):
        q.append(u * 10 + x)

print(q.popleft())

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):
  x = q.popleft()
  y = 10 * x + x % 10
  if x % 10:
    q.append(y - 1)
  q.append(y)
  if x % 10 != 9:
    q.append(y + 1)

print(x)

Submission status: Accepted

Solution code:
k=int(input())
a=[]
for i in range(1,10):
    a.append(i)
s=0
t=8
for i in range(1,10):
    for j in range(s,t+1):
        if str(a[j])[len(str(a[j]))-1]=="0":
            a.append(str(a[j])+"0")
            a.append(str(a[j])+"1")
        elif str(a[j])[len(str(a[j]))-1]=="9":
            a.append(str(a[j])+"8")
            a.append(str(a[j])+"9")
        else:
            c=int(str(a[j])[len(str(a[j]))-1])-1
            d=int(str(a[j])[len(str(a[j]))-1])
            e=int(str(a[j])[len(str(a[j]))-1])+1
            a.append(str(a[j])+str(c))
            a.append(str(a[j])+str(d))
            a.append(str(a[j])+str(e))
    s=t+1
    t=len(a)-1
print(a[k-1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

count = 1
d= deque([1,2,3,4,5,6,7,8,9])
#ls = []
while count <= k:
    v = d.popleft()
    count += 1
    last = str(v)[-1]
    if last == '0':
        d.append(int(str(v) + '0'))
        d.append(int(str(v)+'1'))
    elif last == '9':
        d.append(int(str(v) + '8'))
        d.append(int(str(v) + '9'))
    else:
        d.append(int(str(v) + str(int(last) - 1)))
        d.append(int(str(v) + str(int(last) )))
        d.append(int(str(v) + str(int(last) + 1)))
    #ls.append(v)

#print(ls)
print(v)

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())


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

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

cnt = 9
while cnt < k:
    x = q.popleft()
    if x % 10 == 0:
        nx = 10 * x
        q.append(nx)
        lun.append(nx)
        nx = 10 * x + 1
        q.append(nx)
        lun.append(nx)
        cnt += 2
    elif x % 10 == 9:
        nx = 10 * x + 8
        q.append(nx)
        lun.append(nx)
        nx = 10 * x + 9
        q.append(nx)
        lun.append(nx)
        cnt += 2
    else:
        m = x % 10
        nx = 10 * x + m - 1
        q.append(nx)
        lun.append(nx)
        nx = 10 * x + m
        q.append(nx)
        lun.append(nx)
        nx = 10 * x + m + 1
        q.append(nx)
        lun.append(nx)
        cnt += 3
lun.sort()
print(lun[k-1])

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
l = deque([i for i in range(1, 10)])
# print(l)

for i in range(k):
    x = l.popleft()
    mod = x % 10
    if mod != 0:
        l.append(x*10 + mod - 1)
    l.append(x*10 + mod)
    if mod != 9:
        l.append(x*10 + mod + 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):
  num = q.popleft()
  if num%10 != 0:
    q.append(num*10+num%10-1)
  q.append(num*10+num%10)
  if num%10 != 9:
    q.append(num*10+num%10+1)

print(num)