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:
n = 100000
k = int(input())

ll_list = []

def ll(d, v):
  if d==10:
    return
  
  r = v%10
  v = v*10
  
  for i in (-1, 0, 1):
    if r+i>=0 and r+i<=9:
      ll(d+1, v+r+i)
      ll_list.append(v+r+i)
      
for i in range(1, 10):
  r = i%10
  v = i*10
    
  ll_list.append(i)
  for j in (-1, 0, 1):
    if r+j>=0 and r+j<=9:
      ll(1, v+r+j)
      ll_list.append(v+r+j)
      
      
ll_list.sort()
print(ll_list[k-1])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

def check(a):
    for l in range(len(a) - 1):
        if not -1 <= a[l] - a[l + 1] <= 1:
            return False
    return True

x = [0]
k = I()
ret = 0
j = len(x) - 1
while True:
    if x == [9] * len(x):
        x = [1] + [0] * len(x)
        ret += 1
        j = len(x) - 1
        if ret == k:
            print(''.join([str(m) for m in x]))
            exit()
    if j and (x[j - 1] + 1 == x[j] or x[j] == 9):
        j -= 1
        continue
    x[j] += 1
    for n in range(j + 1, len(x)):
        x[n] = x[n - 1] - 1 if x[n - 1] else 0
    j = len(x) - 1
    ret += 1
    if ret == k:
        print(''.join([str(m) for m in x]))
        exit()

Submission status: Accepted

Solution code:
k = int(input())
num = 0
for _ in range(k):
  num += 1
  digit = [int(digit) for digit in str(num)]
  len_digit = len(digit)
  flag = False
  for i in range(1, len_digit):
    # current_digit = digit[-i]
    # upper_digit = digit[-i-1]
    if digit[-i] == 10:
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] > digit[-i-1] + 1:
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] < digit[-i-1] - 1:
      digit[-i] = -1
  if digit[0] == 10:
    num = 10 ** len_digit
  else:
    for i in range(1, len_digit):
      if digit[i] == -1:
        for j in range(i, len_digit):
          digit[j] = max(digit[j-1] - 1, 0)
        break
    num = 0
    for d in digit:
      num = num * 10 + d
print(num)

Submission status: Accepted

Solution code:
import heapq
 
heap=[]
N = int(input())
for i in range(1,10):
  heapq.heappush(heap,i)
for i in range(N):
  x = heapq.heappop(heap)
  if x%10!=0:
    heapq.heappush(heap,10*x+(x%10)-1)
  heapq.heappush(heap,10*x+(x%10))
  if x%10!=9:
    heapq.heappush(heap,10*x+(x%10)+1)
  
print(x)

Submission status: Accepted

Solution code:
n=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)
while n!=1:
    x=q.get();k=x%10
    for i in range(max(0,k-1),min(10,k+2)) :
        q.put(10*x+i)
    n-=1
print(q.get())

Submission status: Accepted

Solution code:
n=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)
while n!=1:
    x=q.get();k=x%10
    for i in range(max(0,k-1),min(10,k+2)) :
        q.put(10*x+i)
    n-=1
print(q.get())

Submission status: Accepted

Solution code:
n=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)
while n!=1:
    x=q.get();k=x%10
    for j in [10*x+i for i in range(max(0,k-1),min(10,k+2))] :
        q.put(j)
    n-=1
print(q.get())

Submission status: Accepted

Solution code:
n=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)
while n!=0:
    x=q.get();k=x%10
    for j in [10*x+i for i in range(max(0,k-1),min(10,k+2))] :
        q.put(j)
    n-=1
print(x)

Submission status: Accepted

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

# d:現在の桁数
# val:現在の値
# dist:ここに格納


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


N = int(input())
dist = []
for i in range(1, 10):
    func(1, i, dist)
    #print(func(1, i, dist))
ans = sorted(dist)
print(ans[N-1])

Submission status: Accepted

Solution code:
_,*s=range(10)
for v in s:*t,=range(v*10+max(0,v%10-1),v*10+min(10,v%10+2));s+=t*(v<4e8)
print(s[int(input())-1])

Submission status: Accepted

Solution code:
k=int(input())
a=list(range(1, 10))
b=[]
n=int(len(a))
x=k
while x>n:
  x-=n
  for i in range(n):
    for l in range(3):
      c=(a[i]%10)-1+l
      if 0<=c<=9:
        a.append((a[i]*10)+c)
  del a[0:n]
print(a[x-1])

Submission status: Accepted

Solution code:
k = int(input())
a = []
for i in range(1,10):
    a.append(i)
while(True):
    if k < len(a):
        print(a[k-1])
        break
    else:
        k -= len(a)
        old = a.copy()
        a = []
        for i in old:
            for j in [-1,0,1]:
                d = int(str(i)[-1])+j
                if (d<0) or (d>9):
                    continue
                n = int(str(i)+str(d))
                a.append(n)

Submission status: Accepted

Solution code:
import queue
q=queue.Queue()

K=int(input())
for i in range(1,10):q.put(i)
while(not q.empty()):
    a=q.get()
    K-=1
    if K==0:
        print(a)
        exit()
    for i in range(a%10-1,a%10+1+1):
        if i<0 or i>9:continue
        q.put(a*10+i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(K: int):

    X = set()

    def rec(keta, x):
        X.add(x)
        if keta == 10:
            return
        y = x % 10
        if 0 <= y - 1:
            rec(keta+1, x*10 + y-1)
        rec(keta+1, x*10+y)
        if y+1 <= 9:
            rec(keta+1, x*10+y+1)

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())

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

if n <= 9:
    print(n)
else:
    count = 9
    while count<=n:
        i = query.pop(0)

        if i%10-1>=0:
            query.append(i*10+(i%10-1))
            count += 1
            if count == n:
                print(i*10+(i%10-1))
                break

        query.append(i*10+(i%10))
        count += 1
        if count == n:
            print(i*10+(i%10))
            break

        if i%10+1<=9:
            query.append(i*10+(i%10+1))
            count += 1
            if count == n:
                print(i*10+(i%10+1))
                break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import queue

S = int(input())

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

cnt = 9
num = 9
digit = 0

if S <= 9:
    print(S)
else:
    while cnt <= S:
        num = q.get()
        digit = int(str(num)[-1])
        num = num * 10

        if digit == 0:
            for i in range(2):
                cnt += 1
                if cnt == S:
                    print(num + i)
                    exit()
                else:
                    q.put(num + i)

        elif digit == 9:
            num += digit - 1
            for i in range(2):
                cnt += 1
                if cnt == S:
                    print(num + i)
                    exit()
                else:
                    q.put(num+i)
        else:
            num += digit - 1
            for i in range(3):
                cnt += 1
                if cnt == S:
                    print(num + i)
                    exit()
                else:
                    q.put(num+i)

Submission status: Accepted

Solution code:
k = int(input())
num = 0
for _ in range(k):
  num += 1
  digit = list(map(int, str(num)))
  len_digit = len(digit)
  for i in range(1, len_digit):
    if digit[-i] > min(digit[-i-1] + 1, 9):
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] < digit[-i-1] - 1:
      digit[-i] = -1
  for i in range(1, len_digit):
    if digit[i] == -1:
      for j in range(i, len_digit):
        digit[j] = max(digit[j-1] - 1, 0)
      break
  num = int(''.join(map(str, digit)))
print(num)

Submission status: Accepted

Solution code:
k = int(input())
num = 0
for _ in range(k):
  num += 1
  digit = [int(digit) for digit in str(num)]
  len_digit = len(digit)
  flag = False
  for i in range(1, len_digit):
    # current_digit = digit[-i]
    # upper_digit = digit[-i-1]
    if digit[-i] == 10:
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] > digit[-i-1] + 1:
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] < digit[-i-1] - 1:
      digit[-i] = -1
  if digit[0] == 10:
    num = 10 ** len_digit
  else:
    for i in range(1, len_digit):
      if digit[i] == -1:
        for j in range(i, len_digit):
          digit[j] = max(digit[j-1] - 1, 0)
        break
    num = 0
    for d in digit:
      num = num * 10 + d
print(num)

Submission status: Accepted

Solution code:
def lunlun_maker(l: int) -> int:
    next_lunluns = []
    for e in l:
        nxt = e * 10
        mod = e % 10
        if 0 < mod < 9:
            next_lunluns.extend([nxt + mod - 1, nxt + mod, nxt + mod + 1])
        elif mod == 0:
            next_lunluns.extend([nxt, nxt + 1])
        elif mod == 9:
            next_lunluns.extend([nxt + 8, nxt + 9])
    return next_lunluns


def get_lunlun(num: int) -> int:
    lunluns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    counter = len(lunluns)
    counter_tmp = counter
    while counter < num:
        lunluns = lunlun_maker(lunluns)
        counter_tmp = counter
        counter += len(lunluns)
    return lunluns[num - counter_tmp - 1]


K = int(input())
print(get_lunlun(K))

Submission status: Accepted

Solution code:
k = int(input())
lis = [1,2,3,4,5,6,7,8,9]
i=0
while len(lis) < k:
	m = lis[i]%10
	if m != 0:
		lis.append(int(str(lis[i])+str(m-1)))
	lis.append(int(str(lis[i])+str(m)))
	if m!= 9:
		lis.append(int(str(lis[i])+str(m+1)))
	i+=1
print(lis[k-1])

Submission status: Accepted

Solution code:
K = int(input())
from collections import deque
que = deque()
for i in range(1,10):
  que.append(i)
  
while K > 0:
  a = que.popleft()
  b = a % 10
  if b == 0:
    que.append(a*10 + b)
    que.append(a*10 + b+1)
  elif b == 9:
    que.append(a*10 + b-1)
    que.append(a*10 + b)
  else:
    que.append(a*10 + b-1)
    que.append(a*10 + b)
    que.append(a*10 + b+1)
  K -= 1
print(a)

Submission status: Accepted

Solution code:
# 桁dp + 二分探索
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def lunlun_num(N):
    N = str(N)
    L = len(N)

    dp = [[0]*10 for j in range(L)]
    for j in range(1,int(N[0])):
        dp[0][j] = 1

    flag = True
    for i in range(L-1):
        d = int(N[i+1])
        b = int(N[i])
        
        dp[i+1][0] += dp[i][0] + dp[i][1]
        dp[i+1][9] += dp[i][8] + dp[i][9]
        for j in range(1,9):
            dp[i+1][j] += dp[i][j-1] + dp[i][j] + dp[i][j+1]
        for j in range(1,10):
            dp[i+1][j] += 1

        if flag:
            if d < b - 1:
                flag = False
            elif d <= b + 1:
                for j in range(max(0, b-1),d):
                    dp[i+1][j] += 1
            else:
                for j in range(max(0, b-1),b+2):
                    dp[i+1][j] += 1
                    flag = False

    return sum(dp[L-1]) + 1 if flag else sum(dp[L-1])


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

    # xを決め打って二分探索
    left = 0
    right = 10**10
    while left + 1 < right:
        x = (left + right) // 2

        if lunlun_num(x) >= K:
            right = x
        else:
            left = x
    
    print(right)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue

k = int(input())
q = queue.Queue()
for l in range(10)[1:]:
    q.put(l)
if k < 10:
    print(q.queue[k-1])
    exit()
k -= 9
for l in range(k):
    dequeued = q.get()
    mod = dequeued % 10
    if mod != 0:
        q.put(dequeued * 10 + mod - 1)
    q.put(dequeued * 10 + mod)
    if mod != 9:
        q.put(dequeued * 10 + mod + 1)
print(q.queue[8])

Submission status: Accepted

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

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

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

k -= 9

while k > 0:
    a = q.popleft()
    b = a % 10
    if b == 0:
        q.append(10*a)
        q.append(10*a + 1)
        k -= 2
    elif b != 0 and b != 9:
        q.append(10*a + (b - 1))
        q.append(10*a + b)
        q.append(10*a + (b + 1))
        k -= 3
    else:
        q.append(10*a + 8)
        q.append(10*a + 9)
        k -= 2

if k == -2:
    print(q[-3])
elif k == -1:
    print(q[-2])
elif k == 0:
    print(q[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(1000000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def is_lunlun(n):
    s = str(n)
    for i in range(len(s)-1):
        if abs(int(s[i])-int(s[i+1])) > 1:
            return False
    return True

def slv(k):
    if k <= 9:
        return k
    lunlun = list(range(1, 10))
    q = deque(lunlun)

    while True:
        n = q.popleft()
        for i in (-1, 0, 1):
            d = n % 10
            if 0 <= d + i <= 9:
                l = n * 10 + d+i
                q.append(l)
                lunlun.append(l)
                if len(lunlun) == k:
                    return lunlun[-1]




def main():
    K = read_int()
    print(slv(K))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix

# strlist = "abcdefghijklmnopqrstuvwxyz"
k = int(input())

que = deque(range(1,10)) 
for _ in range(k):
    tmp = que.popleft()
    if tmp % 10 !=0:
        val = tmp*10 + (tmp%10) - 1
        que.append(val)
    val = tmp*10 + (tmp%10)
    que.append(val)
    if tmp%10 != 9:
        val = tmp*10 + (tmp%10) + 1
        que.append(val)

ans = tmp
print(ans)
# print("{:.10f}".format(ans))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
d = deque()
for i in range(1, 10):
  d.append(i)
cc = 0
while cc < k:
  num = d.popleft()
  if num%10 == 0:
    d.append(10*num)
    d.append(10*num + 1)
  elif num%10 == 9:
    d.append(10*num+8)
    d.append(10*num+9)
  else:
    d.append(10*num+num%10-1)
    d.append(10*num+num%10)
    d.append(10*num+num%10+1)
  cc += 1
print(num)

Submission status: Accepted

Solution code:
import queue

K = int(input())

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

for _ in range(K):
    now_lunlun = que_lunlun.get()
    
    first_digit = now_lunlun % 10
    if first_digit != 0:
        que_lunlun.put(now_lunlun*10 + first_digit-1)
    
    que_lunlun.put(now_lunlun*10 + first_digit)

    if first_digit != 9:
        que_lunlun.put(now_lunlun*10 + first_digit+1)
    
print(now_lunlun)

Submission status: Accepted

Solution code:
k=int(input())

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

for x in a:
    if k<=len(a):
        break
    
    if x%10!=0:
        a.append(10*x+(x%10)-1)
    a.append(10*x+(x%10))
    if x%10!=9:
        a.append(10*x+(x%10)+1)
        
print(a[k-1])

Submission status: Accepted

Solution code:
k = int(input())
from collections import deque
queue = deque(range(1,10)) # 1から10のベースとなるルンルン数
count = 0
 
while count < k: # K番目になるまで
  count += 1
  tmp = queue.popleft()
  tail = tmp % 10 # 末尾の数
  if tail!=0:
    queue.append(tmp*10+tail-1)  # 0以外の時、末尾の1つ前の数を末尾に追加
  queue.append(tmp*10+tail) # 末尾と同じ数を末尾に追加
  if tail!=9:
    queue.append(tmp*10+tail+1) # 9以外の時、末尾の次の数を末尾に追加
  
print(tmp) # K番目のルンルン数

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
K=int(input())

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

temp=[]
for _ in range(9):
    for item in cand:
        if int(str(item)[-1])!=0:
            temp.append(int(str(item)[-1])-1+item*10)
        temp.append(int(str(item)[-1])+item*10)
        if int(str(item)[-1])!=9:
            temp.append(int(str(item)[-1])+1+item*10)
    al+=cand
    cand=temp[:]
    al=list(set(al))
    al.sort()
al+=temp
al=list(set(al))
al.sort()
print(al[K-1])

Submission status: Accepted

Solution code:
import sys

K = int(input())

NLUNLUN = [[-1 for _ in range(11)] for _ in range(10)]
def num_lunlun(n, digit):
    if digit == 1:
        NLUNLUN[n][digit] = 1
        return NLUNLUN[n][digit]

    if digit == 2:
        if 0 < n < 9:
            NLUNLUN[n][digit] = 3
        else:
            NLUNLUN[n][digit] = 2
        return NLUNLUN[n][digit]

    n2 = 0
    if n - 1 >= 0:
        n2 += NLUNLUN[n-1][digit-1]
    n2 += NLUNLUN[n][digit-1]
    if n + 1 <= 9:
        n2 += NLUNLUN[n+1][digit-1]
    NLUNLUN[n][digit] = n2
    return NLUNLUN[n][digit]


if K < 10:
    print(K)
    sys.exit(0)

k = 0
for digit in range(1, 11):
    for n in range(10):
        tmp = num_lunlun(n, digit)
        if n > 0:
            if k + tmp >= K:
                ans = str(n)
                n2 = n
                for digit2 in range(digit-1, 1, -1):
                    if n2 - 1 >= 0:
                        tmp = NLUNLUN[n2 - 1][digit2]
                        if k + tmp >= K:
                            ans += str(n2 - 1)
                            n2 -= 1
                            continue
                        k += tmp

                    tmp = NLUNLUN[n2][digit2]
                    if k + tmp >= K:
                        ans += str(n2)
                        continue
                    k += tmp

                    if n2 + 1 <= 9:
                        tmp = NLUNLUN[n2 + 1][digit2]
                        if k + tmp >= K:
                            ans += str(n2 + 1)
                            n2 += 1
                            continue
                        k += tmp

                if ans[-1] == '0':
                    ans = int(ans + str(n2 + K - k - 1))
                else:
                    ans = int(ans + str(n2 + K - k - 2))
                print(ans)

                sys.exit(0)
            k += tmp

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(tmp*10+tail-1)
  queue.append(tmp*10+tail)
  if tail!=9:
    queue.append(tmp*10+tail+1)
  
print(tmp)

Submission status: Accepted

Solution code:
from collections import deque

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

for k in range(K):
  num = dq.popleft()

  if num%10 != 0:
    dq.append(10*num + (num % 10) -1)
  dq.append(10*num + (num%10))
  if num%10 != 9:
    dq.append(10*num + (num % 10) +1)
    
print(num)

Submission status: Accepted

Solution code:
def findnxt(x):
	i=len(x)-1
	if x[i]==9:
		while True:
			if i==0 :
				break
			if(x[i]<=x[i-1] and x[i]!=9):
				break
			i-=1
		if x[i]==9:
			x.insert(0,1)
			for j in range(1,len(x)):
				x[j]=0
		else:
			x[i]+=1
			i+=1
			while i<len(x):
				if x[i-1]:
					x[i]=x[i-1]-1
				else:
					x[i]=0
				i+=1
	else:
		while i:
			if x[i]<=x[i-1]:
				break
			i-=1
		x[i]+=1
		i+=1
		while i<len(x):
			if x[i-1]:
				x[i]=x[i-1]-1
			else:
				x[i]=0
			i+=1
	return x
	
x=[1]
k=int(input())
for l in range(2,k+1):
	x=findnxt(x)
for l in x:
	print(l,end='')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

K = int(input())
Q = collections.deque([i for i in range(1, 10)])
for _ in range(K):
  x = Q.popleft()
  r = x%10
  if r != 0: Q.append(x*10 + r - 1)
  Q.append(x*10 + r)
  if r != 9: Q.append(x*10 + r + 1)
print(x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    def gen():
        counter = 0
        q = deque(range(1, 10))
        while counter < 100001:
            n = q.popleft()
            yield n
            counter += 1
            t = n % 10
            if t > 0:
                q.append(n*10 + (t - 1))
            q.append(n*10 + t)
            if t < 9:
                q.append(n*10 + (t + 1))
    g = gen()
    for _ in range(ii() - 1):
        next(g)
    print(next(g))

main()

Submission status: Accepted

Solution code:
k=int(input())

a=[]
for i in range(1,10):
    a.append(i)
while True:
    if k<=len(a):
        print(a[k-1])
        break
    
    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:
from collections import deque
que=deque([1,2,3,4,5,6,7,8,9])
k=int(input())
for i in range(k-1):
  q=que.popleft()
  #print("q",q)
  m=q%10
  #print("m",m,"que",que)
  if m==0:
    que.append(q*10)
    que.append(q*10+1)
  elif m==9:
    que.append(q*10+8)
    que.append(q*10+9)
  else:
    que.append(q*10+m-1)
    que.append(q*10+m)
    que.append(q*10+m+1)
print(que[0])

Submission status: Accepted

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

Q = deque(range(1, 10)) #るんるん数を格納するキュー
# Q: 1 2 3 4 5 6 7 8 9

for i in range(k):
  x = Q.popleft()
  #x = 1 <--  Q: 2 3 4 5 6 7 8 9
  last_digit = x % 10 # 1 一番目の桁の値
  z = 10*x + last_digit #11

  if last_digit != 0:
    Q.append(z-1)
    # Q: 2 3 4 5 6 7 8 9 <--10
  Q.append(z)
  # Q: 2 3 4 5 6 7 8 9 10 <--11
  if last_digit != 9:
    Q.append(z+1)
    # Q: 2 3 4 5 6 7 8 9 10 11 <--12
print(x)

Submission status: Accepted

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

Q = deque(range(1, 10)) #るんるん数を格納するキュー
# Q: 1 2 3 4 5 6 7 8 9

for i in range(k):
  x = Q.popleft()
  #x = 1 <--  Q: 2 3 4 5 6 7 8 9
  last_digit = x % 10 # 1 一番目の桁の値
  if last_digit == 0:
        Q.append(10*x + 0)
        Q.append(10*x + 1)

  elif last_digit == 9:
        Q.append(10*x + 8)
        Q.append(10*x + 9)

  else: # 1<=last_digit <=8
        Q.append(10*x + last_digit - 1)
        Q.append(10*x + last_digit)
        Q.append(10*x + last_digit + 1)
print(x)

Submission status: Accepted

Solution code:
import collections

k = int(input())
L = collections.deque(range(1,10))
for i in range(k):
    x = L.popleft()
    if x%10 != 0:
        L.append((10*x)+(x%10)-1)
    L.append(10*x+x%10)
    if x%10 != 9:
        L.append(10*x+x%10+1)

print(x)

Submission status: Accepted

Solution code:
K = int(input())

if K < 11:
    print(K)
    exit()
K -=10
ll_num = [0,1]
while(K>0):
    ll_num[0]+=1
    digit_num = len(ll_num)
    for digit in range(digit_num):
        if ll_num[digit] ==10:
            if digit == digit_num-1:
                ll_num.append(0)
                digit_num +=1
            ll_num[digit+1] +=1
            if ll_num[digit+1] ==10:
                ll_num[digit] = 0
            for i in reversed(range(0,digit+1)):
                ll_num[i] = ll_num[i+1]-1
                if ll_num[i] < 0:
                    ll_num[i] = 0

    for digit in range(digit_num-1):
        if ll_num[digit]>ll_num[digit+1]+1:
            ll_num[digit+1] +=1
            for i in reversed(range(0,digit+1)):
                ll_num[i] = ll_num[i+1]-1
                if ll_num[i] < 0:
                    ll_num[i] = 0
    K -=1
result_str = ""
for num in range(len(ll_num)):
     result_str = str(ll_num[num]) + result_str
print(int(result_str))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

dp = [[0] * 10 for _ in range(11)]
for i in range(10):
    dp[0][i] = 1
for i in range(1, 11):
    for j in range(0, 10):
        dp[i][j] += dp[i-1][j]
        if j-1 >= 0:
            dp[i][j] += dp[i-1][j-1]
        if j+1 < 10:
            dp[i][j] += dp[i-1][j+1]
    
k = int(input())
ans = ""
ret = 0
lv = 0
for i in range(11):
    if k > sum(dp[i][1:]):
        k -= sum(dp[i][1:])
    else:
        lv = i
        break

lft = 1; rgt = 10 
for l in range(lv, -1, -1):
    for i in range(lft, rgt):
        item = dp[l][i]
        if k > item:
            k -= item
        else:
            lft = max(i - 1, 0)
            rgt = i + 2
            ans += str(i)
            break
print(ans)

Submission status: Accepted

Solution code:
K=int(input())
a=list(range(1,10))
if K<=9:
  print(a[K-1])
  quit()
count=9
i=0
while count<K:
  b=a[i]%10
  if b!=0:
    a.append(a[i]*10+b-1)
    count+=1
  a.append(a[i]*10+b)
  count+=1
  if b!=9:
    a.append(a[i]*10+b+1)
    count+=1
  i+=1
print(a[K-1])

Submission status: Accepted

Solution code:
K=int(input())
a=list(range(1,10))
if K<=9:
  print(a[K-1])
  quit()
count=9
i=0
while count<K+1:
  b=a[i]%10
  if b!=0:
    a.append(a[i]*10+b-1)
    count+=1
  a.append(a[i]*10+b)
  count+=1
  if b!=9:
    a.append(a[i]*10+b+1)
    count+=1
  i+=1
print(a[K-1])

Submission status: Accepted

Solution code:
k=int(input())
L=[1,2,3,4,5,6,7,8,9]
temp1=[L[:]]
temp2=[]

def dfs(n):
	if n>3234566667:
		return
	temp2=[]
	for i in range(3):
		m=int(str(n)[-1])
		if 0<=m+i-1<=9:
			nn=n*10+m+i-1
			temp2.append(nn)
			L.append(nn)
	if temp2:
		temp1.append(temp2)
	for n in temp1[-1]:
		dfs(n)

for i in range(9):
	dfs(i+1)

LS=sorted(L)
print(LS[k-1])