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 unittest
import collections


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(15), 23)

    def test_2(self):
        self.assertEqual(think(1), 1)

    def test_3(self):
        self.assertEqual(think(13), 21)

    def test_4(self):
        self.assertEqual(think(100000), 3234566667)


def solve():
    k = read()
    result = think(k)
    write(result)


def read():
    return read_int(1)[0]


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(k):
    k_max = 10 ** 5
    list_of_lunlun_number = prepare_lunlun_number(k_max)
    return list_of_lunlun_number[k - 1]


def write(result):
    print(result)


def prepare_lunlun_number(k_max):
    lunlun_number = collections.deque([])
    deque = collections.deque(list(range(1, 10)))
    length = 0
    while length < k_max:
        d = deque.popleft()
        lunlun_number.append(d)
        length += 1
        if d % 10 == 0:
            deque.append(d * 10 + 0)
            deque.append(d * 10 + 1)
        elif d % 10 == 9:
            deque.append(d * 10 + 8)
            deque.append(d * 10 + 9)
        else:
            m = d % 10
            deque.append(d * 10 + m - 1)
            deque.append(d * 10 + m)
            deque.append(d * 10 + m + 1)
    return lunlun_number


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def generate_lunlun(p):
    last = p % 10
    if last - 1 >= 0:
        yield p * 10 + last - 1
    yield p * 10 + last
    if last + 1 <= 9:
        yield p * 10 + last + 1

if __name__ == '__main__':
    k = int(input())
    lunlun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    p = 0

    while len(lunlun) < k:
        for new_lunlun in generate_lunlun(lunlun[p]):
            lunlun.append(new_lunlun)
        p += 1

    print(lunlun[k-1])

Submission status: Accepted

Solution code:
from queue import Queue

k = int(input())

#  print(k)

q = Queue()

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

ans = 0
for j in range(k):
  ans = q.get()
  f = ans % 10
  n = ans * 10 + f
  
  if f != 0:
    q.put(n-1)
  
  q.put(n)
  
  if f != 9:
    q.put(n+1)
print(ans)

Submission status: Accepted

Solution code:
#python3
from collections import deque

def main():

    k = int(input())
    cand = []
    for i in range(1, 10):
        cand.append(i)

    cnt = 0
    dq = deque()
    for i in range(1, 10):
        dq.append(i)

    while len(dq):
        v = dq.popleft()
        x = v%10 
        cnt += 1
        if x == 0:
            for j in (0, 1):
                nx = v*10 + j
                cand.append(nx)
                dq.append(nx)
        elif x == 9:
            for j in (-1, 0):
                nx = v*10 + 9 + j
                cand.append(nx) 
                dq.append(nx)
        else:
            for j in (-1, 0, 1):
                nx = v*10 + x + j
                cand.append(nx)
                dq.append(nx)
        if len(cand) > 2*k:
            break    

    print(cand[k-1])
main()

Submission status: Accepted

Solution code:
import heapq
import sys

a=[1,2,3,4,5,6,7,8,9]
heapq.heapify(a)

k = int(input())

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

ans = 9

while True:
  x = heapq.heappop(a)
  # print(a)
  if x%10 ==0:
    for i in [0,1]:
      y = x*10 + i
      ans += 1
      if ans == k:
        print(y)
        sys.exit()
      heapq.heappush(a,y)
  elif x%10 == 9:
    for i in [-1,0]:
      y = x*10 + x%10 + i
      ans += 1
      if ans == k:
        print(y)
        sys.exit()
      heapq.heappush(a,y)
  else:
    for i in [-1,0,1]:
      # print(i)
      y = x*10 + x%10 + i
      ans += 1
      if ans == k:
        print(y)
        sys.exit()
      heapq.heappush(a,y)

Submission status: Accepted

Solution code:
K=int(input())
import queue
a=queue.Queue()
if K<=9:
  print(K)
else:
  for i in range(1,10):
    a.put(i)
  n=K
  while n>1:
    p=a.get()
    x=p%10
    if x%10!=0:
      a.put(10*p+x-1)
    a.put(10*p+x)
    if x%10!=9:
      a.put(10*p+x+1)
    n-=1
  ans=a.get()
  print(ans)

Submission status: Accepted

Solution code:
#python3
from collections import deque

def main():

    k = int(input())
    cand = []
    for i in range(1, 10):
        cand.append(i)

    cnt = 0
    dq = deque()
    for i in range(1, 10):
        dq.append(i)

    while len(dq):
        v = dq.popleft()
        x = v%10 
        cnt += 1
        if x == 0:
            for j in (0, 1):
                nx = v*10 + j
                cand.append(nx)
                dq.append(nx)
        elif x == 9:
            for j in (-1, 0):
                nx = v*10 + 9 + j
                cand.append(nx) 
                dq.append(nx)
        else:
            for j in (-1, 0, 1):
                nx = v*10 + x + j
                cand.append(nx)
                dq.append(nx)
        if len(cand) > 2*k:
            break    

    cand.sort()
    print(cand[k-1])
main()

Submission status: Accepted

Solution code:
from collections import deque

n= int(input())

if n < 10:
    print(n);exit()

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

for _ in range(1,n):

    t = q.popleft()

    # tt = t%10
    tt = int(str(t)[-1])

    for j in range(-1,2):
        ttt = tt+j
        if ttt >= 0 and ttt <= 9:
            # q.append(t * 10 + ttt)
            q.append(int(str(t) + str(ttt)))

print(q.popleft())

Submission status: Accepted

Solution code:
from collections import deque

n= int(input())

if n < 10:
    print(n);exit()

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

for _ in range(1,n):

    t = q.popleft()

    tt = t%10

    for j in range(-1,2):
        ttt = tt+j
        if ttt >= 0 and ttt <= 9:
            q.append(t * 10 + ttt)

print(q.popleft())

Submission status: Accepted

Solution code:
k = int(input())
a = 0
import queue
q = queue.Queue()
for i in range(1,10):
  q.put(i)
while True:
  x = q.get()
  a += 1
  if a == k:
    break
  elif x % 10 != 9 and x % 10 != 0:
      q.put(10*x + x%10 - 1)
      q.put(10*x + x%10)
      q.put(10*x + x%10 + 1)
  elif x % 10 == 9:
    q.put(10*x + x%10 - 1)
    q.put(10*x + x%10)
  else:
    q.put(10*x + x%10)
    q.put(10*x + x%10 + 1)
print(x)

Submission status: Accepted

Solution code:
k = int(input())


def dfs(d, val, all):
    all.append(val)
    if d == 10:
        return
    for j in [-1, 0, 1]:
        add = (val) % 10 + j
        if 0 <= add <= 9:
            dfs(d+1, val*10+add, all)


all = []
for v in range(1, 10):
    dfs(1, v, all)
all.sort()
print(all[k-1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

q = deque()

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

for _ in range(k):
    temp = q.popleft()
    if temp % 10 != 0:
        q.append(temp*10+int(str(temp)[-1])-1)
    
    q.append(temp*10+int(str(temp)[-1]))

    if temp % 10 != 9:
        q.append(temp*10+int(str(temp)[-1])+1)

print(temp)

Submission status: Accepted

Solution code:
def main():
    import sys
    
    K = int(sys.stdin.readline())
    
    lunlun_list = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
    
    if K <= 9:
        ans = lunlun_list[0][K - 1]
    else:
        count = 9
        n = 0
        while count < K:
            add_list = []
            for m in lunlun_list[n]:
                if m % 10 == 0:
                    m_1 = m * 10
                    add_list.append(m_1)
                    count += 1
                    if count == K:
                        ans = m_1
                        break
                    m_2 = m * 10 + 1
                    add_list.append(m_2)
                    count += 1
                    if count == K:
                        ans = m_2
                        break
                elif m % 10 == 9:
                    m_1 = m * 10 + 8
                    add_list.append(m_1)
                    count += 1
                    if count == K:
                        ans = m_1
                        break
                    m_2 = m * 10 + 9
                    add_list.append(m_2)
                    count += 1
                    if count == K:
                        ans = m_2
                        break
                else:
                    l = m % 10
                    m_1 = m * 10 + l - 1
                    add_list.append(m_1)
                    count += 1
                    if count == K:
                        ans = m_1
                        break
                    m_2 = m * 10 + l
                    add_list.append(m_2)
                    count += 1
                    if count == K:
                        ans = m_2
                        break
                    m_3 = m * 10 + l + 1
                    add_list.append(m_3)
                    count += 1
                    if count == K:
                        ans = m_3
                        break
            lunlun_list.append(add_list)
            n += 1
            
    print(ans)
                    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import queue

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

    i = 0
    while True:
        i += 1

        n = q.get()
        center_num = (10 * n) + (n % 10)
        
        if n % 10 != 0:
            q.put(center_num - 1)
        
        q.put(center_num)

        if n % 10 != 9:
            q.put(center_num + 1)

        if i >= K:
            # print(q.queue)
            print(n)
            sys.exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue
K = int(input())
q = queue.Queue()
for i in range (1,10):
  q.put(i)
for j in range(K):
  x = q.get()
  r = x % 10
  if r != 0:
    q.put(10 * x + r - 1)
  q.put(10 * x + r)
  if r != 9:
    q.put(10 * x + r + 1)
print(x)

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):
    a = q.get()
    if i==k-1:
        print(a)
        exit()
    c = int(str(a)[-1])
    if c==0:
        q.put(a * 10 + c)
        q.put(a * 10 + c + 1)
    elif c==9:
        q.put(a * 10 + c - 1)
        q.put(a * 10 + c)
    else:
        q.put(a*10+c-1)
        q.put(a*10+c)
        q.put(a*10+c+1)

Submission status: Accepted

Solution code:
k=int(input())
total=0
def count(keta,s,ans):
    global total
    if keta==1:
        total+=1
        if k==total:
            print(ans) #ここで終了させたい
        return 
    for m in range(10):
        if abs(s-m)<=1:
            count(keta-1,m,ans+str(m))
for i in range(1,11):
    for j in range(1,10):
        count(i,j,str(j))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
K=input()

L=[]

def dfs(n,depth):
    L.append(n)
    if depth==9: return
    ichi_no_kurai=n%10
    for i in range(max(0,ichi_no_kurai-1),min(ichi_no_kurai+2,10)):
        next=n*10+i
        dfs(next,depth+1)

for n in range(1,10):
    dfs(n,0)

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

Submission status: Accepted

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

for k 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())

Current = [1, 2, 3, 4, 5, 6, 7, 8, 9]
while 1:
    Next = deque([])
    cnt = len(Current) 
    if K <= cnt:
        #現在の桁の中で考える
        ans = Current[K - 1]
        break
    else:   #K > cnt
        #次の桁を考える
        for i in Current:
            key = i % 10
            for j in [key - 1, key, key + 1]:
                if 0 <= j and j <= 9:
                    Next.append(i * 10 + j)
                else: #j < 0 or 9 < j
                    pass
        K -= cnt
        Current = Next


print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

a = []

def g(x):
    for i in range(-1,2):
        last = (x%10) + i
        if x <= 3234566667 and last != -1 and last != 10:
            f(10*x+last)
def f(x):
    a.append(x)
    g(x)

for i in range(1,10):
    f(i)
a.sort()

def main():
    n = inp()
    print(a[n-1])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Current = [1, 2, 3, 4, 5, 6, 7, 8, 9]
cnt = 9
times = 0
while 1:
    Next = deque([])
    cnt = len(Current) 
    if K <= cnt:
        #現在の桁の中で考える
        ans = Current[K - 1]
        break
    else:   #K > cnt
        #次の桁を考える
        for i in Current:
            key = i % 10
            for j in [key - 1, key, key + 1]:
                if 0 <= j and j <= 9:
                    Next.append(i * 10 + j)
                else: #j < 0 or 9 < j
                    pass
        K -= cnt
        Current = Next


print(ans)

Submission status: Accepted

Solution code:
k = int(input())

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

count = 0

while queue:
    now = queue.popleft()
    count += 1
    if count == k:
        print(now)
        exit()
    now_ = now%10
    if now_ == 0:
        queue.append(10*now+now_)
        queue.append(10*now+now_+1)
    elif now_ == 9:
        queue.append(10*now+now_-1)
        queue.append(10*now+now_)
    else:
        queue.append(10*now+now_-1 )
        queue.append(10*now+now_)
        queue.append(10*now+now_+1)

Submission status: Accepted

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

ans=0
cnt=0

while 1:
    x=q.popleft()
    cnt+=1
    if cnt==k:
        ans=x
        break
    xmod10 = x % 10
    if xmod10 != 0:
        q.append(10*x+(xmod10-1))
    q.append(10*x+(xmod10))
    if xmod10 != 9:
        q.append(10*x+(xmod10+1))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

K = int(input())
t = 0
ans = 0

while t < K:
  t += 1
  ans = q.get()
  p = int(str(ans)[-1])
  for i in range(-1, 2):
    if 0 <= p+i < 10: q.put(int(str(ans) + str(p+i)))

print(ans)

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from queue import Queue


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


def INT(): return int(input())


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


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


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    k = INT()
    q = Queue()
    for i in range(1, k+10):
        # print(q.queue)
        if i < 10:
            q.put(i)
        else:
            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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K = int(input())
import heapq
que = [i for i in range(1,10)]
heapq.heapify(que)
for i in range(K):
    now = heapq.heappop(que)
    if now%10 == 0:
        heapq.heappush(que,10*now)
        heapq.heappush(que,10*now+1)
    elif now%10 == 9:
        heapq.heappush(que,10*now+8)
        heapq.heappush(que,10*now+9)
    else:
        heapq.heappush(que,10*now+(now%10))
        heapq.heappush(que,10*now+(now%10)-1)
        heapq.heappush(que,10*now+(now%10)+1)
print(now)

Submission status: Accepted

Solution code:
import queue

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

    numq = queue.Queue()
    for n in range(1, 9+1):
        numq.put(n)

    ans = None
    for _ in range(K):
        n = numq.get()
        #print('[DEBUG] n: ', n)
        #print('[DEBUG] type(n): ', type(n))
        base = n*10
        if base//10%10 >= 1:
            numq.put(base + (base//10%10-1))
        numq.put(base + (base//10%10))
        if base//10%10 <= 8:
            numq.put(base + (base//10%10+1))
        ans = n

    print(ans)
        

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
l = [9,8,7,6,5,4,3,2,1]
lunlun = deque(l)
ans = l
for _ in range(K - 9):
    x = lunlun.pop()
    tmp = 10 * x + (x % 10)
    if x % 10 != 0:
        lunlun.appendleft(tmp - 1)
        ans.append(tmp - 1)
    lunlun.appendleft(tmp)
    ans.append(tmp)
    if x % 10 != 9:
        lunlun.appendleft(tmp + 1)
        ans.append(tmp + 1)
ans.sort()
print(ans[K - 1])

Submission status: Accepted

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

K = int(read().rstrip())

runrun = [None for _ in range(1, 20)] # 20は十分な値
runrun[1] = (1, 2, 3, 4, 5, 6, 7, 8, 9)

def gen_runrun(keta):
    for x in runrun[keta-1]:
        r = x % 10

        if r > 0:
            yield x * 10 + r - 1
        yield x * 10 + r
        if r < 9: 
            yield x * 10 + r + 1

# 10桁以下のrunrun数の列挙
for keta in range(2, 11):
    runrun[keta] = tuple(gen_runrun(keta))

for keta in range(1, 11):
    if K < len(runrun[keta]):
        answer = runrun[keta][K-1]
        break
    K -= len(runrun[keta])

print(answer)

Submission status: Accepted

Solution code:
K = int(input())

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

def lunlun_generator(now_lunlun):
    last = now_lunlun%10
    if last-1>=0:
        yield 10*now_lunlun+last-1
    yield 10*now_lunlun+last
    if last+1<=9:
        yield 10*now_lunlun+last+1 

while 1:
    for new_lunlun in lunlun_generator(lunlun[p]):
       lunlun.append(new_lunlun)

    p += 1
    if p == K:
        break

print(lunlun[p-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k = int(input())
lunlun = [1,2,3,4,5,6,7,8,9]
i = 0
while len(lunlun) < k:
  p = lunlun[i]
  if str(p)[-1] == '0':
    lunlun.append(p*10)
    lunlun.append(p*10+1)
  elif str(p)[-1] == '9':
    lunlun.append(p*10+8)
    lunlun.append(p*10+9)
  else:
    lunlun.append(p*10+p%10-1)
    lunlun.append(p*10+p%10)
    lunlun.append(p*10+p%10+1)
  i += 1

print(lunlun[k-1])

Submission status: Accepted

Solution code:
import numpy as np
K = int(input())
lunlun_number = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
for _ in range(9):
    tmp = []
    for n in lunlun_number[-1]:
        if n % 10 != 0:  # 末尾が0の場合は-1した数がルンルン数にならないのでそれ以外を採用
            tmp.append(n * 10 + (n % 10 - 1))
        tmp.append(n * 10 + (n % 10))
        if n % 10 != 9:  # 末尾が9のときは+1した数がルンルン数にならないのでそれ以外を採用
            tmp.append(n * 10 + (n % 10 + 1))
    lunlun_number.append(tmp)
lunlun_number = [flatten for inner in lunlun_number for flatten in inner]
print(lunlun_number[K - 1])

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline
from collections import deque

def main():

    K = int(input())

    q = deque([])   # キュー
    for i in range(1,10):
        q.append(i)
    k=0
    while k<K:
        p = q.popleft()     # キュー取りだし（先頭）
        k+=1
        x=p%10
        if x-1>=0:
            q.append(p*10+x-1)
        q.append(p*10+x)
        if x+1<=9:
            q.append(p*10+x+1)
    print(p)

if __name__ == '__main__':
    main()

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):
    q_K = q.get()
    q_K_mod10 = q_K % 10
    if q_K_mod10 != 0:
        q.put(10 * q_K + q_K_mod10 - 1)
    q.put(10 * q_K + q_K_mod10)
    if q_K_mod10 != 9:
        q.put(10 * q_K + q_K_mod10 + 1)

print(q_K)

Submission status: Accepted

Solution code:
K = int(input())

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


def get_lunlun(K):
    for num in queue:
        if len(queue) >= K:
            return queue[K - 1]
        for i in range(-1, 2):
            last = num % 10 + i
            if last < 0 or last > 9:
                continue
            queue.append(num * 10 + last)


print(get_lunlun(K))

Submission status: Accepted

Solution code:
k = int(input())
ans = []


def dfs(x):
    if x > 3234566667:
        return 0
    else:
        ans.append(x)
        y = x % 10
        for i in range(10):
            if abs(y-i) <= 1:
                dfs(10*x+i)
    

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

Submission status: Accepted

Solution code:
import sys

MAX = 1000000
Q = [0] * MAX
head = 0
tail = 0

def isEmpty():
    return head == tail

def isFull():
    return head == (tail + 1) % MAX

def enqueue(x):
    global tail
    if isFull():
        print("オーバーフロー")
        sys.exit()
    Q[tail] = x
    if tail + 1 == MAX:
        tail = 0
    else:
        tail += 1

def dequeue():
    global head
    if isEmpty():
        print("アンダーフロー")
        sys.exit()
    x = Q[head]
    if head + 1 == MAX:
        head = 0
    else:
        head += 1
    return x

k = int(input())

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

for i in range(k):
    x = dequeue()
    b = x % 10
    if b != 0:
        enqueue(10 * x + b - 1)
    enqueue(10 * x + b)
    if b != 9:
        enqueue(10 * x + b + 1)
print(x)

Submission status: Accepted

Solution code:
k = int(input())
ans = []


def dfs(x):
    if x > 10**10:
        return 0
    else:
        ans.append(x)
        y = x % 10
        for i in range(10):
            if abs(y-i) <= 1:
                dfs(10*x+i)
                
for i in range(1, 10):
    dfs(i)
ans.sort()
print(ans[k-1])

Submission status: Accepted

Solution code:
K = int(input())
a = list(range(1,10))
for i in a:
  if len(a) > K:
    break
  x = i % 10
  for j in range(max(0, x - 1), min(x + 2, 10)):
    a.append(i * 10 + j)
print(a[K - 1])

Submission status: Accepted

Solution code:
import queue

k = int(input())
q = queue.Queue()
x = -1
for i in range(1,10):
    q.put(i)
for i in range(1,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(x)

Submission status: Accepted

Solution code:
k = int(input())
ans = [i for i in range(1,10)]

i = 0

for i in range(k):
    now = ans[i]
    if str(now)[-1] == '0':
        ans.append(now*10)
        ans.append(now*10+1)
    elif str(now)[-1] == '9':
        ans.append(now*10+8)
        ans.append(now*10+9)
    else:
        ans.append(now*10+now%10-1)
        ans.append(now*10+now%10)
        ans.append(now*10+now%10+1)
    if len(ans) > k:
        break

print(ans[k-1])

Submission status: Accepted

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

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

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



q = deque()
for i in range(len(lunlun)):
    for j in lunlun[i]:
        q.append(j)
        
print(q[k-1])

Submission status: Accepted

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

count=0
while True:
    count += 1
    check = d.popleft()
    mod = check % 10
    if check % 10 == 0:
        d.append(check*10)
        d.append(check*10+1)
    elif check % 10 == 9:
        d.append(check*10+8)
        d.append(check*10+9)
    else:
        d.append(check*10+mod-1)
        d.append(check*10+mod)
        d.append(check*10+mod+1)
    if count == K:
        break
print(check)

Submission status: Accepted

Solution code:
import sys

def main(n):
    ans = []
    ans.append(list(range(1,10)))
    count = len(ans[0])

    if n < 10:
        return n

    while True:
        ans.append([])
        for i in ans[-2]:
            if int(str(i)[-1]) != 0:
                ans[-1].append(int(str(i) + str(int(str(i)[-1])-1)))
                count += 1
                if count == n:
                    return ans[-1][-1]
            ans[-1].append(int(str(i) + str(i)[-1]))
            count += 1
            if count == n:
                return ans[-1][-1]
            if int(str(i)[-1]) != 9:
                ans[-1].append(int(str(i) + str(int(str(i)[-1])+1)))
                count += 1
                if count == n:
                    return ans[-1][-1]

K = int(input())
print(main(K))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc161/submissions/11510702

k = int(input())
ans = [i for i in range(1,10)]
#1,2,3,4,5,6,7,8,9
i = 0

#全探索
#みぎにずらした時に1の位にくる数字ごとに分岐
for i in range(k):
    now = ans[i]
    if str(now)[-1] == '0':
        ans.append(now*10)
        ans.append(now*10+1)
    elif str(now)[-1] == '9':
        ans.append(now*10+8)
        ans.append(now*10+9)
    else:
        ans.append(now*10+now%10-1)
        ans.append(now*10+now%10)
        ans.append(now*10+now%10+1)
    if len(ans) > k:
        break

print(ans[k-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

deq = deque(range(9, 0, -1))
enqueue = deq.appendleft
dequeue = deq.pop

for _ in range(K):
	x = dequeue()
	y = x % 10
	if y != 0:
		enqueue(x * 10 + y - 1)
	enqueue(x * 10 + y)
	if y != 9:
		enqueue(x * 10 + y + 1)
print(x)

Submission status: Accepted

Solution code:
def gen_lunlun(stop, base=[1, 2, 3, 4, 5, 6, 7, 8, 9]):
    if stop <= 0:
        return base
    
    new_lunlun = []
    for x in base:
        lank1 = x%10
        b = x*10+lank1
        if lank1 == 0:
            tmp = [b, b+1]
        elif lank1 == 9:
            tmp = [b-1, b]
        else:
            tmp = [b-1, b, b+1]
        new_lunlun.extend(tmp)
        if len(new_lunlun) >= stop:
            break
    base.extend(gen_lunlun(stop-len(new_lunlun), new_lunlun))
    return base

k = int(input())
print(gen_lunlun(k-9)[k-1])

Submission status: Accepted

Solution code:
import heapq
lunlun = [i for i in range(1, 10)]
heapq.heapify(lunlun)
K = int(input())
ans = 0

while K > 0:
    ans = heapq.heappop(lunlun)
    K -= 1
    last_digit = int(str(ans)[-1])
    up, down = last_digit + 1, last_digit - 1
    heapq.heappush(lunlun, ans * 10 + last_digit)
    if up < 10:
        heapq.heappush(lunlun, ans * 10 + up)
    if down >= 0:
        heapq.heappush(lunlun, ans * 10 + down)

print(ans)

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

Submission status: Accepted

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

k = ni()

luns = []


def make_lunlun(l):
    if l > 3234566667:
        return
    luns.append(l)

    last = l-l//10*10

    if last!=0:
        make_lunlun(l*10 + last-1)
    make_lunlun(l*10+last)
    if last!=9:
        make_lunlun(l*10 + last+1)


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

print(sorted(luns)[k-1])

Submission status: Accepted

Solution code:

k = int(input())
q = []

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

while True:
    if k <= len(q):
        print(q[k-1])
        break
    k = k - len(q)
    old_q = q[:]
    q = []

    for x in old_q:
        for i in range(-1, 2):
            d = x%10 + i
            if d < 0 or d > 9:
                continue
            nx = x*10 + d
            q.append(nx)

Submission status: Accepted

Solution code:
k = int(input())

a = list(range(1, 10))

while(1):
    if k <= len(a):
        print(a[k-1])
        exit()
    k -= len(a)
    old = []
    old, a = a, old
    for x in old:
        for i in [-1, 0, 1]:
            d = x%10 + i
            if d<0 or d>9: continue
            nx = x*10 + d
            a.append(nx)

Submission status: Accepted

Solution code:
k = int(input())
lunList = [i for i in range(1, 10)]
for i in range(k-9):
    x = lunList[i]
    for j in range(-1, 2):
        d = x%10 + j
        if 0 <= d <= 9:
            lunList.append(10*x + d)
print(lunList[k-1])