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:
k=int(input())
# num から始まる digit 桁（num 含む）のルンルン数の個数を返す
def count(digit,num):
    if digit==1:
        return 1
    c=0
    if num!=0:
        c+=count(digit-1,num-1)
    c+=count(digit-1,num)
    if num!=9:
        c+=count(digit-1,num+1)
    return c

# num から始まる digit 桁（num 含む）のルンルン数の中で i 番目の ans を返す
def answer(digit,num,i,ans):
    # print(digit,num,i,ans)
    if digit==2:
        add=(i+num-2)
        if num==0:
            add+=1
        return ans*10+add
    if num!=0:
        c=count(digit-1,num-1)
        if c>=i:
            return answer(digit-1,num-1,i,ans*10+num-1)
        i-=c
    c=count(digit-1,num)
    if c>=i:
        return answer(digit-1,num,i,ans*10+num)
    i-=c
    if num!=9:
        c=count(digit-1,num+1)
        if c>=i:
            return answer(digit-1,num+1,i,ans*10+num+1)
    return 0

size=9
num=1
digit=2
while True:
    s=count(digit,num)
    if s+size>=k:
        break
    size+=s
    num+=1
    if num==10:
        num=1
        digit+=1
ans=0
if k<=9:
    ans=k
else:
    ans=answer(digit,num,k-size,num)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


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

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

print(x)

Submission status: Accepted

Solution code:
#!/usr/bin/python3


def calcComb(n, dnum, dc):
    return sum(dc[n][dnum - 1])

def lunNum(n, dnum, remain, dc):
    sl = len(str(n))
    if dnum == sl:
        return n

    #sl < dnum
    rd = dnum - sl
    ld = n % 10
    
    if ld > 0:
        c = calcComb(ld - 1, dnum - sl, dc)
        if remain > c:
            remain -= c
        else:
            return lunNum(n * 10 +  ld - 1, dnum, remain, dc)
        
    c = calcComb(ld, dnum - sl, dc)
    if remain > c:
        remain -= c
    else:
        return lunNum(n * 10 + ld, dnum, remain, dc)

    if ld == 9:
        print("Oops!!")
        return -1

    return lunNum(n * 10 + ld + 1, dnum, remain, dc)

k = int(input())

dc = {}

for i in range(10):
    l = [ 1 if i == j else 0 for j in range(10) ]
    dc[i] = [l]

#print(dc)
    
dnum = 1
s = 0
ps = 0
ck = 0
while True:
    out = False
    for key in range(1, 10):
        ck = key
        l = dc[key][dnum - 1]
        ps = s        
        s += sum(l)
        if k <= s:
            out = True
            break

    if out:
        break
    
    #calc next digit
    for key in dc:
        l = dc[key][dnum - 1]
        nl = [0 for i in range(10)]

        for i in range(10):
            nl[i] += l[i]
            if i > 0:
                nl[i] += l[i - 1]
            if i < 9:
                nl[i] += l[i + 1]
        dc[key].append(nl)

    dnum += 1


remain = k - ps
#print(dnum, remain, ck)
print(lunNum(ck, dnum, remain, dc))

Submission status: Accepted

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


def bfs():
  count=0
  d=deque()
  for i in range(1,10):
    d.append(str(i))
    count+=1
    if count==K:
      print(i)
      return
  while count<K:
    S=d.popleft()
    if S[-1]=="9":
      for i in [8,9]:
        d.append(S+str(i))
        count+=1
        if count==K:
          print(S+str(i))
          break
    elif S[-1]=="0":
      for i in [0,1]:
        d.append(S+str(i))
        count+=1
        if count==K:
          print(S+str(i))
          break
    else:
      s=int(S[-1])
      for i in [s-1,s,s+1]:
        d.append(S+str(i))
        count+=1
        if count==K:
          print(S+str(i))
          break
bfs()

Submission status: Accepted

Solution code:
import math
import queue

def readInt():
	return int(input())

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

def readChars():
	return input().split()


q = queue.Queue()

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

n = readInt()

for i in range(1,100001):
	a = str(q.get())
	b = int(a[-1])
	if b!=0:
		q.put(int(a+str(b-1)))
	q.put(int(a+str(b)))
	if b!=9:
		q.put(int(a+str(b+1)))	
	if i==n:
		print(int(a))
		break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
import sys

k = int(input())

q = deque([i for i in range(1, 10)])
if k <= 9:
    print(q[k-1])
    sys.exit()

cnt = 0
while True:
    if cnt == k:
        print(x)
        break
    x = q.popleft()
    m = x % 10
    if m == 0:
        q.extend([10*x + m, 10*x + (m+1)])
    elif m == 9:
        q.extend([10*x + (m-1), 10*x + m])
    else:
        q.extend([10*x + (m-1), 10*x + m, 10*x + (m+1)])
    cnt += 1

Submission status: Accepted

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

INF = float('inf')


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

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

    counter = 0
    while True:
        counter += 1
        x = q.popleft()
        amari = x % 10
        if counter != K:
            if amari > 0:
                q.append(x * 10 + (amari - 1))
            q.append(x * 10 + amari)
            if amari < 9:
                q.append(x * 10 + (amari + 1))
        else:
            print(x)
            exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k=int(input())
q=[i for i in range(1,10)]
ans=0
c=0
for i in range(k):
    ans=q.pop(0)
    p=10*ans+int(str(ans)[-1])
    if(p%10!=0):q.append(p-1)
    q.append(p)
    if(p%10!=9):q.append(p+1)
    if(i+len(q)>k):break
    c+=1
for i in range(k-c-1):
    ans=q.pop(0)

print(ans)

Submission status: Accepted

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

INF = float('inf')


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

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

    counter = 0
    while True:
        counter += 1
        x = q.popleft()
        amari = x % 10
        if counter != K:
            if amari == 0:
                q.append(x * 10 + amari)
                q.append(x * 10 + (amari + 1))
            elif amari == 9:
                q.append(x * 10 + (amari - 1))
                q.append(x * 10 + amari)
            else:
                q.append(x * 10 + (amari - 1))
                q.append(x * 10 + amari)
                q.append(x * 10 + (amari + 1))
        else:
            print(x)
            exit()

Submission status: Accepted

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

x = int(input())

def Add(count, list, change, check):
    # 出力
    if count <= 0:
        print(''.join(map(str, list)))
        return

    # 桁数の増加
    if all(item == 9 for item in list):
        list = [0 for y in range(0, len(list) + 1)]
        list[0] = 1
        Add(count - 1, list, len(list) - 1, max(0, len(list) - 2))
        return

    # 加算できる桁に加算
    if list[change] <= list[check] and list[change] < 9:
        list[change] += 1
        Clean(list, change + 1)
        Add(count - 1, list, len(list) - 1, max(0, len(list) - 2))
        return

    # 一つ上の桁を確認
    else:
        Add(count, list, change - 1, max(0, change - 2))
        return

# changeより下の桁を最小にする
def Clean(list, change):
    if change >= len(list):
        return
    for x in range(change, len(list)):
        list[x] = max(0, list[max(0, x - 1)] - 1)


Add(x, [0], 0, 0)

Submission status: Accepted

Solution code:
k = int(input())
dp = [[] for _ in range(k)]
dp[0] = [1,2,3,4,5,6,7,8,9]

if k <= 9:
    print(k)
else:
    total = 0
    i = 0
    while total + len(dp[i]) < k:
        total += len(dp[i])
        for j in dp[i]:
            x = j%10
            if x == 0:
                dp[i+1].append(j*10)
                dp[i+1].append(j*10+1)
            elif x == 9:
                dp[i+1].append(j*10+8)
                dp[i+1].append(j*10+9)
            else:
                dp[i+1].append(j*10+x-1)
                dp[i+1].append(j*10+x)
                dp[i+1].append(j*10+x+1)
        i += 1
    print(dp[i][k-total-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

'''
100000
99990
90000
'''

K = int(input())
# K = 100000 - K

# c = list(str(3234566667))
# c = [int(i) for i in c][::-1]
c = 1

for i in range(K -1):
    str_c = list(str(c))
    str_c = [int(i) for i in str_c][::-1]

    keta = len(str_c)
    # print(c)
    # print(str_c)

    if set(str_c) == set([9]):
        c = c + 1
        continue

    for ket in range(keta):
        # 次の桁を見る
        if ket == keta - 1:
            str_c[ket] += 1

            for j in range(ket):
                # print(str_c)
                if str_c[ket - j] == 0:
                    str_c[ket - j - 1] = 0
                else:
                    str_c[ket - j - 1] = str_c[ket - j] - 1

            str_c = [str(i) for i in str_c][::-1]
            c = int(''.join(str_c))
            break

        if str_c[ket] == str_c[ket + 1] + 1:
            continue

        # 大きくできるところがあれば増やす
        if abs(str_c[ket] - str_c[ket + 1]) <= 1:
            if str_c[ket] < 9:
                str_c[ket] += 1
                for j in range(ket):
                    if str_c[ket - j] == 0:
                        str_c[ket - j - 1] = 0
                    else:
                        str_c[ket - j - 1] = str_c[ket - j] - 1
                str_c = [str(i) for i in str_c][::-1]
                c = int(''.join(str_c))
                break


print(c)

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

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

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

    count = 9

    for i in range(2,11):
        for j in pre:
            for k in range(-1,2):
                d = j % 10 + k
                if (d < 0) | (d > 9):
                    continue
                temp = j * 10 + d
                now.append(temp)
                count += 1
                if count == K:
                    print(temp)
                    sys.exit()
        pre = now



main()

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

q = deque(range(1, 10))

for i in range(k):
    t = q.popleft()

    if t % 10 != 0:
        q.append(10 * t + t % 10 - 1)

    q.append(10 * t + t % 10)

    if t % 10 != 9:
        q.append(10 * t + t % 10 + 1)
 
print(t)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
K = int(input())
LEN = 32345666
#S = input()[:-1]
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
def enqueue(Q,x,tail):#末尾にクラスPの要素xを加える。ぐるっと回った場合
    Q[tail] = x       #以前dequeueで取り出したものが書き換えられる。
    if tail+1 == LEN: #headは先頭のindex,tailは末尾のindex+1
        tail = 0
    else:
        tail += 1
    return tail
def dequeue(Q,head):
    x = Q[head]
    if head+1 == LEN:
        head = 0
    else:
        head += 1
    return x,head
Q = [1,2,3,4,5,6,7,8,9]+[0]*(LEN-9)
head = 0
tail = 9

i = 0
while i < K:
    x,head = dequeue(Q,head)
    if x % 10 == 0:
        tail = enqueue(Q,10*x,tail)
        tail = enqueue(Q,10*x+1,tail)
    elif x % 10 == 9:
        tail = enqueue(Q,10*x+8,tail)
        tail = enqueue(Q,10*x+9,tail)
    else:
        y = x%10
        tail = enqueue(Q,10*x+y-1,tail)
        tail = enqueue(Q,10*x+y,tail)
        tail = enqueue(Q,10*x+y+1,tail)
    i += 1
print(x)

Submission status: Accepted

Solution code:
k = int(input())

a = list(range(1,10))

while True:
    if(k<=len(a)):
        print(a[k-1])
        exit()
    k-=len(a)
    old = a
    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 random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
#import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""

#import math
from collections import deque, defaultdict, Counter


def main():
    """
    N = int(input())
    Nr = math.sqrt(N)
    Nr = int(Nr)+1
    count = 0
    for i in range(2, Nr):

        if N % i == 0:
            M = N
            while M % i != 0:
                M = M // i

            if M < i:
                break
            else:
                ans = M % i
                if ans == 1:
                    count += 1
        else:
            ans = N % i
            if ans == 1:
                count += 1
    print(count+2)

    """
    K = int(input())
    count = 0
    q = deque()
    for i in range(1, 10):
        q.append(i)
    while q:
        num = q.popleft()
        count += 1
        if count == K:
            ans = num
            break
        mod10 = num % 10
        if mod10 != 0:
            q.append(10*num + mod10 - 1)
        q.append(10*num + mod10)
        if mod10 != 9:
            q.append(10*num + mod10 + 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    queue = deque()

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

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

    print(x)



main()

Submission status: Accepted

Solution code:
k=int(input())
a=[0,0,0,0,0,0,0,0,0,0]
keta=1
for i in range(k):
  unta=-1
  a[0]+=1
  for j in range(keta):
    if (j+1<keta and a[j]>a[j+1]+1) or a[j]>=10:
      a[j+1]+=1
      unta=j
  if unta>-1:
    if unta==keta-1:
      keta+=1
    for j in range(unta+1):
      a[unta-j]=max(a[unta-j+1]-1,0)

ans=0
for i in range(10):
  ans+=a[i]*(10**i)
print(str(ans))

Submission status: Accepted

Solution code:
K=int(input())
if K<10:
  print(K);exit()
def dfs(v,n):
  u=[]
  for x in v:
    for d in [-1,0,1]:
      if(0<=x%10+d<=9):
        u.append(x*10+x%10+d)
  if(n+len(u)>=K):
    u.sort()
    print(u[K-n-1])
  else:
    dfs(u,n+len(u))
dfs(range(1,10),9);

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

if N <= 12:
    print(N)
else:
    str_ans = "12"
    counter = 12
    while counter < N:
        len_ans = len(str_ans)
        low_nine_num = 0
        for i in range(len_ans):
            if str_ans[len_ans - i - 1] == "9":
                low_nine_num += 1
            else:
                break
        if low_nine_num == len_ans:
            str_ans = "1" + "0" * len_ans
        else:
            chenged_top_num = -1
            low_digit_num = -1
            if low_nine_num == len_ans - 1:
                chenged_top_num = int(str_ans[len_ans - low_nine_num - 1])
                low_digit_num = len_ans - 1
            else:
                for i in range(len_ans):
                    if i == len_ans - 1 :
                        if chenged_top_num == -1:
                            chenged_top_num = int(str_ans[0])
                            low_digit_num = len_ans - 1
                    elif str_ans[-1 * (i + 1)] == "9":
                        continue
                    else:
                        compare_high_num = int(str_ans[-1 * (i + 2)])
                        compare_low_num = int(str_ans[-1 * (i + 1)])
                        if compare_high_num - compare_low_num != 0 and compare_high_num - compare_low_num != 1:
                            chenged_top_num = compare_high_num
                            low_digit_num = i + 1
    #                         print("A", str_ans, compare_high_num, low_digit_num)
                        else:
                            chenged_top_num = compare_low_num
                            low_digit_num = i
    #                         print("B", str_ans, compare_high_num, low_digit_num)
                            break

                            
            temp_str_ans = str_ans[:len_ans - low_digit_num - 1] # not chenged
            temp_str_ans += str(chenged_top_num + 1)
            for i in range(low_digit_num):
                temp_str_ans += str(max(chenged_top_num - i, 0))
            str_ans = temp_str_ans
        
        counter += 1
#         print(counter, str_ans, low_nine_num, low_digit_num)
    
    print(int(str_ans))

Submission status: Accepted

Solution code:
from collections import deque
from copy import copy,deepcopy
from itertools import permutations,combinations
from pprint import pprint

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

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)

k = int(input())

def bfs(k):
    ls = []
    q = deque()
    for i in range(1,10):
        q.append(str(i))
    while q:
        tmp = q.popleft()
        ls.append(tmp)
        if len(ls)==k:
            break
        n = int(tmp[-1])
        if n==0:
            tmp_new = tmp + "0"
            q.append(tmp_new)
            tmp_new = tmp + "1"
            q.append(tmp_new)
        elif 0<n<9:
            tmp_new = tmp + str(n-1)
            q.append(tmp_new)
            tmp_new = tmp + str(n)
            q.append(tmp_new)
            tmp_new = tmp + str(n+1)
            q.append(tmp_new)
        elif n==9:
            tmp_new = tmp + "8"
            q.append(tmp_new)
            tmp_new = tmp + "9"
            q.append(tmp_new)
        else:
            print("Error")
    return ls

ls = bfs(k)
# print(ls)
print(ls[k-1])

Submission status: Accepted

Solution code:
import queue

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

    q = queue.Queue()
    for i in range(9):
        q.put(i+1)

    count = 0
    while True:
        count = count+1
        a = q.get()

        if count == K:
            break

        tail = int(str(a)[-1])
        for i in range(10):
            if abs(tail-i) > 1:
                continue
            q.put(int(str(a)+str(i)))

    print(a)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k=int(input())
A=[1,2,3,4,5,6,7,8,9]
head=0
tail=len(A)
for z in range(10):
    for i in range(head,tail):
        now=A[i]%10
        ad=A[i]*10
        if now!=0:
            A.append(ad+now-1)
        if now!=9:
            A.append(ad+now+1)
        A.append(ad+now)
    head=tail
    tail=len(A)
A.sort()
print(A[k-1])

Submission status: Accepted

Solution code:
from collections import deque

def resolve():
    K = int(input())
    q = deque(range(1, 10))

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

INF = float('inf')


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

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

    counter = 0
    while True:
        counter += 1
        x = q.popleft()
        if counter != K:
            if x % 10 == 0:
                q.append(x * 10)
                q.append(x * 10 + 1)
            elif x % 10 == 9:
                q.append(x * 10 + 8)
                q.append(x * 10 + 9)
            else:
                q.append(x * 10 + (x % 10 - 1))
                q.append(x * 10 + (x % 10))
                q.append(x * 10 + (x % 10 + 1))
        else:
            print(x)
            exit()

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
q = deque(range(1, 10))
for _ in range(K - 1):
    x = q.popleft()
    y = x % 10
    if y != 0:
        q.append(10 * x + y - 1)
    q.append(10 * x + y)
    if y != 9:
        q.append(10 * x + y + 1)
ans = q.popleft()
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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

#count = 0
#while count <= K:
for _ in range(K):
    n = q.popleft()
    #count += 1
    if n % 10 != 0:
        q.append(n*10 + n % 10 - 1)
    q.append(n*10 + n % 10)
    if n % 10 != 9:
        q.append(n*10 + n % 10 + 1)
print(n)

Submission status: Accepted

Solution code:
k=int(input())
lunlun=[None for _ in range(100)]
lunlun[0]=(1,2,3,4,5,6,7,8,9)
for i in range(0,10):
  tmp=[]
  for j in lunlun[i]:
    s=j%10
    if s==0:
      tmp+=j*10+0,
      tmp+=j*10+1,
    elif s==9:
      tmp+=j*10+8,
      tmp+=j*10+9,
    else:
      tmp+=j*10+s-1,
      tmp+=j*10+s,
      tmp+=j*10+s+1,
  lunlun[i+1]=tuple(tmp)
L=[]
for i in range(0,10):
  for j in lunlun[i]:
    L+=j,
print(L[k-1])

Submission status: Accepted

Solution code:
from collections import deque


def calc_next_ones_places(last_ones_place):
    """次の Lunlun数 の一の位の数を返す"""
    if last_ones_place == 0:
        return [last_ones_place, last_ones_place+1]
    elif last_ones_place == 9:
        return [last_ones_place-1, last_ones_place]
    else:
        return [last_ones_place-1, last_ones_place, last_ones_place+1]


def calc_k_th_lunlun_num(k):
    """
    Kが10以上の時、K番目のLunlun数を計算する
    """
    lunlun_num_queue = deque()

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

    iterate_num = 9
    while True:
        last_lunlun_num = lunlun_num_queue.popleft()
        last_ones_place = str(last_lunlun_num)[-1]
        next_ones_places_list = calc_next_ones_places(int(last_ones_place))
        for next_ones_place in next_ones_places_list:
            lunlun_num = 10*last_lunlun_num + next_ones_place
            lunlun_num_queue.append(lunlun_num)

            iterate_num += 1
            if iterate_num == k:
                return lunlun_num


def main():
    K = int(input())
    if K <= 9:
        print(K)
    else:
        k_th_lunlun_num = calc_k_th_lunlun_num(K)
        print(k_th_lunlun_num)


main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
k = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
que = deque([i for i in range(1, 10)])
for _ in range(k - 1):
    x = que.popleft()
    if x % 10 != 0:
        que.append(10 * x + x % 10 - 1)
    que.append(10 * x + x % 10)
    if x % 10 != 9:
        que.append(10 * x + x % 10 + 1)
ans = que.popleft()
print(ans)

Submission status: Accepted

Solution code:
K = int(input())

dig = 10
# dp[i][j] := jで始まるi桁のルンルン数の数
dp = [[0 for _ in range(10)] for _ in range(dig + 1)]

# 1桁
for j in range(0, 10):
    dp[1][j] = 1 # jで始まる1桁のルンルン数の数

# 2〜3桁
for i in range(2, dig + 1): # 2〜3桁
    dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
    for j in range(1, 9):
        # jで始まるi桁のルンルン数の数 = j-1, j, またはj+1で始まるi-1桁のルンルン数の数
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1]
    dp[i][9] = dp[i - 1][8] + dp[i - 1][9]

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

ac = 0
for i in range(1, dig + 1):
    for j in range(1, 10):
        ac += dp[i][j]
        if ac >= K:
            ans = j * (10 ** (i - 1))
            break
    else:
        continue
    break

# MSBがjであるi桁の数字
rem = K - ac + dp[i][j]
while i > 1:
    if j == 0: # 次の桁は0か1
        jlist = [0, 1]
    elif j == 9: # 次の桁は8か9
        jlist = [8, 9]
    else:  # 次の桁はj-1かjかj+1
        jlist = [j - 1, j, j + 1]

    for j in jlist:
        if dp[i - 1][j] < rem:
            rem -= dp[i - 1][j]
        else:
            break
    i -= 1
    ans += j * 10 ** (i - 1)

print(ans)

Submission status: Accepted

Solution code:
K = int(input())
L = [[1,2,3,4,5,6,7,8,9]]
M = 9 #(M+1)桁まで考える

for i in range(M):
    X = []
    for n in L[-1]:
        t = n % 10
        if t == 0:
            X.append(n * 10 + t)
            X.append(n * 10 + t + 1)
        elif t == 9:
            X.append(n * 10 + t - 1)
            X.append(n * 10 + t)
        else:
            X.append(n * 10 + t- 1)
            X.append(n * 10 + t)
            X.append(n * 10 + t + 1)
    L.append(X)

L2 = []
for i in range(len(L)):
    L2 += L[i]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k=int(input())
ans=[i for i in range(1,10)]
def dfs(x):
    if x>=3234566667:
        return
    for i in range(max(0,x%10-1),min(10,x%10+2)):
        ans.append(10*x+i)
        dfs(10*x+i)
for i in range(1,10):
    dfs(i)
print(sorted(ans)[k-1])

Submission status: Accepted

Solution code:
# from sys import stdin
import sys
global cnt1


def bts(A, cnt, max):
    # print(A)
    if cnt == max:
        global cnt1
        cnt1 = cnt1+1
        if cnt1 == K:
            print(A)
            sys.exit()
        return
    cnt = cnt+1
    if A % 10 == 0:
        bts(A*10+(A % 10), cnt, max)
        bts(A*10+(A % 10)+1, cnt, max)
    elif A % 10 == 9:
        bts(A*10+(A % 10)-1, cnt, max)
        bts(A*10+(A % 10), cnt, max)
    else:
        bts(A*10+(A % 10)-1, cnt, max)
        bts(A*10+(A % 10), cnt, max)
        bts(A*10+(A % 10)+1, cnt, max)


K = int(input())
# print(K)
N = 9
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# global cnt1
cnt1 = 0
for k in range(1, 11):
    for i in range(len(A)):
        bts(A[i], 1, k)
# print(cnt1)

Submission status: Accepted

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

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

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

print(lunlun[k - 1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]
queue = deque(queue)
cnt = 0
while cnt < k:
    cnt += 1
    a = queue.popleft()
    hitoketa = a % 10
    kouho = [hitoketa - 1, hitoketa, hitoketa + 1]
    for b in kouho:
        if b >= 0 and b <= 9:
            queue.append(10 * a + b)
print(a)

Submission status: Accepted

Solution code:
import queue

k = int(input())
a = queue.Queue()
for i in range(9):
    a.put(i + 1)
for i in range(k):
    test = a.get()
    temp = test % 10
    if temp == 0:
        a.put(test * 10)
        a.put(test * 10 + 1)
    elif temp == 9:
        a.put(test * 10 + 8)
        a.put(test * 10 + 9)
    else:
        a.put(test * 10 + temp - 1)
        a.put(test * 10 + temp)
        a.put(test * 10 + temp + 1)
print(test)

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

d = [-1,0,1]

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

cnt = 0
while que:
    p = que.popleft()
    cnt += 1
    if cnt == k:
        print(p)
        break
    for i in d:
        if 0 <= int(str(p)[-1]) + i <= 9:
            que.append(int(str(p) + str(int(str(p)[-1]) + i)))

Submission status: Accepted

Solution code:
import queue

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

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

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

print(x)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

q = deque(range(1, 10))

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

print(x)

Submission status: Accepted

Solution code:
from queue import Queue

K=int(input())
q=Queue()
for h in range(1,10):
    q.put(h)
for i in range(K):
    x=q.get()
    d=x%10
    if x%10!=0:
        q.put(x*10+d-1)
    q.put(x*10+d)
    if x%10!=9:
        q.put(x*10+d+1)
print(x)

Submission status: Accepted

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

for i in ans:
    if len(ans) > K:
        break
    if i%10 == 0:
        ans.append(i*10+i%10)
        ans.append(i*10+i%10+1)
    elif i%10 == 9:
        ans.append(i*10+i%10-1)
        ans.append(i*10+i%10)
    else:
        ans.append(i*10+i%10-1)
        ans.append(i*10+i%10)
        ans.append(i*10+i%10+1)
    
print(ans[K-1])