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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)[2:]
# oct_str = oct(i)[2:]
# hex_str = hex(i)[2:]

##### とても大きな数 と 小数の計算誤差 #####
# 「Decimal」は計算誤差を 0にできる。必要に応じて粒度を設定せよ。
# getcontext().prec = 100
#
# tmp = Decimal(i)
# A,B = map(Decimal, input().split())
# ans = A * B

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	K = inputInt()

	dp = []
	dp.append(["1","2","3","4","5","6","7","8","9"])
	ans = [1,2,3,4,5,6,7,8,9]

	for i in range(10):
		testcase = dp[-1]
		nextcalse = []
		for val in testcase:
			base = val[-1]
			manaka = val + base
			nextcalse.append(manaka)
			ans.append(int(manaka))

			samp = int(base)
			if samp - 1 >= 0:
				rinko = val + str(samp - 1)
				nextcalse.append(rinko)
				ans.append(int(rinko))

			if samp + 1 <= 9:
				nene = val + str(samp + 1)
				nextcalse.append(nene)
				ans.append(int(nene))
		dp.append(nextcalse)

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







#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 2分検索のリバース
def bisect_left_reverse(a, x):
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

def bisect_right_reverse(a, x):
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 2分検索
# 存在しない場合: None 存在する場合: その値
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Accepted

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

qu=deque(list(range(1,10)))
count=0
while True:
  x=qu.popleft()
  count+=1
  if count==k:
    print(x)
    break
  if str(x)[-1]!="0":
    qu.append(int(str(x)+str(int(str(x)[-1])-1)))
  qu.append(int(str(x)+str(x)[-1]))
  if str(x)[-1]!="9":
    qu.append(int(str(x)+str(int(str(x)[-1])+1)))

Submission status: Accepted

Solution code:
def generate(n):
    if n == 1:
        for i in range(1, 10):
            yield [i]
    else:
        for A in generate(n - 1):
            for i in range(10):
                if abs(A[-1] - i) <= 1:
                    yield A + [i]


L = []
for n in range(1, 11):
    for A in generate(n):
        L.append(int(''.join([str(a) for a in A])))
k = int(input())
print(L[k - 1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
k = I()
que = deque([])
for i in range(1,10):
    que.append(i)
if k <= 9:
    print(que[k-1])
    exit()
while que:
    num = que.popleft()
    if k == 1:
        print(num)
        exit()
    lo = num%10
    if 0 <= lo - 1:
        que.append(num*10 + lo-1)
    que.append(num*10 + lo)
    if lo + 1 <= 9:
        que.append(num*10 + lo + 1)
    k -= 1

Submission status: Accepted

Solution code:
def lunlun(K,S):
    if len(S) >= K:
        S.sort()
        print(S[K-1])
        return

    for a in range(len(S)):
        i = S[a]
        rem = i%10
        n = 10*i + rem

        if rem == 9:
            S.append(n)
            S.append(n-1)
        elif rem == 0:
            S.append(n)
            S.append(n+1)
        else:
            S.append(n)
            S.append(n+1)
            S.append(n-1)
    lunlun(K,list(set(S)))


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

lunlun(K,S)

Submission status: Accepted

Solution code:
k = int(input())

if k <= 9:
    print(k)
k -= 9

lst = list(range(1, 10))
while k > 0:
    new = []
    for num in lst:
        amari = num % 10
        if amari == 0:
            new.append(num*10)
            new.append(num*10+1)
        elif amari == 9:
            new.append(num*10+8)
            new.append(num*10+9)
        else:
            new.append(num*10+(amari-1))
            new.append(num*10+amari)
            new.append(num*10+(amari+1))
    if len(new) >= k:
        print(new[k-1])
        exit()
    else:
        k -= len(new)
        lst = new

Submission status: Accepted

Solution code:
K = int(input())
S = set([1,2,3,4,5,6,7,8,9])
prev = set([1,2,3,4,5,6,7,8,9])

while len(S) < K:
    temp = set([])
    for e in prev:
        if e%10 == 0:
            temp.add(e*10)
            temp.add(e*10+1)
        elif e%10 == 9:
            temp.add(e*10+8)
            temp.add(e*10+9)
        else:
            temp.add(e*10+e%10-1)
            temp.add(e*10+e%10)
            temp.add(e*10+e%10+1)
    prev = temp
    S = S|temp
print(sorted(list(S))[K-1])

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

K = int(input())

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

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

for _ in range(K-1):
    lli = heappop(ll)
    next_nums = next_num(lli)
    for ni in next_nums:
        heappush(ll, lli*10+ni)

ans = ll[0]
print(ans)

Submission status: Accepted

Solution code:
K = int(input())

a = list(range(1, 10))
i = 0
while len(a) < K:
  A = []
  for j in range(3):
    n = str(a[i])
    if j == 0 and int(n[-1]) - 1 >= 0:
      A.append(int(n + str(int(n[-1]) - 1)))
    elif j == 1:
      A.append(int(n + n[-1]))
    elif j == 2 and int(n[-1]) + 1 < 10:
      A.append(int(n + str(int(n[-1]) + 1)))
  a += A
  i += 1
print(a[K-1])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

k = int(input())

lunlun_num = []

def dfs(s):
    if len(s) > 10:
        return
    s = list(s)
    s_last = int(s[-1])
    for i in range(s_last - 1, s_last + 2):
        if 0 <= i <= 9:
            s.append(str(i))
            lunlun_num.append(int("".join(s)))
            dfs("".join(s))
            s.pop()

for i in range(1, 10):
    dfs(str(i))
    lunlun_num.append(int(i))

lunlun_num.sort()
# print(lunlun_num)

print(lunlun_num[k - 1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

LL = [i for i in range(1, 10)]
LL = deque(LL)
for j in range(k):
    num = LL.popleft()
    amari = num % 10
    kouho = [amari - 1, amari, amari + 1]
    for nn in kouho:
        if nn >= 0 and nn < 10:
            LL.append(10 * num + nn)
print(num)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

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

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

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K = INT()

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

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

print(n)

Submission status: Accepted

Solution code:
import queue

k = int(input())
q = queue.Queue()

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

Submission status: Accepted

Solution code:
K = int(input())
A = [list(range(1, 10))]
cnt = 0

while cnt < K * 2:
    B = []
    for a in A[-1]:
        r = a % 10
        a *= 10
        for i in range(max(0, r - 1), min(r + 2, 10)):
            B.append(a + i)
    cnt += len(B)
    A.append(B)

A = [a for B in A for a in B]
A.sort()
print(A[K - 1])

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest


def recursive(base, lunluns):

    lunluns.append(base)

    # 想定される最大値を超える場合何もせず戻る（再帰の終わり)
    if len(base) > 10 or len(base) > 9 and int(base[0]) > 3:
        return
    target = int(base[-1])

    if target is 0:
        add_num = ["0", "1"]
    elif target is 9:
        add_num = ["8", "9"]
    else:
        add_num = [str(target - 1), str(target), str(target+1)]

    for i in add_num:
        recursive("".join(base + str(i)), lunluns)


def resolve():

    k = int(input())

    # 1桁は全てルンルンNoなので、初期値に設定(0も加えておくことで、kと数え方を合わせる)
    lunluns = ["0"]

    # 再帰的処理
    for i in ["1", "2", "3", "4", "5", "6", "7", "8", "9"]:
        recursive(i, lunluns)

    lunluns = list(map(int, lunluns))
    lunluns.sort()

    print(lunluns[k])


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """15"""
        output = """23"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """1"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """13"""
        output = """21"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """100000"""
        output = """3234566667"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque

K=int(input())

num_str=[str(i) for i in range(10)]

numbers=deque()
for i in range(1,len(num_str)):
    numbers.append((i,num_str[i]))

times=0
while numbers:
    times+=1
    if times==K:
        break
    else:
        num=numbers.popleft()
        for i in range(3):
            index=num[0]-1+i
            if index>=0 and index<10:
                numbers.append((num[0]-1+i,num[1]+num_str[num[0]-1+i]))


print(numbers.popleft()[1])

Submission status: Accepted

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

Q = deque([1,2,3,4,5,6,7,8,9])
a = 0
for i in range(N):
  a = Q.popleft()
  if a%10 > 0:
    Q.append(a*10 + (a%10 -1))
  Q.append(a*10 + a%10)
  if a%10 < 9:
    Q.append(a*10 + (a%10 +1))

print(a)

Submission status: Accepted

Solution code:
import sys
# from collections import defaultdict
# from collections import Counter
from queue import Queue
# sys.setrecursionlimit(2000000)

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

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

    for i in range(1, K+1):
        lunlun = queue.get()
        digit = lunlun % 10

        new_lunluns = []
        # pushする順番は小さい順にする必要がある
        if digit == 0:
            new_lunluns.append(lunlun * 10 + digit)
            new_lunluns.append(lunlun * 10 + digit + 1)
        elif digit == 9:
            new_lunluns.append(lunlun * 10 + digit - 1)
            new_lunluns.append(lunlun * 10 + digit)
        else:
            new_lunluns.append(lunlun * 10 + digit - 1)
            new_lunluns.append(lunlun * 10 + digit)
            new_lunluns.append(lunlun * 10 + digit + 1)

        for new_lunlun in new_lunluns:
            queue.put(new_lunlun)

    print(lunlun)
    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Accepted

Solution code:
import heapq

K = int(input())
q = [i for i in range(1, 10)]
ans = []
for i in range(K):
  n = heapq.heappop(q)
  ans += [n]
  stn = str(n)
  last = (stn[-1])
  cand1 = int(str(n) + last)
  heapq.heappush(q, cand1)
  if 0 < int(last):
    cand2 = int(str(n) + str(int(last)-1))
    heapq.heappush(q, cand2)
  if int(last) < 9:
    cand3 = int(str(n) + str(int(last)+1))
    heapq.heappush(q, cand3)

print(ans[-1])

Submission status: Accepted

Solution code:
# 再帰的なDFS
def rec(d, val, nums):
    nums.append(val)
    if d == 10:
        return
    
    for delta in (-1, 0, 1):
        add = val % 10 + delta
        if add >= 0 and add <= 9:
            rec(d+1, val * 10 + add, nums)

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

main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
k=int(input())

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

for i in range(k):
    l=q.pop(0)
    if l%10!=0:
        q.append(10*l+l%10-1)
    q.append(10*l+l%10)
    if l%10!=9:
        q.append(10*l+l%10+1)
    
print(l)

Submission status: Accepted

Solution code:
import sys

k=int(input())

lun=[i for i in range(1,10)]
while 1>0:
    if k <=len(lun): 
        print(lun[k-1])
        sys.exit()
    else:
        k-=len(lun)
        lunw=[]
        for i in range(len(lun)):
            if lun[i]%10!=0:
                lunw.append(lun[i]*10+lun[i]%10-1)
            lunw.append(lun[i]*10+lun[i]%10)
            if lun[i]%10!=9:
                lunw.append(lun[i]*10+lun[i]%10+1)
    lun =lunw

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    all = []

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

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

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
K = int(input())

ans_list = []
def dfs(A):
    if len(A)!=0 and int("".join(A))<=10**10:
        ans_list.append(int("".join(A)))
    elif len(A)!=0 and int("".join(A))>10**10:
        return
    if len(A)==0:
        for i in range(1, 10, 1):
            A.append(str(i))
            dfs(A)
            A.pop()
        return

    for i in range(0, 10, 1):
        if abs(int(A[-1])-i)<=1:
            A.append(str(i))
            dfs(A)
            A.pop()
    return
dfs([])
ans_list.sort()
print(ans_list[K-1])

Submission status: Accepted

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

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

while(1):
    if k <= len(runrun):
        print(runrun[k-1])
        break
    k -= len(runrun)
    old = []
    runrun, old = old, runrun
    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
            runrun.append(nx)

Submission status: Accepted

Solution code:
K = int(input())

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

while K > len(old):
    new = []
    K -= len(old)
    for i in range(len(old)):
        tmp = old[i]
        l = tmp % 10
        if l != 0:
            new.append(tmp*10+l-1)
        new.append(tmp*10+l)
        if l != 9:
            new.append(tmp*10+l+1)
    old = new[:]



print(old[K-1])

Submission status: Accepted

Solution code:
k = int(input())
from collections import deque
lun = deque([str(n)for n in list(range(1,10))])
if k<=9:
    print(lun[k-1])
    exit()
l = 9
while l<k:
    n = lun.popleft()
    c = int(n[-1])
    if c>0:
        lun.append(n+str(c-1))
        l+=1
        if l==k:break
    lun.append(n+str(c))
    l+=1
    if l==k:break
    if c<9:
        lun.append(n+str(c+1))
        l+=1
        if l==k:break
    
print(lun[-1])

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(k-1):
    # popをk-1回やる
    x = q.popleft()
    y = int(str(x)[-1])
    if y-1 >= 0:
        q.append(int(str(x)+str(y-1)))
    q.append(int(str(x)+str(x)[-1]))
    if y+1 < 10:
        q.append(int(str(x)+str(y+1)))

print(q[0])

Submission status: Accepted

Solution code:
k = int(input())

class Myqueue:
  def __init__(self):
    self.queue = []
    
  def enqueue (self, item):
    self.queue.append(item)
  
  def dequeue (self):
    if len(self.queue) ==0:
      return None
    result =self.queue[0]
    del self.queue[0]
    return result

myq = Myqueue()
myq.enqueue(1)
myq.enqueue(2)
myq.enqueue(3)
myq.enqueue(4)
myq.enqueue(5)
myq.enqueue(6)
myq.enqueue(7)
myq.enqueue(8)
myq.enqueue(9)

K = 9
s = 9
if k < 10:
  None
elif k >= 10:
  while s <= k:
    x = myq.dequeue()
    I = x % 10
    if I == 0:
      myq.enqueue(x*10 + I)
      myq.enqueue(x*10 + (I+1))
      s += 2
    elif I ==9:
      myq.enqueue(x*10 + (I-1))
      myq.enqueue(x*10 + I)
      s += 2
    else:
      myq.enqueue(x*10 + (I-1))
      myq.enqueue(x*10 + I)
      myq.enqueue(x*10 + (I+1))
      s += 3

if k < 10:
  print(k)
elif s - 2 == k:
  print(myq.queue[-3])
elif s - 1 == k:
  print(myq.queue[-2])
elif s == k:
  print(myq.queue[-1])
elif s -3 == k:
  print(myq.queue[-4])

Submission status: Accepted

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

def dfs(num, A):
  A.append(num)

  if(len(str(num)) == 10):
    return 0

  for i in range(-1, 2):
    s = num%10 + i
    if(s >= 0 and s <= 9):
      dfs(num * 10 + s, A)

  return 0

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

n = sorted(n)

print(n[k - 1])

Submission status: Accepted

Solution code:
def main():
    runrun = {1: [1, 2, 3, 4, 5, 6, 7, 8, 9]}
    for i in range(2, 13):
        r = []
        for v in runrun[i-1]:
            num = v % 10
            for j in range(max(0, num-1), min(10, num+2)):
                r.append(v*10+j)
        runrun[i] = r

    mrunrun = []
    for _, v in runrun.items():
        mrunrun.extend(v)
    mrunrun.sort()
    k = int(input())
    print(mrunrun[k-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k = int(input())

lun_ls = []
def change_to_num(ls):
    ls = list(map(str, ls))
    strnum = ''.join(ls)
    return int(strnum)
def lun(num):
    '''
    渡された数が上限行ってなければlun_lsに追加して、次の数で再帰呼出
    '''
    if num > 3234566667:
        return

    lun_ls.append(num)
    last = num % 10
    for nex in range(last-1, last+2):
        if 0<= nex < 10:
            new_str = str(num) + str(nex)
            new = int(new_str)
            lun(new)
            
for start in range(1,10):
    lun(start)
lun_ls.sort()
print(lun_ls[k-1])

Submission status: Accepted

Solution code:
from collections import deque

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

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

for i in range(K):
    k=X.popleft()
    if k%d!=0:
        X.append(k*10+(k%d)-1)
        
    X.append(k*10+(k%d))

    if k%d!=d-1:
        X.append(k*10+(k%d)+1)

print(k)

Submission status: Accepted

Solution code:
k = int(input())
import sys

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

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

def check(n,cc):
    cc += 1
    if(cc == k):
        print(n)
        sys.exit()
    return cc


for i in lun:
    new_lun = []
    for j in i:
        a = j*10
        b = j%10
        if(b != 0):
            new_lun.append(a + b - 1)
            count = check(a + b - 1,count)
        new_lun.append(a + b)
        count = check(a + b,count)
        if(b != 9):
            new_lun.append(a + b + 1)
            count = check(a + b + 1, count)
    lun.append(new_lun)

Submission status: Accepted

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

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

while K > 0:
    q = Q.popleft()
    a = q % 10
    if a == 0:
        Q.append(q * 10)
        Q.append(q * 10 + 1)
    elif a == 9:
        Q.append(q * 10 + 8)
        Q.append(q * 10 + 9)
    else:
        Q.append(q * 10 + a - 1)
        Q.append(q * 10 + a)
        Q.append(q * 10 + a + 1)
    K -= 1

print(q)

Submission status: Accepted

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

runn=['0','1','2','3','4','5','6','7','8','9']
List=['1','2','3','4','5','6','7','8','9']
while True:
    if len(runn)-1>K:
        print(int(runn[K]))
        break
    else:
        list1=[]
        for i in range(len(List)):
            
            if List[i][-1]=='0':
                list1.append(List[i]+'0')
                list1.append(List[i]+'1')
            
            for u in range(1,9):
                if List[i][-1]=='{}'.format(u):
                    list1.append(List[i]+'{}'.format(u-1))
                    list1.append(List[i]+'{}'.format(u))
                    list1.append(List[i]+'{}'.format(u+1))
            if List[i][-1]=='9':
                list1.append(List[i]+'8')
                list1.append(List[i]+'9')
           # print(list1)
        List=list1
        runn=runn+list1
        #print(runn)

Submission status: Accepted

Solution code:
from functools import reduce

from itertools import product
k = int(input())
if k < 10:
    print(k)
else:
    i = 1
    sigma = 9
    while sigma < k:
        L = product([-1, 0, 1], repeat=i)
        # print(L)

        def f(n, v):
            returnlist = []
            for j in range(len(v)+1):
                if j == 0:
                    returnlist.append(n)
                else:
                    x = returnlist[-1]
                    returnlist.append(x + v[j-1])
            return returnlist
        biglist = []
        for v in L:
            for kk in range(1, 10):
                biglist.append(f(kk, v))
        # print(biglist)
        numbers = []
        for lists in biglist:
            if not (- 1 in set(lists) or 10 in set(lists)):
                x = [(10 ** (i - j)) * lists[j] for j in range(i+1)]
                y = reduce(lambda x, y: x + y, x)
                numbers.append(y)
        numbers.sort()
        if sigma + len(numbers) >= k:
            print(numbers[k - sigma - 1])
            sigma += len(numbers)
        else:
            sigma += len(numbers)
            i += 1

Submission status: Accepted

Solution code:
from collections import deque

k=int(input())


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

i=0
ans=0
while i < k:
    ans=q.popleft()
    if ans%10 != 0:
        q.append(10*ans+ans%10-1)
    q.append(10*ans+ans%10)
    if ans%10 != 9:
        q.append(10*ans+ans%10+1)
    i+=1
print(ans)

Submission status: Accepted

Solution code:
import queue

q = queue.Queue()
K = int(input())

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

ans = 0
for i in range(K):
    ans = q.get()
    if ans % 10 != 0:
        q.put(ans * 10 + (ans % 10) - 1)

    q.put(ans * 10 + (ans % 10))

    if ans % 10 != 9:
        q.put(ans * 10 + (ans % 10) + 1)


print(ans)