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:
from collections import deque


def main():
    k = int(input())
    if k <= 9:
        print(k)
    else:
        queue = deque()
        for i in range(1, 10):
            queue.append(i)
        flag = 1
        cnt_lunlun = 9
        while flag:
            first_element = queue.popleft()
            lunlun_nums = extend_lunlun(first_element)
            for n in lunlun_nums:
                queue.append(n)
                cnt_lunlun += 1
                if cnt_lunlun == k:
                    flag -= 1
                    break
        print(queue.pop())


def extend_lunlun(num):
    lunlun_nums = []
    last_digit = num % 10
    for i in range(-1, 2):
        d = last_digit + i
        if d >= 0 and d <= 9:
            lunlun_nums.append(num*10+d)
    return lunlun_nums


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


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

    while k > 0:
        k -= 1
        n = q.popleft()
        # print('====== popleft:', n)

        if n % 10 != 0:
            n0 = int(str(n) + str(n % 10 - 1))
            q.append(n0)
            # print('=== append:', n0)

        n1 = int(str(n) + str(n % 10))
        q.append(n1)
        # print('=== append:', n1)

        if n % 10 != 9:
            n2 = int(str(n) + str(n % 10 + 1))
            q.append(n2)
            # print('=== append:', n2)

    print(n)


##########
if __name__ == "__main__":
    lunlun()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    k = int(input())
    if k <= 9:
        print(k)
    else:
        queue = deque()
        for i in range(1, 10):
            queue.append(i)
        flag = 1
        cnt_lunlun = 9
        while flag:
            first_element = queue.popleft()
            lunlun_nums = extend_lunlun(first_element)
            for n in lunlun_nums:
                queue.append(n)
                cnt_lunlun += 1
                if cnt_lunlun == k:
                    flag -= 1
                    break
        print(queue.pop())


def extend_lunlun(num):
    last_digit = int(str(num)[-1])
    if last_digit == 0:
        return int(str(num)+"0"), int(str(num)+"1")
    elif last_digit == 9:
        return int(str(num) + "8"), int(str(num) + "9")
    else:
        return (
            int(str(num) + str(last_digit - 1)),
            int(str(num) + str(last_digit)),
            int(str(num) + str(last_digit + 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:
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])
l=len(ans[-1])
v=sorted([int(i) for i in ans[-1]])

print(v[k-(d-l)-1])

Submission status: Accepted

Solution code:
k = int(input())

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

while k:
    if k <= len(A):
        print(A[k-1])
        exit()

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

Submission status: Accepted

Solution code:
import queue

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

    count = 0
    q = queue.Queue()
    for i in range(1,10):
        count += 1
        q.put(i)
        if count == K:
            print(i)
            break

    result = 0
    while count != K:
        tmp = q.get()
        keta1 = tmp % 10
        for i in  range(-1,2):
            if i == -1 and keta1 == 0:
                continue
            if i == 1 and keta1 == 9:
                continue
            result = tmp*10 + (keta1+i)
            q.put(result)
            count += 1
            if count == K:
                print(result)
                break
        else:
            continue
        break

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])
        if z==0:
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        elif 1<=z<=8:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        else:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
    d+=len(ans[-1])
l=len(ans[-1])
v=sorted([int(i) for i in ans[-1]])

print(v[k-(d-l)-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

lunlun = []

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

while len(lunlun) <= K:
    # print(q)
    old = q.popleft()
    lunlun.append(old)
    last = old % 10
    if last - 1 >= 0:
        q.append(old * 10 + last - 1)
    q.append(old * 10 + last)
    if last + 1 <= 9:
        q.append(old * 10 + last + 1)

# print(lunlun)
print(lunlun[K - 1])

Submission status: Accepted

Solution code:
from collections import deque

def dfs(q, keta):
    global K
    
    if len(q)==keta:
        K -= 1
        
        if K==0:
            q = list(map(str, q))
            print(''.join(q))
            exit()
        
        return
    
    for nex in range(max(0, q[-1]-1), min(9, q[-1]+1)+1):
        q.append(nex)
        dfs(q, keta)
        q.pop()

K = int(input())

for i in range(1, 100):
    for j in range(1, 10):
        q = deque([j])
        dfs(q, i)

Submission status: Accepted

Solution code:
#coding:utf-8

def up(nums):
    if len(nums) == nums.count(9):
        nums = [1] + [0] * len(nums)
        return nums
    
    for i in list(reversed(range(len(nums)))):
        if nums[i] > nums[i-1] or nums[i] == 9:
            continue
        else:
            nums[i] += 1
            for j in range(i+1, len(nums)):
                nums[j] = max(nums[j-1]-1, 0)
            return nums
          
  
def main():
    k = int(input())
    nums = [0]
    for _ in range(k):
        nums = up(nums)
        
    print(''.join([str(num) for num in nums]))
        
    
        
  
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
lunlun = [[1,2,3,4,5,6,7,8,9]]
 
for _ in range(10):
    tmp = []
    for i in lunlun[-1]:
        if i % 10 == 0 :
            tmp.append(10 * i + i % 10)
            tmp.append(10 * i + i % 10 + 1)
        elif i % 10 == 9:
            tmp.append(10 * i + i % 10 - 1)
            tmp.append(10 * i + i % 10)
        else:
            tmp.append(10 * i + i % 10 - 1)
            tmp.append(10 * i + i % 10)
            tmp.append(10 * i + i % 10 + 1)
    lunlun.append(tmp)
ans = []
for i in lunlun:
    for j in i:
        ans.append(j)
print(ans[n-1])

Submission status: Accepted

Solution code:
K = int(input())

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

p = 0


def genelate_lunlun(p):
    last = p % 10
    if last > 0:
        yield p * 10 + last - 1
    yield p * 10 + last
    if last + 1 < 10:
        yield p * 10 + last + 1


while len(lunlun) <= K:
    for new in genelate_lunlun(lunlun[p]):
        lunlun.append(new)
    p += 1

# print(lunlun)
print(lunlun[K - 1])

Submission status: Accepted

Solution code:
n = 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(10 * i + i % 10)
            tmp.append(10 * i + i % 10 + 1)
        elif i % 10 == 9:
            tmp.append(10 * i + i % 10 - 1)
            tmp.append(10 * i + i % 10)
        else:
            tmp.append(10 * i + i % 10 - 1)
            tmp.append(10 * i + i % 10)
            tmp.append(10 * i + i % 10 + 1)
    lunlun.append(tmp)
ans = []
for i in lunlun:
    for j in i:
        ans.append(j)
print(ans[n-1])

Submission status: Accepted

Solution code:
from collections import deque

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

while q:
    n = q.popleft()
    K -= 1
    
    if K==0:
        print(n)
        exit()
    
    for m in range(max(0, n%10-1), min(9, n%10+1)+1):
        q.append(10*n+m)

Submission status: Accepted

Solution code:
import sys
k = int(input())
if k <= 9:
	print(k)
	sys.exit()

def judge(s):
	for i in range(1,len(s)):
		if abs(int(s[i-1]) - int(s[i])) > 1:
			return 0
	return 1

q = ['1','2','3','4','5','6','7','8','9']
cnt = 9
cond = False
while True:

	cp = q.pop(0)
	digit = int(cp[-1])
	for d in range(-1,2):
		if 0 <= digit + d <= 9:
			cnt += 1
			if cnt == k:
				ans = cp+str(digit+d)
				cond = True
				break
			q.append(cp+str(digit+d))
	
	if cond:
		break
print(ans)

Submission status: Accepted

Solution code:
# BFS
from collections import deque
def bfs(x):
    q = deque()
    for i in range(1, 10):
        q.append((i, i))
    #(a,b):=(ルンルン数,末尾の数)
    cnt=9
    while q:
        # qの先頭を取り出す
        num, back_number = q.popleft()
        for i in [-1, 0, 1]:
            temp = back_number + i
            if temp == -1: continue
            if temp == 10: continue
            cnt += 1
            q.append((num * 10 + temp, temp))
            if cnt == x :
                return q[-1][0]

x = int(input())
if x <= 9:
    print(x)
else:
    print(bfs(x))

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
lunlun = deque([])
ans = 0

# 一桁のルンルン数
for i in range(1, 10):
    lunlun.append(str(i))
if k < 10:
    ans = lunlun[k - 1]

# 二桁以上のルンルン数
cnt = 9
while cnt < k + 1:
    # 1番小さなルンルン数を抜き出す
    l = lunlun.popleft()
    l_last = int(l[-1])
    if l_last != 0:
        lunlun.append('{}{}'.format(l, l_last - 1))
        cnt += 1
        if cnt == k:
            ans = lunlun[-1]
            break
    lunlun.append('{}{}'.format(l, l_last))
    cnt += 1
    if cnt == k:
        ans = lunlun[-1]
        break
    if l_last != 9:
        lunlun.append('{}{}'.format(l, l_last + 1))
        cnt += 1
        if cnt == k:
            ans = lunlun[-1]
            break

print(ans)

Submission status: Accepted

Solution code:
k = int(input())

from collections import *
arr = deque(list(range(1,10)))

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

print(x)

Submission status: Accepted

Solution code:

import copy

k = int(input())

lun = [1,2,3,4,5,6,7,8,9]
tlun = []
tlun = copy.deepcopy(lun)
length = 2
while len(lun) < k:
    tmp = []
    for x in tlun:
        y = str(x)
        xt = int( y[-1] )
        a = xt + 1
        b = xt - 1
        if b != -1:
            lun.append(int(y+str(b)))
            tmp.append(int(y+str(b)))
        
        lun.append(int(y+str(xt)))
        tmp.append(int(y+str(xt)))

        if a != 10:
            lun.append(int(y+str(a)))
            tmp.append(int(y+str(a)))
        

    tlun = copy.deepcopy(tmp)

# lun.sort()
print(lun[k-1])

Submission status: Accepted

Solution code:
import collections
import sys


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


def bfs(K):
    q = collections.deque(list("123456789"))
    ans = list("123456789")
    while len(ans) < K:
        n = q.popleft()
        for i in range(int(n[-1]) - 1, int(n[-1]) + 2):
            if 0 <= i < 10:
                q.append(n + str(i))
                ans.append(n + str(i))

    return ans[K - 1]


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

n_popleft = n.popleft
n_append = n.append
for i in range(k) :
  ans = n_popleft()
  a = ans*10+ans%10
  if a%10 == 0 :
    ap = [a,a+1]
  elif a%10 == 9 :
    ap = [a-1,a]
  else :
    ap = [a-1,a,a+1]
  for num in ap :
    n_append(num)
  
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
K = int(input())

ans = []
for l in range(10):
    for s in range(1, 10):
        for pattern in product([-1, 0, 1], repeat=l):
            X = [s]
            for p in pattern:
                if not (0 <= X[-1] + p <= 9):
                    break
                X.append(X[-1] + p)
            else:
                ans.append(int(''.join(map(str, X))))

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

Submission status: Accepted

Solution code:
# 初期入力
K = int(input())

#
runrun_su = [i for i in range(1,10)]
tyusi = False
while tyusi ==False:
    if K< len(runrun_su):
        print(runrun_su[K-1])
        tyusi =True 
        break
    else:
        for i in runrun_su:
            i_mod_10 = i % 10
            if 1<= i_mod_10 and i_mod_10 < 9:           # 通常3つ増える
                runrun_su.append(10*i + i_mod_10 -1)
                runrun_su.append(10*i + i_mod_10   )
                runrun_su.append(10*i + i_mod_10 + 1)

            elif i % 10 ==9:                            # 位が上がる前
                runrun_su.append(10*i +i_mod_10 -1)
                runrun_su.append(10*i +i_mod_10   )
            elif i % 10 ==0:                            # 位が上がった後
                runrun_su.append(10*i )
                runrun_su.append(10*i +1)
            #print(runrun_su)
            if K< len(runrun_su):
                print(runrun_su[K-1])
                tyusi =True 
                break

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
from collections import deque

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

K = i_i()
q = deque(range(1, 10))

for _ in range(K):
    x = q.popleft()

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

Submission status: Accepted

Solution code:
from collections import *
d=deque([i for i in range(1,10)])
for _ in range(int(input())):
    i=d.popleft()
    j=i%10
    for k in range(max(0,j-1),min(10,j+2)):
        d.append(i*10+k)
print(i)

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
s = deque([1,2,3,4,5,6,7,8,9])
for i in range(k):
    c = s.popleft()
    d = int(str(c)[-1])
    for j in range(max(0,d-1),min(10,d+2)):
        s.append(int(str(c)+str(j)))
print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
k = int(input())
a = []
for i in range(1, 10):
    a.append(i)
while True:
    if k <= len(a):
        print(a[k - 1])
        exit()
    k -= len(a)
    old = []
    a, old = old, a
    for x in old:
        for i in range(-1, 2):
            d = x % 10 + i
            if d < 0 or d > 9:
                continue
            nx = x * 10 + d
            a.append(nx)

Submission status: Accepted

Solution code:
import math
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
mod = 10**9 + 7 
sys.setrecursionlimit(1000010)

K = ni()
if K <=9: 
    print(K)
    exit(0)

u = []
dp = [[1] * 10,] 
sum = 0
for j in range(1,10):
    sum += dp[0][j]
# print(sum)
u.append(sum)
for i in range(1,10):
    a = dp[i-1]
    b = [a[0]+a[1],]
    for j in range(1,9):
        b.append(a[j-1]+a[j]+a[j+1])
    b. append(a[8]+a[9])
    dp.append(b)
    # print(dp)
    for j in range(1,10):
        sum += dp[i][j]
    # print(sum)
    u.append(sum)
# print(u)

def ggg(upN,keta,n):
    # print("ggg",upN,keta,n)
    s = 0
    start = max(upN-1,0)
    end = min(upN+ 1,9)
    for i in range(start, end+1):
        #print("keta",keta,start,"N",n,s,dp[keta -1][i])
        if n <= s + dp[keta -1][i]:
            #print("debug")
            if keta == 1:
                    # print("deb2")
                    return i
            else:
                return i * 10 **(keta -1) + ggg(i,keta-1,n -s)
        s += dp[keta-1][i]
        #print("xxx",i,s)
    print("Erorr ggg",upN,keta,n)
    exit(-1)

def fff (keta,n):
    #print("fff",keta,n)
    s = 0
    for i in range(1,10):
        if n <= s + dp[keta-1][i]:
            return i * 10 ** (keta-1) + ggg(i,keta-1,n-s)
        s += dp[keta-1][i]
    print("Error")
    exit(-1)


for i in range(1,10):
    if K <= u[i]:
        print(fff(i+1,K-u[i-1]))
        exit(0)

Submission status: Accepted

Solution code:
N=int(input())
L=[set() for i in range(11)]
for i in range(1,10):
    L[0].add(i)
#print(L[0])
for i in range(1,11):
    for j in L[i-1]:
        if j%10==0:
            L[i].add(j*10)
            L[i].add(j*10+1)
        elif j%10==9:
            L[i].add(j*10+8)
            L[i].add(j*10+9)
        else:
            M=(j%10)
            for k in range(3):
                L[i].add(j*10+M-1+k)
SET=L[0]
for i in range(1,11):
    SET|=L[i]
SET=list(SET)
SET.sort()
print(SET[N-1])

Submission status: Accepted

Solution code:
# Problem D - Lunlun Number

# input
K = int(input())

# initialization
num_queue = []
k = 1

# count
while True:
    if k>=1 and k<=9: # 1桁の場合
        num_queue.append(k)
        k += 1
    else: # 2桁以降の場合
        min_num = str(num_queue.pop(0))
        keta_1 = int(min_num[-1])
        if keta_1==0:
            for i in range(2):
                tmp = int(min_num + str(i))
                num_queue.append(tmp)
                k += 1
                if k>K:
                    break
        elif keta_1==9:
            for i in range(keta_1-1, keta_1+1):
                tmp = int(min_num + str(i))
                num_queue.append(tmp)
                k += 1
                if k>K:
                    break
        else:
            for i in range(keta_1-1, keta_1+2):
                tmp = int(min_num + str(i))
                num_queue.append(tmp)
                k += 1
                if k>K:
                    break
    if k>K:
        break

# output
print(num_queue[-1])

Submission status: Accepted

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

# FIFOキューの作成
q = queue.Queue()
for i in range(1, 10):
    q.put(i)
k = 0
while k< K:
    x = q.get()
    k += 1
    if x %10 != 0:
        q.put(x*10 + x%10 - 1)
    q.put(x*10 + x%10)
    if x % 10 != 9:
        q.put(x*10 + x%10 +1)
    
print(x)

Submission status: Accepted

Solution code:
import queue

k = int(input())

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

def make_lunlun(p):
    last = p%10
    if last != 0:
        lunlun.put(p * 10 + last - 1)
    lunlun.put(p*10 + last)
    if last != 9:
        lunlun.put(p * 10 + last + 1)

i = 0
while i < k:
    p = lunlun.get()
    make_lunlun(p)
    i += 1
    if i == k:
        print(p)
        break

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k = int(input())

from collections import deque
queue = deque(range(1,10))
count = 0
while count < k:
  count += 1
  tmp = queue.popleft()
  tail = tmp%10
  if tail != 0:
    queue.append(10*tmp+tail-1)
  queue.append(10*tmp+tail)
  if tail != 9:
    queue.append(10*tmp+tail+1)

print(tmp)

Submission status: Accepted

Solution code:
k = int(input())
a = [i for i in range(1, 10)]
while True:
    if k <= len(a):
        print(a[k-1])
        exit()
    k -= len(a)
    old = []
    old, a = a, old
    for i in range(len(old)):
        for j in range(-1, 2):
            d = old[i]%10+j
            if d >= 0 and d <= 9:
                a.append(old[i]*10+d)

Submission status: Accepted

Solution code:
K = int(input())
lunlun = [i for i in range(1,10)]
while True:
    if len(lunlun) >= K:
        break
    K -= len(lunlun)
    new = []
    for lun in lunlun:
        last_digit = lun %10
        for diff in range(-1, 2):
            if last_digit +diff >9 or last_digit +diff <0:
                continue
            new.append(10*lun +last_digit +diff)
    lunlun = new
print(lunlun[K-1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

d = deque(list(range(1, 10)))
c = 0
v = 0
while c < k:
    v = d.popleft()
    c += 1
    if v % 10 == 9:
        d.append(v * 10 + 8)
        d.append(v * 10 + 9)
    elif v % 10 == 0:
        d.append(v * 10)
        d.append(v * 10 + 1)
    else:
        t = v % 10
        d.append(v * 10 + t - 1)
        d.append(v * 10 + t)
        d.append(v * 10 + t + 1)
print(v)

Submission status: Accepted

Solution code:
import queue
n = int(input())
q = queue.Queue()
count=0
p=0
for i in range(1,10):
    q.put(i)
while count!=n:
    count+=1
    a = q.get()
    p = a
    str_a = str(a)
    if str_a[-1]=='0':
        q.put(a*10)
        q.put(a*10+1)
    elif str_a[-1]=='9':
        q.put(a*10+8)
        q.put(a*10+9)
    else:
        q.put(a*10 + int(str_a[-1])-1)
        q.put(a*10 + int(str_a[-1]))
        q.put(a*10 + int(str_a[-1])+1)
print(p)

Submission status: Accepted

Solution code:
# bfs, time O(k), space O(k)

from collections import deque
k = int(input())
q = deque([i for i in range(1, 10)])
# sz = 10
for _ in range(k):
    cur = q.popleft()
    nxt = cur * 10 + cur % 10
    if cur % 10 != 0:
        q.append(nxt - 1)
    q.append(nxt)
    if cur % 10 != 9:
        q.append(nxt + 1)
#     sz = max(sz, len(q))
# print(sz)
print(cur)

Submission status: Accepted

Solution code:
import sys
from collections import deque


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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue
def solve(n):
    if n < 10:
        return n
    cnt = 0
    next = queue.Queue()
    for i in range(1, 10):
        next.put(i)
        cnt += 1
    while True:
        i = next.get()
        for j in range(i % 10 - 1, i % 10 + 2):
            if j < 0 or 9 < j:
                continue
            next.put(i * 10 + j)
            cnt += 1
            if cnt == n:
                return i * 10 + j
k = int(input())
next = queue.Queue
print(solve(k))

Submission status: Accepted

Solution code:
from queue import Queue

k = int(input())

q = Queue()

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

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

Submission status: Accepted

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

lunlun = deque(list(range(1, 10)))

added_count = len(lunlun)
start_index = 0
while True:
  if (len(lunlun) > K):
    break
  
  next_count = 0
  for i in range(added_count):
    check_num = lunlun[start_index + i]
    for n in range(-1, 2):
      d = check_num % 10 + n
      if(d < 0 or 9 < d):
        continue
      to_add = check_num * 10 + d
      lunlun.append(to_add)
      next_count += 1
  
  start_index += added_count
  added_count = next_count

print(lunlun[K - 1])

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

Submission status: Accepted

Solution code:
K = int(input())

# キューに候補の値を順に入れていく方法で解く
from collections import deque
d = deque()

# 事前に１桁のを入れる
for i in range(1,10):
    d.append(i)

x = 0
# 取り出しをK回行う
for i in range(K):
    x = d.popleft()
    # 次の候補を入れる
    # xの右に末尾プラマイ１をくっつけた値を入れる
    # ただし、末尾0のときと、９のときは例外あり
    tmp = x%10
    if tmp != 0:
        d.append(10*x + (tmp-1))
    d.append(10*x + tmp)
    if tmp != 9:
        d.append(10*x + (tmp+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"])
cnt = 1
while cnt < k:
  add = deque()
  num = q.popleft()
  if num[-1] == "0":
    add.append(num + "0")
    add.append(num + "1")
  elif int(num[-1]) < 9:
    add.append(num + str(int(num[-1]) - 1))
    add.append(num + num[-1])
    add.append(num + str(int(num[-1]) + 1))
  else:
    add.append(num + "8")
    add.append(num + "9")
  q.extend(add)
  cnt += 1
print(q.popleft())

Submission status: Accepted

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


#初めに、1~9まではキューに入れておく
q = deque([i for i in range(1, 10)])
ans = 0
while True:
    v = q.popleft()
    ans += 1
    if ans == k:
        print(v)
        break
    
    #末尾の1桁を求める
    last_digit = v % 10
    #求めた末尾の1桁との差が1になる数字を最後の1桁にする
    #つまり、末尾の1桁に対して-1,+0,+1とする計算を行う
    for i in range(-1, 2):
        new_digit = last_digit + i
        if new_digit < 0 or new_digit > 9:
            continue
        q.append(v * 10 + new_digit)

Submission status: Accepted

Solution code:
k = int(input())

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


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


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:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

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

K = I()

q = [1,2,3,4,5,6,7,8,9]
n = len(q)
num = 0
while q:
    q1 = []
    for v in q:
        num += 1
        if num == K:
            print(v)
            exit()
        for u in next_digit(int(str(v)[-1])):
            q1.append(10*v+u)
    q = q1

Submission status: Accepted

Solution code:
from collections import deque


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

    print(q.popleft())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 2020/04/04
# AtCoder Beginner Contest 161 - D

runsu = list()

def makerunrun(s):

    if int(s) > 3234566667:
        return 0

    runsu.append(int(s))
    lketa = int(s[len(s)-1])
    if lketa > 0:
        wks = s + str(lketa - 1)
        makerunrun(wks)
    
    wks = s + str(lketa)
    makerunrun(wks)
    
    if lketa < 9:
        wks = s + str(lketa + 1)
        makerunrun(wks)
    
# Input
k = int(input())

# Make Runrun List
for i in range(1, 10):
    makerunrun(str(i))

runsu.sort()

# Output
print(runsu[k-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
queue = deque([n for n in range(1, 10)])

res = None
cnt = 0
while True:
    x = queue.popleft()
    cnt += 1
    if cnt == K:
        res = x
        break
    xmod10 = x % 10
    if xmod10 != 0:
        queue.append(10*x+(xmod10-1))
    queue.append(10*x+xmod10)
    if xmod10 != 9:
        queue.append(10*x+(xmod10+1))

print(res)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    k = int(input())
    q = deque(range(1, 10))
    for _ in range(k):
        x = q.popleft()
        y = x * 10 + x % 10
        if x % 10 > 0:
            q.append(y - 1)
        q.append(y)
        if x % 10 < 9:
            q.append(y + 1)
    print(x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!python3

from collections import deque
iim = lambda: map(int, input().rstrip().split())

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

    if K <= 9:
        print(K)
        return

    s1 = "0123456789"
    s2 = { str(i) : s1[i-1:i+2] for i in range(1, 9) }
    s2["0"] = "01"
    s2["9"] = "89"

    dq = deque(s1[1:])
    for i in range(K):
        ans = dq.popleft()

        for c2 in s2[ans[-1]]:
            dq.append(ans + c2)

        if len(dq) + i >= K:
            print(dq[K-i-2])
            return


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import deque

def create_lunlun(n):
    q=deque([i for i in range(1,10)])
    count=0
    while count<n:
        count+=1
        a=q.popleft()
        if count==n:
            print(a)
            exit()
        for i in range(-1,2):
            d=a%10+i
            if d<0 or d>9:
                continue
            q.append(a*10+d)
    return q

def main():
    N=int(input())
    print(create_lunlun(N))

main()