Problem:


Score : 400 points

Problem Statement

A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:

In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1.

For example, 1234, 1, and 334 are lunlun numbers, while none of 31415, 119, or 13579 is.

You are given a positive integer K. Find the K-th smallest lunlun number.

Constraints

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer.

Sample Input 1

15

Sample Output 1

23

We will list the 15 smallest lunlun numbers in ascending order:

1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
21,
22,
23.

Thus, the answer is 23.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

13

Sample Output 3

21

Sample Input 4

100000

Sample Output 4

3234566667

Note that the answer may not fit into the 32-bit signed integer type.



Sample input:
15


Sample output:
23

Submission status: Accepted

Solution code:
import sys
import collections


def resolve(in_):
    k = int(next(in_))

    q = collections.deque(range(1, 10))
    lunlun = q.popleft()

    for _ in range(k - 1):
        a = lunlun * 10
        m = lunlun % 10
        if (b := m - 1) >= 0:
            q.append(a + b)
        q.append(a + m)
        if (b := m + 1) <= 9:
            q.append(a + b)
        lunlun = q.popleft()

    return lunlun


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

k = inp()

runrun = [["1","2","3","4","5","6","7","8","9"]]
runrun_int = []

for j in range(2,11):
    tmp = []
    for i in range(len(runrun[j - 2])):
        if runrun[j-2][i][j-2] == "0":
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2])))
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2]) + 1))
        elif runrun[j-2][i][j-2] in ["1","2","3","4","5","6","7","8"]:
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2]) - 1))
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2])))
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2]) + 1))
        elif runrun[j-2][i][j-2] == "9":
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2]) - 1))
            tmp.append(runrun[j-2][i] + str(int(runrun[j-2][i][j-2])))
    runrun.append(tmp)

ans = []
for i in range(len(runrun)):
    for j in range(len(runrun[i])):
        ans.append(int(runrun[i][j]))
ans.sort()

print(ans[k - 1])

Submission status: Accepted

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

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:
import queue

K = int(input())

Q = queue.Queue()

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

ans = 1
for k in range(K):
    ans = Q.get()
    ansm = ans % 10
    if ans%10 != 0:
        Q.put(10 * ans + ansm - 1)
    Q.put(10 * ans + ansm)
    if ans%10 != 9:
        Q.put(10 * ans + ansm + 1)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


lun = [[str(i)] for i in range(10)] + [[]]
olun =[[str(i)] for i in range(10)] + [[]]

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

while True:
    for i in range(0,10):
        lun[i] = list(map(lambda x: str(i) + x, (olun[i-1]+olun[i]+olun[i+1])))
        if i>= 1: ans += lun[i]

    if len(ans) >= 10**5 + 5: break
    olun = copy.deepcopy(lun)

k = int(input())
print(ans[k-1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
cnt = 9
q = deque([])
for i in range(1,10):
    q.append(i)
ans = 0

if k < 10:
    print(k)
else:
    while cnt != k:
        n = q.popleft()
        if n%10 == 0:
            tmp = n*10
            q.append(n*10)
            cnt += 1
            if cnt == k:
                print(tmp)
                break
            q.append(1+tmp)
            cnt += 1
            if cnt == k:
                print(tmp+1)
                break
        elif n%10 == 9:
            tmp = n*10
            q.append(tmp+8)
            cnt+=1
            if cnt == k:
                print(tmp+8)
                break
            q.append(tmp+9)
            cnt += 1
            if cnt == k:
                print(tmp+9)
                break
        else:
            tmp = n%10
            q.append(tmp-1+(n*10))
            cnt += 1
            if cnt ==k:
                print(tmp-1+(n*10))
                break
            q.append(tmp+(n*10))
            cnt +=1
            if cnt == k:
                print(tmp+(n*10))
                break
            q.append(tmp+1+(n*10))
            cnt += 1
            if cnt == k:
                print(tmp+1+(n*10))
                break

Submission status: Accepted

Solution code:
k = int(input())

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

while True:
    if k <= len(RunRun):
        print(RunRun[k-1])
        exit()
        
    k -= len(RunRun)
    
    now = []
    now, RunRun = RunRun, now

    for r in now:
        for i in range(-1, 2):
            tmp = r % 10 + i
            if tmp < 0 or 9 < tmp: continue
            tmp = (r * 10) + tmp
            RunRun.append(tmp)
        #print(RunRun)

Submission status: Accepted

Solution code:
K=int(input())

S=[str(_) for _ in range(10)]
ans=S[1:]
S_=[]
for i in range(10):
    for s in S:
        if abs(int(s[0])-i)<=1:
            S_.append(str(i)+s)
            if i!=0:
                ans.append(str(i)+s)
            
for _ in range(9):
#     print(_,'=========')
    S=S_.copy()
    S_=[]
    # print(S)
    S_dict={}

    for i in range(10):
        S_dict[i]=[]

    s_zero=0
    for i in range(10):
        for s in S:
            if abs(int(s[0])-i)<=1:
                S_.append(str(i)+s)
                if i!=0:
                    ans.append(str(i)+s)
                    
    if len(ans)>K+10:
        break
                                
print(ans[K-1])

Submission status: Accepted

Solution code:
import queue

def main():
    k = int(input())
    q = queue.Queue()
    for i in range(1, 10):
        q.put(str(i))
    ans = ""
    for i in range(1, k+1):
        ans = q.get()
        if i < k:
            p = int(ans[-1])
            if p == 0:
                q.put(ans + "0")
                q.put(ans + "1")
            elif p == 9:
                q.put(ans + "8")
                q.put(ans + "9")
            else:
                for v in range(p-1, p+2):
                    q.put(ans + str(v))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

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

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
q = deque(range(1, 10))
for _ in range(n - 1):
    x = q.popleft()
    r = x % 10
    y = 10 * x
    if r == 0:
        q.extend([y, y+1])
    elif r == 9:
        q.extend([y+8, y+9])
    else:
        q.extend([y+r-1, y+r, y+r+1])
print(q.popleft())

Submission status: Accepted

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

# 23から232(A),233(B),234(C)が作れる
# 20からは200(B),201(C)しか作れない
# 29からは298(A),299(B)しか作れない

queue = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
for i in range(k):
    x = queue.popleft()
    #print(x)
# (A)の場合
    if x % 10 != 0:
        queue.append(10 * x + (x % 10) - 1)
# (B)の場合
    queue.append(10 * x + x % 10)
# (C)の場合
    if x % 10 != 9:
        queue.append(10 * x + x % 10 + 1)

print(x)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import queue
K = int(input())
q = queue.Queue()

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

a = 0
while count < K:
  
  a = q.get()
  fp = int(str(a)[-1])
  if fp == 0:
    q.put(a*10)
    q.put(a*10 + 1)
  elif fp == 9:
    q.put(a*10 + 8)
    q.put(a*10 + 9)
  else:
    q.put(a*10 + fp - 1)
    q.put(a*10 + fp)
    q.put(a*10 + fp + 1)
  count += 1

print(a)

Submission status: Accepted

Solution code:
K = int(input())

queue = list(range(1,10))
counter = 0
while counter != K - 1:
    num = queue[counter]
    ichi = num % 10
    num *= 10
    if ichi != 0:
        queue.append(num + ichi - 1)
    queue.append(num + ichi)
    if ichi != 9:
        queue.append(num + ichi + 1)
    counter += 1
print(queue[counter])

Submission status: Accepted

Solution code:
def main():
    k = int(input())
    if k<10:
        print(k)
        return
    que = [i for i in range(1,10)]
    cnt = 0
    while True:
        q = que.pop(0)
        cnt += 1
        if cnt==k:
            print(q)
            return
        if q%10==0:
            que.append(q*10)
            que.append(q*10+1)
        elif q%10==9:
            que.append(q*10+9-1)
            que.append(q*10+9)
        else:
            que.append(q*10+q%10-1)
            que.append(q*10+q%10)
            que.append(q*10+q%10+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

count = 0
while queue:
    number = queue.pop()
    count += 1

    if count == K:
        print(number)
        break

    last_number = int(str(number)[-1])
    add_center = number * 10 + last_number

    if last_number > 0:
        queue.appendleft(add_center - 1)

    queue.appendleft(add_center)

    if last_number < 9:
        queue.appendleft(add_center + 1)

Submission status: Accepted

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

queue = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
for i in range(k):
    x = queue.popleft()
    if x % 10 != 0:
        queue.append(10 * x + (x % 10) - 1)
    queue.append(10 * x + x % 10)
    if x % 10 != 9:
        queue.append(10 * x + x % 10 + 1)
#print(queue)
print(x)

Submission status: Accepted

Solution code:
import collections

def main():
    k = int(input())
    Q = collections.deque([int(i) for i in range(1, 10)])
    chk = False
    for i in range(k):
        x = Q.popleft()
        if i + len(Q) > k:
            chk = True
        if chk:
            continue
        else:
            if x%10:
                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)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

k = int(input())
Q = collections.deque([int(i) for i in range(1, 10)])
chk = False
for i in range(k):
    x = Q.popleft()
    if i + len(Q) > k:
        chk = True
    if chk:
        continue
    else:
        if x%10:
            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:
import collections

k = int(input())
Q = collections.deque([int(i) for i in range(1, 10)])
for _ in range(k):
    x = Q.popleft()
    if x%10:
        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 queue import deque
k = int(input())
que = deque(range(1,10))

for _ in range(k):
    x = que.popleft()
    if not x % 10 == 0:
        # 123: 10*123 + 123 % 10 = 1233
        que.append(10*x+(x%10)-1)
    que.append(10*x+(x%10))
    if not x %10 == 9:
        que.append(10*x+(x%10)+1)
print(x)

Submission status: Accepted

Solution code:
k = int(input())
cur = [[1]*10 for i in range(11)]
if k <= 9:
  print(k)
  exit()
c = 9
i = 0
while c < k:
  i += 1
  for j in range(10):
    cur[i][j] = cur[i-1][j]
    if j != 0:
      cur[i][j] += cur[i-1][j-1]
    if j != 9:
      cur[i][j] += cur[i-1][j+1]
  if c+sum(cur[i][1:]) >= k:
    break
  else:
    c += sum(cur[i][1:])
ans = ''
for j in range(i,-1,-1):
  for l in range(10):
    if j == i and l == 0:
      continue
    if j != i and abs(l-int(ans[-1])) > 1:
      continue
    if c + cur[j][l] >= k:
      ans += str(l)
      break
    else:
      c += cur[j][l]
print(ans)

Submission status: Accepted

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

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

nums.sort()
print(nums[k-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
import heapq
k = int(input())
s =[1,2,3,4,5,6,7,8,9,10]
heapq.heapify(s)
li = set()
for val in range(1,2**11):
    v = int(str(bin(val)[2:]))
    li.add(v)
while len(li)<=301000:
    val = heapq.heappop(s)
    li.add(val)
    if str(val)[-1]=='0':
        heapq.heappush(s,10*val)
        heapq.heappush(s,10*val + 1)
    elif str(val)[-1]=='9':
        heapq.heappush(s,10*val + 8)
        heapq.heappush(s,10*val + 9)
    else:
        heapq.heappush(s,10*val + int(str(val)[-1]))
        heapq.heappush(s,10*val + int(str(val)[-1])+1)
        heapq.heappush(s,10*val + int(str(val)[-1])-1)
L = list(li)
L.sort()
print(L[k-1])

Submission status: Accepted

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

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

cnt = 0
while True:
    n = l.popleft()
    cnt +=1
    if cnt ==K:
        print(n)
        exit()

    if n%10 != 0:
        l.append(10*n+n%10-1)

    l.append(10*n+n%10)

    if n%10 != 9:
        l.append(10*n+n%10+1)

Submission status: Accepted

Solution code:

from collections import deque

K = int(input())
q = deque(list(range(1, 10)))
cnt = 0
ans = 0
while True:
    u = q.popleft()
    cnt += 1
    if cnt == K:
        ans = u
        break

    ll = u % 10
    for i in range(max(0, ll - 1), min(9, ll + 1) + 1):
        q.append(u * 10 + i)

print(ans)

Submission status: Accepted

Solution code:
def skip_num(num_digits:list, compare_digit):
    compare_upper_digit = num_digits[compare_digit]
    compare_lower_digit = num_digits[compare_digit + 1]
    if compare_upper_digit > compare_lower_digit:
        num_digits[compare_digit + 1] = compare_lower_digit + 1
        if compare_digit + 2 > len(num_digits):
            num_digits[compare_digit + 2:] = [0] * (len(num_digits) - compare_digit - 2)
    else: # compare_upper_digit < compare_lower_digit
        num_digits[compare_digit] = compare_upper_digit + 1
        num_digits[compare_digit + 1:] = [0] * (len(num_digits) - compare_digit - 1)
    
    return int("".join([str(i) for i in num_digits]))

K = int(input())

lunlun_count = 0
num = 0
while True:
    num += 1
    if num < 10:
        lunlun_count += 1
    else:
        num_digits = list(map(int, str(num)))
        is_lunlun = True
        for i in range(len(num_digits) - 1):
            if abs(num_digits[i] - num_digits[i + 1]) > 1:
                is_lunlun = False
                num = skip_num(num_digits, i) - 1
                break
            
        if is_lunlun:
            lunlun_count += 1
    if lunlun_count >= K:
        break

print(num)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
L = deque()
for i in range(9):
    L.append((i+1))

for i in range(K):
    ans = L.popleft()
    if ans % 10:
        L.append(10*ans+ans%10-1)
    L.append(10*ans+ans%10)
    if ans % 10-9:
        L.append(10*ans+ans%10+1)

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

K = int(input())

ans = set()
def dfs(last, lis):
    ans.add(int(''.join(lis)))
    if len(lis)==11:
        return
    dfs(last, lis+str(last))
    if last!=0:
        dfs(last-1, lis+str(last-1))
    if last!=9:
        dfs(last+1, lis+str(last+1))

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

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

Submission status: Accepted

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

q = collections.deque()
for i in range(9):
    q.append(i+1)
while(q):
    x = q.popleft()
    k = x % 10
    for j in range(3):
        if k == 0 and j == 0:
            continue
        elif k == 9 and j == 2:
            continue
        else:
            if j == 0:
                q.append(x*10+k-1)
            elif j == 1:
                q.append(x*10 + k)
            else:
                q.append(x*10+k+1)
    #     print(q)
    # print(x)
    K -= 1
    if K == 0:
        print(x)
        break

Submission status: Accepted

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

k=int(input())

def dfs(keta,num):
  global ans
  ans.append(int(''.join(num)))

  if keta==10:
    return

  min_n=max(0,int(num[-1])-1)
  max_n=min(9,int(num[-1])+1)
  for i in range(min_n,max_n+1):
    dfs(keta+1,num+[str(i)])

ans=[]
for i in range(1,10):
  dfs(1,[str(i)])

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

Submission status: Accepted

Solution code:
import sys

k=int(input())

def dfs(keta,num):
  global ans
  ans.append(int(''.join(num)))

  if keta==10:
    return

  min_n=max(0,int(num[-1])-1)
  max_n=min(9,int(num[-1])+1)
  for i in range(min_n,max_n+1):
    dfs(keta+1,num+[str(i)])

ans=[]
for i in range(1,10):
  dfs(1,[str(i)])

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

Submission status: Accepted

Solution code:
k=int(input())

def dfs(keta,num):
  global ans
  ans.append(int(''.join(num)))

  if keta==10:
    return

  min_n=max(0,int(num[-1])-1)
  max_n=min(9,int(num[-1])+1)
  for i in range(min_n,max_n+1):
    dfs(keta+1,num+[str(i)])

ans=[]
for i in range(1,10):
  dfs(1,[str(i)])

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

Submission status: Accepted

Solution code:
K = int(input())

def f(n, k, a):
    if k == n:
        return 1
    res = 0
    res += f(n, k+1, a)
    if a > 0:
        res += f(n, k+1, a-1)
    if a < 9:
        res += f(n, k+1, a+1)
    return res


cnt = 0
for n in range(1, 12):
    c2 = 0
    for a in range(1, 10):
        c2 += f(n, 1, a)
        if cnt+c2 >= K:
            num = n
            ini = a
            cnt += c2-f(n, 1, a)
            c2 = -1
            break
    if c2 < 0:
        break
    cnt += c2

ans = [ini]
for k in range(2, num+1):
    for a in range(max(0, ans[-1]-1), min(10, ans[-1]+2)):
        cnt += f(num, k, a)
        if cnt >= K:
            ans.append(a)
            cnt -= f(num, k, a)
            break

for i in range(len(ans)):
    ans[i] = str(ans[i])
print("".join(ans))

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
A = deque([str(i) for i in range(1,10)])
cnt = 0
while cnt<K:
    a = A.popleft()
    cnt += 1
    if a[-1]=="0":
        a0 = a+"0"
        a1 = a+"1"
        A.append(a0)
        A.append(a1)
    elif a[-1]=="9":
        a0 = a+"8"
        a1 = a+"9"
        A.append(a0)
        A.append(a1)
    else:
        b = a[-1]
        a0 = a+str(int(b)-1)
        a1 = a+b
        a2 = a+str(int(b)+1)
        A.append(a0)
        A.append(a1)
        A.append(a2)
print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def dfs(s):
  if len(s)==11:
    return
  if s!="":
    a.append(int(s))
  for c in "0123456789":
    if s=="" and c=="0":continue
    if s!="":
      if abs(ord(c)-ord(s[-1]))<=1:
        dfs(s+c)
    else:
      dfs(s+c)

k=int(input())
a=[]
dfs("")
a=list(set(a))
a.sort()
print(a[k-1])

Submission status: Accepted

Solution code:
N = int(input())
if N <= 9:
  print(N)
  exit()
A = [[] for _ in range(11)]
A[0] = [1,2,3,4,5,6,7,8,9]
now = 9
keta = 1
while True:
  for x in A[keta-1]:
    x = str(x)
    last = int(x[-1])
    if last - 1 >= 0:
      temp = x+str(last-1)
      A[keta].append(int(temp))
      now += 1
      if now == N:
        print(temp)
        exit()
    temp = x+str(last)
    A[keta].append(int(temp))
    now += 1
    if now == N:
      print(temp)
      exit()
    if last+1 <= 9:
      temp = x+str(last+1)
      A[keta].append(int(temp))
      now += 1
      if now == N:
        print(temp)
        exit()
  keta += 1

Submission status: Accepted

Solution code:
K = int(input())


def dfs(d, n, buf):
    buf.append(n)

    if d == 10:
        return

    lsd = n % 10

    if lsd != 0:
        dfs(d + 1, n * 10 + lsd - 1, buf)

    dfs(d + 1, n * 10 + lsd, buf)

    if lsd != 9:
        dfs(d + 1, n * 10 + lsd + 1, buf)


buf = []

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

print(sorted(buf)[K - 1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

queue = deque(range(1, 10))

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

print(x)

Submission status: Accepted

Solution code:
K = int(input())

k = K - 1

numbers = {
    0: 1
}

while k > 0:
    k -= 1
    for i in range(len(numbers)):
        n = numbers[i]
        if n == 9:
            continue

        if abs(numbers.get(i - 1, n) - (n + 1)) <= 1 and abs(numbers.get(i + 1, n) - (n + 1)) <= 1:
            numbers[i] += 1
            j = i - 1
            while j >= 0:
                numbers[j] = max(numbers[j + 1] - 1, 0)
                j -= 1
            break
    else:
        for key in numbers.keys():
            numbers[key] = 0
        numbers[len(numbers)] = 1

print(''.join([str(numbers[i]) for i in range(len(numbers))])[::-1])

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

ans = q.popleft()
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
que = deque(list(range(1,10)))
for i in range(k):
    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)
print(x)

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

heapify(a)
while len(a):
    tmp = heappop(a)
    keta = len(str(tmp))
    one = tmp % 10
    k -= 1
    # -1,0,+1の範囲で末尾につけてqueueに入れる
    if one != 0: heappush(a, tmp * 10 + one - 1)
    heappush(a, tmp * 10 + one)
    if one != 9: heappush(a, tmp * 10 + one + 1)
    if k == 0:
        print(tmp)
        exit()

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

heapify(a)
while len(a):
    tmp = heappop(a)
    keta = len(str(tmp))
    one = tmp % 10
    k -= 1
    for i in range(0, 10):
        if abs(one - i) <= 1:
            heappush(a, tmp * 10 + i)
    if k == 0:
        print(tmp)
        exit()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    vec = list(range(1, 10))
    for i in range(K):
        tail = vec[i] % 10
        n10 = vec[i] * 10
        if tail == 0:
            vec.append(n10 + tail)
            vec.append(n10 + tail + 1)
        elif tail == 9:
            vec.append(n10 + tail - 1)
            vec.append(n10 + tail)
        else:
            vec.append(n10 + tail - 1)
            vec.append(n10 + tail)
            vec.append(n10 + tail + 1)

        if len(vec) >= K:
            break

    print(vec[K - 1])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    vec = list(range(1, 10))
    for i in range(K):
        tail = vec[i] % 10
        if tail == 0:
            vec.append(vec[i] * 10 + tail)
            vec.append(vec[i] * 10 + tail + 1)
        elif tail == 9:
            vec.append(vec[i] * 10 + tail - 1)
            vec.append(vec[i] * 10 + tail)
        else:
            vec.append(vec[i] * 10 + tail - 1)
            vec.append(vec[i] * 10 + tail)
            vec.append(vec[i] * 10 + tail + 1)

        if len(vec) == K:
            break

    print(vec[K - 1])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    vec = list(range(1, 10))
    for i in range(K):
        tail = vec[i] % 10
        n10 = vec[i] * 10
        if tail == 0:
            vec.append(n10 + tail)
            vec.append(n10 + tail + 1)
        elif tail == 9:
            vec.append(n10 + tail - 1)
            vec.append(n10 + tail)
        else:
            vec.append(n10 + tail - 1)
            vec.append(n10 + tail)
            vec.append(n10 + tail + 1)
            
        if len(vec) == K:
            break

    print(vec[K - 1])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    vec = list(range(1, 10))
    for i in range(K):
        tail = vec[i] % 10
        n10 = vec[i] * 10
        if tail == 0:
            vec.append(n10 + tail)
            vec.append(n10 + tail + 1)
        elif tail == 9:
            vec.append(n10 + tail - 1)
            vec.append(n10 + tail)
        else:
            vec.append(n10 + tail - 1)
            vec.append(n10 + tail)
            vec.append(n10 + tail + 1)

    print(vec[K - 1])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    queue = deque(range(1, 10))
    for _ in range(K):
        n = queue.popleft()

        tail = n % 10
        n10 = n * 10
        if tail == 0:
            queue.append(n10 + tail)
            queue.append(n10 + tail + 1)
        elif tail == 9:
            queue.append(n10 + tail - 1)
            queue.append(n10 + tail)
        else:
            queue.append(n10 + tail - 1)
            queue.append(n10 + tail)
            queue.append(n10 + tail + 1)

    print(n)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    queue = deque(range(1, 10))
    for _ in range(K):
        n = queue.popleft()

        tail = n % 10
        n10 = n * 10
        if tail != 0:
            queue.append(n10 + tail - 1)
        queue.append(n10 + tail)
        if tail != 9:
            queue.append(n10 + tail + 1)

    print(n)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    n = 0

    def dfs(vec, d):
        nonlocal n
        if d == 0:
            n += 1
            if n == K:
                print(''.join(map(str, vec)))
                return
            else:
                return

        for i in range(max(0, vec[-1] - 1), min(9, vec[-1] + 1) + 1):
            vec.append(i)
            dfs(vec, d - 1)
            if n >= K:
                return
            vec.pop()

    for d in range(10 ** 20):
        for i in range(1, 10):
            vec = [i]
            dfs(vec, d)
            if n >= K:
                return

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import chain

K = int(input())

L = 10
lunlun = [[] for _ in range(L+1)]

lunlun[1] = list(range(1,10))

for i in range(1,L):
    for x in lunlun[i]:
        r = x%10
        if r == 0:
            lunlun[i+1] += [x*10 + r, x*10 + r+1]
        elif r == 9:
            lunlun[i+1] += [x*10 + r-1, x*10 + r]
        else:
            lunlun[i+1] += [x*10 + r-1, x*10 + r, x*10 + r+1]

res = list(chain.from_iterable(lunlun))

print(res[K-1])