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())
lunlun = []

def dfs(x):
    lunlun.append(x)
    if len(str(x))==10:
        return
    d = x % 10
    for v in [d-1,d,d+1]:
        if 0<= v <= 9:
            dfs(x*10+v)

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

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

Submission status: Accepted

Solution code:
def solve():
    K = int(input())
    all = []
    for i in range(1,10):
        dfs(1,i,all)
    
    all.sort()
    print(all[K-1])
    
def dfs(d, val, all):
    all.append(val)

    if d == 10:
        return
    
    for j in [-1,0,1]:
        add = val % 10 + j
        if 0 <= add <= 9:
            dfs(d+1, val*10+add, all)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
q = deque()
for i in range(1, 10):
    q.append(i)
for _ in range(K - 1):
    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(q.popleft())

Submission status: Accepted

Solution code:
from collections import deque
import sys

k = int(input())
d = deque()
c = 1

while True:
    if c < 10:
        d.append(c)
        c += 1
        if c > k:
            print(d.pop())
            sys.exit()
    else:
        n = d.popleft()
        m = n % 10
        for i in range(-1, 2):
            if 0 <= m + i <= 9:
                d.append(n * 10 + m + i)
                c += 1
                if c > k:
                    print(d.pop())
                    sys.exit()

Submission status: Accepted

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

def RN(x,y):

    RUNRUN_numbers.append(y)

    if y > 10**9:
        return
    if x == 0:
        for i in range(0,2):
            
            yy = 10*y + i
            RN(i,yy)
    elif x == 9:
        for i in range(8,10):
            
            yy = 10*y + i
            RN(i,yy)
    else:
        for i in range(x-1,x+2,1):
            
            yy = 10*y + i
            RN(i,yy)


for i in range(1,10):
    RN(i,i)

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

Submission status: Accepted

Solution code:
k=int(input())
li=[str(i) for i in range(1,10)]

for j in range(k):
    t=li[j]
    if t[-1]!="0":
        li.append(t+str(int(t[-1])-1))
    
    li.append(t+str(int(t[-1])))
        
    if t[-1]!="9":
        li.append(t+str(int(t[-1])+1))

print(li[k-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

for i in range(K):
    now = dq.popleft()
    for i in (-1,0,1):
        add = (now%10)+i
        if 0 <= add<10:
            dq.append(now*10+add)

print(now)

Submission status: Accepted

Solution code:
import math

k = int(input())

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

c = 0
while k > len(l):
    f = l[c] - (l[c] // 10 * 10)

    if f != 0:
        l.append(l[c] * 10 + f - 1)

    l.append(l[c] * 10 + f)

    if f != 9:
        l.append(l[c] * 10 + f + 1)

    c += 1

print(l[k - 1])

Submission status: Accepted

Solution code:
def main():
    k = int(input())
    a = [i for i in range(1,10)]
    x = 0
    while(1):
        if k <= len(a):
            print(a[k-1])
            return
        for i in range(-1,2):
            d = a[x]%10 +i
            if 0 <= d and d < 10:
                a.append(a[x]*10 + d)
        x+=1

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dfs(A,B):
    if len("".join(A))>10:
        return
    if int(A[-1]) == 0:
        for i in [0,1]:
            A.append(str(i))
            B.append("".join(A))
            dfs(A, B)
            A.pop()
    elif int(A[-1]) == 9:
        for i in [8,9]:
            A.append(str(i))
            B.append("".join(A))
            dfs(A, B)
            A.pop()
    else:
        for i in range(int(A[-1])-1,int(A[-1])+2):
            A.append(str(i))
            B.append("".join(A))
            dfs(A,B)
            A.pop()

if __name__ == "__main__":
    k=int(input())
    ans_list=[]
    num_list=[]
    for i in range(1,10):
        ans_list.append(str(i))
        num_list.append(str(i))
        dfs(num_list,ans_list)
        num_list.clear()
    ans_list=sorted(ans_list,key=int)
    print(ans_list[k-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
k = int(input())

dq = deque(list(range(1, 10)))
rep = 0
while rep < k:
    now = dq.popleft()
    rep+=1
    for i in (-1, 0, 1):
        if 0<=now%10+i<10:
            dq.append(now*10+now%10+i)
print(now)

Submission status: Accepted

Solution code:
K = int(input())

LLs = []

def dfs(d, num):
    LLs.append(num)
    
    if d == 10: return

    a = num % 10
    for i in [-1, 0, 1]:
        b = a + i
        if  0 <= b < 10:
            dfs(d+1, num * 10 + b)

d = 1
for i in range(1, 10):
    dfs(d, i)

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

Submission status: Accepted

Solution code:
import math
import copy
from queue import Queue

n = int(input())
#n, k = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
#num = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
# s = [input() for i in range(n)]
#s = input()
# list = list(s)
# dp = [[0 for _ in range(2)] for _ in range(13)]
#s = [input() for i in range(n)]

#a = [[0 for _ in range(n+1)] for _ in range(n+1)]
#b = [[0 for _ in range(n+1)] for _ in range(n+1)]

queue = Queue()
temp = 0

if (n < 10):
    print(n)
else:
    for i in range(1,10):
        queue.put(i)
    for i in range(1,n):
        temp = queue.get()
        if (temp % 10 != 0) :
            queue.put(10 * temp + (temp % 10) - 1)
        queue.put(10 * temp + (temp % 10))
        if (temp % 10 != 9) :
            queue.put(10 * temp + (temp % 10) + 1)
    print(queue.get())

Submission status: Accepted

Solution code:
K = int(input())

runrun_pool = [list(range(1,10))]
runrun_num = len(runrun_pool[0])
digit = 1

while runrun_num < K:
    tmp = list()
    for i in runrun_pool[digit-1]:
        if i % 10 == 0:
            tmp.append(i * 10 + i % 10)
            tmp.append(i * 10 + i % 10 + 1)
        elif i % 10 == 9:
            tmp.append(i * 10 + i % 10 - 1)
            tmp.append(i * 10 + i % 10)
        else:
            tmp.append(i * 10 + i % 10 - 1)
            tmp.append(i * 10 + i % 10)
            tmp.append(i * 10 + i % 10 + 1)
    runrun_pool.append(tmp)         
    runrun_num += len(runrun_pool[digit])
    digit += 1

num = K
for i in range(digit-1):
    num -= len(runrun_pool[i])
    
print(runrun_pool[digit-1][num-1])

Submission status: Accepted

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

dq = deque(list(range(1, 10)))
rep = 0
while rep < k:
    now = dq.popleft()
    rep+=1
    for i in (-1, 0, 1):
        if 0<=now%10+i<10: dq.append(now*10+now%10+i)
print(now)

Submission status: Accepted

Solution code:
K = int(input())

def dfs(A, li):
    if len(A)==10:
        return
    
    for i in right(A):
        A.append(i)
        A_int = int(''.join(map(str, A)))
        li.append(A_int)
        dfs(A, li)
        A.pop()
    return
        
def right(A):
    if A==[]:
        return [x for x in range(1, 10)]
    
    ret = A[-1]
    if ret==9:
        return [8, 9]
    elif ret==0:
        return [0, 1]
    else:
        return [ret-1, ret, ret+1]

li = []    
dfs([], li)
li.sort()
# print(len(li))
print(li[K-1])

Submission status: Accepted

Solution code:
k = int(input())

all_lun = []
def dfs(d):
    all_lun.append(d)
    if len(str(d))==10:
        return
    for i in [-1, 0, 1]:
        if 0<=d%10+i<10: dfs(d*10+d%10+i)
for i in range(1, 10):
    dfs(i)
all_lun.sort()
print(all_lun[k-1])

Submission status: Accepted

Solution code:
from collections import deque

def main():
    K = int(input())
    if K <= 9:
        print(K)
        return

    que = deque(range(1,10))
    # print(que)
    cnt = 9
    while True:
        x = que.popleft()
        mod = x % 10

        if mod != 0:
            que.append(10 * x + mod - 1)
            # print(que)
            cnt += 1
            if cnt == K:
                print(que[-1])
                return

        que.append(10 * x + mod)
        # print(que)
        cnt += 1
        if cnt == K:
            print(que[-1])
            return

        if mod != 9:
            que.append(10 * x + mod + 1)
            # print(que)
            cnt += 1
            if cnt == K:
                print(que[-1])
                return

main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    k = I()

    m = {}
    def f(i,t):
        k = (i,t)
        if k in m:
            return m[k]

        r = 0
        if i == 1:
            if t == -1:
                r = 9
            elif t == 0 or t == 9:
                r = 2
            else:
                r = 3
        else:
            if t == -1:
                r += f(i-1, -1)
                for nt in range(1, 10):
                    r += f(i-1, nt)
            else:
                for nt in range(max(0,t-1), min(10, t+2)):
                    r += f(i-1, nt)
        m[k] = r
        return r

    def g(i, t, k):
        if i == 1:
            if t == -1:
                return k
            if t == 0:
                return k - 1
            return t + k - 2

        if t == -1:
            f1 = f(i-1, -1)
            if f1 >= k:
                return g(i-1, -1, k)
            k -= f1
            for j in range(1, 10):
                fj = f(i-1, j)
                if fj >= k:
                    r = g(i-1, j, k)
                    return r + j * 10**(i-1)
                k -= fj
        else:
            for j in range(max(0, t-1), min(10, t+2)):
                fj = f(i-1, j)
                if fj >= k:
                    r = g(i-1, j, k)
                    return r + j * 10**(i-1)
                k -= fj

    r = g(11, -1, k)
    return r

print(main())

Submission status: Accepted

Solution code:
# https://drken1215.hatenablog.com/entry/2020/04/05/150900
def abc161_d():
  k = int(input())
  lunlun = []

  def rec(d, val):
    # 答えリストに追加
    lunlun.append(val)
    # 10桁で打ち止め
    if d == 10: return
    # 次の桁を生成
    for j in range(-1, 2):
      add = val % 10 + j
      if 0 <= add and add <= 9:
        rec(d+1, val*10 + add)

  # メイン
  for i in range(1, 10):
    rec(1, i)
  lunlun.sort()
  ans = lunlun[k-1]
  print(ans)

abc161_d()

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

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

for i in range(k):
  current_num = a.pop()
  current_str = str(current_num)
  current_last = int(current_str[-1])

  up = ""  
  mid = current_str + str(current_last)
  down = ""

  if current_last >= 0 and current_last <= 8:
    up = current_str + str(current_last + 1)

  if current_last >= 1 and current_last <= 9:
    down = current_str + str(current_last - 1)
  
  if len(down) != 0:
    a.appendleft(down)

  a.appendleft(mid)

  if len(up) != 0:
    a.appendleft(up)

print(current_num)

Submission status: Accepted

Solution code:
def plus(x):
    X = str(x)
    p = int(X[len(X)-1])
    if p == 0:
        return(int(X+str(p)), int(X+str(p+1)))
    elif p == 9:
        return(int(X+str(p-1)), int(X+str(p)))
    else:
        return(int(X+str(p-1)), int(X+str(p)), int(X+str(p+1)))
    
A = [[] for _ in range(10)]
for i in range(1,10):
    A[0].append(i)
    
for i in range(1,10):
    for j in A[i-1]:
        A[i].extend(plus(j))
ans = sum(A,[])
print(ans[int(input())-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
que = deque(list(range(1, 10)))

c = 0
while que:
    n = que.popleft()
    s = str(n)

    flg = True

    for i in range(1, len(s)):
        if abs(int(s[i])-int(s[i-1])) >= 2:
            flg = False

    if flg:
        c += 1

    if c == K:
        print(s)
        exit()

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(K: int):

    ct = 0
    q = deque([1,2,3,4,5,6,7,8,9])
    while(len(q)>0):
        a = q.popleft()
        al = a % 10
        ct += 1 
        if ct == K:
            print(a)
            break

        if al != 0:
            q.append(a*10+al - 1)
        q.append(a*10+al)
        if al != 9:
            q.append(a*10+al + 1)

        # print(q)


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
import sys
sys.setrecursionlimit(10**7)
k = int(input())
from collections import deque
d = deque()
for i in range(9):
    d.append(str(i+1)) # 初期

def dfs():
    global cnt
    a = d.popleft()
    
    #print(cnt)
    for i in range(-1,2,1):
        nya = a
        last_string = int(a[-1]) + i
        if last_string < 0 or last_string > 9:
            pass
        else:
            nya += str(last_string)
            cnt += 1
            if k == cnt:
                print(nya)
                exit()
            d.append(nya)
    dfs()

cnt = 9
if k <= cnt:
    print(k)
    exit()
dfs()

Submission status: Accepted

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

listup = []
listup.append(list(range(1, 10)))
list_length = 9
if K <= 9:
    print(listup[0][K - 1])
    sys.exit(0)
for i in range(10000000):
    new_list_floor = []
    for value in listup[i]:
        newlist = []
        mod_value = value % 10
        if mod_value == 0:
            newlist.append(value * 10 + mod_value)
            newlist.append(value * 10 + mod_value + 1)
        elif mod_value == 9:
            newlist.append(value * 10 + mod_value - 1)
            newlist.append(value * 10 + mod_value)
        else:
            newlist.append(value * 10 + mod_value - 1)
            newlist.append(value * 10 + mod_value)
            newlist.append(value * 10 + mod_value + 1)
        list_length_before = list_length
        list_length += len(newlist)
        new_list_floor.extend(newlist)
        if list_length >= K:
            diff = K - list_length_before
            print(newlist[diff - 1])
            sys.exit(0)
    listup.append(new_list_floor)
print(listup)

Submission status: Accepted

Solution code:
def dfs(l, r):
    if len(r) == 11:
        return
    l.append(int(r))
    for i in range(-1, 2):
        tmp = int(r[-1]) + i
        if 0 <= tmp <= 9:
            dfs(l, r + str(tmp))


k = int(input())
l = []
for i in range(1, 10):
    dfs(l, str(i))
print(sorted(l)[k - 1])

Submission status: Accepted

Solution code:
import heapq
K=int(input())
queue=[i for i in range(1,10)]
heapq.heapify(queue)
for i in range(K-1):
    n=heapq.heappop(queue)
    if n%10==0:
        heapq.heappush(queue,n*10+0)
        heapq.heappush(queue,n*10+1)
    elif n%10==9:
        heapq.heappush(queue,n*10+8)
        heapq.heappush(queue,n*10+9) 
    else:
        heapq.heappush(queue,n*10+(n%10))
        heapq.heappush(queue,n*10+(n%10)+1)
        heapq.heappush(queue,n*10+(n%10)-1)
print(queue[0])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

def dfs(n, before):
    global cnt, K, ans, flag
    ints = int(before[-1])
    int1s = ints - 1; ints1 = ints + 1

    if int1s >= 0:
        after1s = before + str(int1s)
        if n == 1: 
            cnt += 1
        if cnt == K and flag == 0:
            ans = after1s; flag = 1
            return
        if n >= 2:
            dfs(n-1, after1s)
    
    afters = before + str(ints)
    if n == 1:
        cnt += 1
    if cnt == K and flag == 0:
        ans = afters; flag = 1
        return
    if n >= 2:
        dfs(n-1, afters)

    if ints1 <= 9:
        afters1 = before + str(ints1)
        if n == 1:
            cnt += 1
        if cnt == K and flag == 0:
            ans = afters1; flag = 1
        if n >= 2:
            dfs(n-1, afters1)


def main():
    global cnt, K, ans, flag
    K = int(input())
    if K <= 9:
        print(K)
        return
    cnt = 9
    flag = 0
    for n in range(1, 13):
        for s in range(1, 10):
            dfs(n, str(s))
            if flag == 1:
                break
        if flag == 1:
            break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dfs(r):
    global l
    if len(r) == 11:
        return
    l.append(int(r))
    for i in range(-1, 2):
        tmp = int(r[-1]) + i
        if 0 <= tmp <= 9:
            dfs(r + str(tmp))


k = int(input())
l = []
for i in range(1, 10):
    dfs(str(i))
print(sorted(l)[k - 1])

Submission status: Accepted

Solution code:
c = int(input())

l = list(range(1, 10))

j = 0

if c < 10:
    print(l[c-1])

else:
    c -= 9

    while True:
        new_l = []
        for i in l:
            d = i % 10
            if d != 0:
                new_l.append(10*i+d-1)
            
            new_l.append(10*i+d)

            if d != 9:
                new_l.append(10*i+d+1)

        if c <= len(new_l):
            new_l.sort()
            print(new_l[c-1])
            break
        else:
            c -= len(new_l)
            l = new_l

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')
from collections import deque


def solve():
    k = II()
    q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

    if k <= 9:
        print(q[k-1])
        return

    cnt = len(q)
    while 1:
    # for _ in range(1000000):
        a = q.popleft()
        # print(a)
        one = int(str(a)[-1])
        for i in range(one-1, one+2):
            # print(' ', i)
            if i < 0 or i > 9:
                continue
            num = int(str(a) + str(i))
            cnt += 1
            # print('  ', num, cnt)
            if cnt == k:
                print(num)
                return

            q.append(num)
        # print(q)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
num = [str(i) for i in range(1, 10)]
lunlun = num
for i in range(10):
    temp_list = []
    for j in num:
        temp = int(j[-1])
        if 0 < temp < 9:
            temp_list.append(j + str(temp - 1))
            temp_list.append(j + str(temp))
            temp_list.append(j + str(temp + 1))
        elif temp == 0:
            temp_list.append(j + str(temp))
            temp_list.append(j + str(temp + 1))
        else:
            temp_list.append(j + str(temp - 1))
            temp_list.append(j + str(temp))
    num = temp_list
    lunlun = lunlun + num
lunlun = [int(l) for l in lunlun]
lunlun = list(set(lunlun))
lunlun.sort()
print(lunlun[N - 1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
d = deque(range(1, 10))
Dequeue = lambda: d.popleft()
Enqueue = lambda x: d.append(x)

for _ in range(int(input())):
    x = Dequeue()
    m = x%10
    if m != 0: Enqueue(10*x + m-1)
    if True  : Enqueue(10*x + m)
    if m != 9: Enqueue(10*x + m+1)
print(x)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    k = int(input())
    res = []

    def dfs(x):
        res.append(x)
        if len(str(x)) == 10:
            return

        for i in range(10):
            if abs(x % 10 - i) <= 1:
                dfs(x * 10 + i)

        return

    for i in range(1, 10):
        dfs(i)
    res.sort()
    print(res[k - 1])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

def dfs(k):
  cnt = 0
  stack = deque()
  for i in range(1, 10):
    stack.append(i)
  while cnt <= k:
    q = stack.popleft()
    ans.append(q)
    cnt += 1
    l = q % 10
    for x in range(max(0, l - 1), min(10, l + 2)):
      stack.append(q * 10 + x)
          
ans = []
dfs(k)
print(ans[k-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
k = int(readline())

X = [[i for i in range(1, 10)]]
for i in range(9):
    Y = []
    for x in X[-1]:
        s = x % 10
        if s == 0:
            Y.append(x*10+s)
            Y.append(x*10+s+1)
        elif s == 9:
            Y.append(x*10+s-1)
            Y.append(x*10+s)
        else:
            Y.append(x*10+s-1)
            Y.append(x*10+s)
            Y.append(x*10+s+1)
    X.append(Y)

XX = []
for x in X:
    XX += x[:]
#XX = sorted(XX)

print(XX[k-1])

Submission status: Accepted

Solution code:
k = int(input())
l = []
for i in range(1, 10):
    l.append(i)
judge = l
for d in range(1, 10):
    tmp = []
    for i in range(len(judge)):
        val = judge[i]
        for j in range(-1, 2):
            add = val%10 + j
            if add >= 0 and add <= 9:
                tmp.append(val*10 + add)
    for i in range(len(tmp)):
        l.append(tmp[i])
    judge = tmp
print(l[k-1])

Submission status: Accepted

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

lunlun_queue = queue.Queue()

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

for i in range(K):
    ans = lunlun_queue.get()

    if(ans % 10 != 0):
        lunlun_queue.put(ans * 10 + ans % 10 - 1)
    
    lunlun_queue.put(ans * 10 + ans % 10)

    if(ans % 10 != 9):
        lunlun_queue.put(ans * 10 + ans % 10 + 1)
'''
while not lunlun_queue.empty():
    print(lunlun_queue.get())
'''
print(ans)

Submission status: Accepted

Solution code:
import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=q
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)


K = readInt()

q = queue.Queue()

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

ans = 0
for i in range(K):
	ans = q.get()
	if str(ans)[-1]=="0":
		q.put(int(str(ans)+"0"))
		q.put(int(str(ans)+"1"))
	elif str(ans)[-1]=="9":
		q.put(int(str(ans)+"8"))
		q.put(int(str(ans)+"9"))
	else:
		q.put(int(str(ans)+str(int(str(ans)[-1])-1)))
		q.put(int(str(ans)+str(int(str(ans)[-1]))))
		q.put(int(str(ans)+str(int(str(ans)[-1])+1)))

print(ans)

Submission status: Accepted

Solution code:
k = int(input())
A = [1,2,3,4,5,6,7,8,9]
for i in A:
    if len(A) > k:
        break
    x = i%10
    for j in range(max(x-1, 0), min(x+2, 10)):
        A.append(10*i+j)
print(A[k-1])

Submission status: Accepted

Solution code:
K = int(input())
table = [1,2,3,4,5,6,7,8,9]
for i in table:
  if len(table) > K:
    break
  x = i % 10
  for j in range(max(0, x - 1), min(x + 2, 10)):
    table.append(i * 10 + j)
print(table[K-1])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

runrun = [None for _ in range(100)]
runrun[1] = (1, 2, 3, 4, 5, 6, 7, 8, 9)


def gen_runrun_keta(k):
    for x in runrun[k - 1]:
        r = x % 10
        if r > 0:
            yield 10 * x + (r - 1)
        yield 10 * x + r
        if r < 9:
            yield 10 * x + (r + 1)


for keta in range(2, 11):
    runrun[keta] = tuple(gen_runrun_keta(keta))


rest = int(read())

answer = 0
for n in range(1, 11):
    if rest <= len(runrun[n]):
        answer = runrun[n][rest - 1]
        break
    rest -= len(runrun[n])
print(answer)

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
cand=["1","2","3","4","5","6","7","8","9"]
cand=deque(cand)
lunlun=['0']
while len(lunlun)<10**5+5:
    l=cand.popleft()
    lunlun.append(l)
    if l[-1]!='0':
        cand.append(l+str(int(l[-1])-1))
    cand.append(l+str(int(l[-1])))
    if l[-1]!='9':
        cand.append(l+str(int(l[-1])+1))
print(lunlun[k])

Submission status: Accepted

Solution code:
import queue

q = queue.Queue()

k = int(input())

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
cnt = 0
def main():
    K = int(readline())
    cnd = [i for i in range(1, 10)]

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

    cnt = 0 
    while len(dq)>0:
        cnt += 1
        x = dq.popleft()
        v = x%10
        if v==0:
            for i in (0, 1):
                nx = 10*x+i
                cnd.append(nx)
                dq.append(nx)
        elif v == 9:
            for i in (-1, 0):
                nx = 10*x+9+i
                cnd.append(nx)
                dq.append(nx)
        else:
            for i in (-1, 0, 1):
                nx = 10*x+v+i
                cnd.append(nx)
                dq.append(nx)
        if cnt == K:
            break 
    cnd.sort()
    print(cnd[K-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# D - Lunlun Number

import queue

K = int(input())

Q = queue.Queue()
for i in range(1, 10):
    Q.put(i)
ans = 0
for _ in range(K):
    ans = Q.get()
    if ans % 10 != 0:
        Q.put((10 * ans) + (ans % 10) - 1)
    Q.put((10 * ans) + (ans % 10))
    if ans % 10 != 9:
        Q.put((10 * ans) + (ans % 10) + 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
K=int(input())
res = 0
deq = deque(['1','2','3','4','5','6','7','8','9'])
for i in range(K):
    now = deq.popleft()
    if i==K-1:
       res = int(now)
       break

    if now[-1] != '0':
        tmp = str(int(now[-1])-1)
        deq.append(now+tmp)
    tmp = now + now[-1]
    deq.append(tmp)
    if now[-1] != '9':
        tmp = str(int(now[-1])+1)
        deq.append(now+tmp)

print(res)

Submission status: Accepted

Solution code:
import sys

k = int(input())
q = []

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

for i in range(k):
  
  n = q[i]
  
  if i == k - 1:
    print(n)
    sys.exit()
    
  if n % 10 != 0:
    q.append(10*n + (n % 10) - 1)
    
  q.append(10*n + (n % 10))
  
  if n % 10 != 9:
    q.append(10*n + (n % 10) + 1)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

K = int(input())

lunlun = []
def dfs(i,before):
    if i == 11:
        return
    lunlun.append(before)
    back = before%10
    for j in range(-1,2):
        t = back + j
        if 0 <= t < 10:
            dfs(i + 1,before*10 + t)

for i in range(1,10):
    dfs(1,i)
lunlun.sort()
print(lunlun[K - 1])

Submission status: Accepted

Solution code:
K = int(input())
r = [[] for _ in range(10)]
r[0] = list(range(1,10))

for i in range(9):
  for a in r[i]:
    s = str(a)
    d = a%10
    for j in range(d-1, d+2):
      if not 0 <= j <= 9: continue
      r[i+1].append(int(s+str(j)))

for i in range(10):
  if K >= len(r[i]):
    K -= len(r[i])
  else:
    print(r[i][K-1])
    break

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 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)

print(x)

Submission status: Accepted

Solution code:
def main():
    from collections import deque

    K = int(input())

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

    cnt = 0

    while dq:
        x = dq.popleft()
        cnt += 1
        if cnt == K:
            print(x)
            return

        r = x % 10

        s = max(0, r - 1)
        t = min(9, r + 1)

        for k in range(s, t + 1):
            dq.append(x * 10 + k)


if __name__ == '__main__':
    main()