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:
from sys import stdin
import heapq
def main():

    input = stdin.readline

    K = int(input())

    h = []
    
    for i in range(1,10):
        heapq.heappush(h,i)
    
    for i in range(K):
        ans = heapq.heappop(h)

        if ans % 10 != 0:
            heapq.heappush(h,ans * 10 + (ans % 10 - 1))
        heapq.heappush(h,ans*10 + (ans%10))
        if ans % 10 != 9:
            heapq.heappush(h,ans * 10 + (ans % 10 + 1))
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
runrun = []


def dfs(x):
    if x > 3234566667:
        return
    runrun.append(x)
    for i in range(10):
        if abs(x % 10 - i) <= 1:
            dfs(x * 10 + i)


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

runrun = sorted(runrun)
K = int(input())

print(runrun[K-1])

Submission status: Accepted

Solution code:
K = int(input())

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

for i in range(K):
    temp = que[i]
    if i == K-1:
        print(que[i])
        break
    mod = temp % 10
    if mod == 0:
        que += [temp*10+(mod), temp*10+(mod)+1]
    elif temp % 10 == 9:
        que += [temp*10+(mod)-1, temp*10+(mod)]
    else:
        que += [temp*10+(mod)-1, temp*10+(mod), temp*10+(mod)+1]

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
q = deque([])
cnt = 0
for i in range(1,10):
    q.append(str(i))

prev_c = 'a'
while cnt < 10**6:
    c = q.popleft()
    if c != prev_c:
        cnt += 1
        # print(c)
    prev_c = c
    if cnt == K:
        print(int(c))
        break
    if c[-1] != '0':
        q.append(c+str(int(c[-1])-1))
    q.append(c+str(int(c[-1])))
    if c[-1] != '9':
        q.append(c+str(int(c[-1])+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:
from queue import Queue
k = int(input())
q = Queue()
for i in range(9):
    q.put(i + 1)
for i in range(k):
    x = q.get()
    y = x % 10
    if x % 10 != 0:
        q.put(10 * x + y - 1)
    q.put(10 * x + y)
    if x % 10 != 9:
        q.put(10 * x + y + 1)
print(x)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
k = int(input())
ans = []
def bfs(que):
    finished = set()
    while que and len(ans) <= 10**5:
        x = que.popleft()
        ans.append(int(x))
        if x not in finished:
            finished.add(x)
            p = int(x[-1])
            if 1 <= p <= 8:
                que.append(x + str(p-1))
                que.append(x + str(p))
                que.append(x + str(p+1))
            elif p == 0:
                que.append(x + str(p))
                que.append(x + str(p+1))
            else:
                que.append(x + str(p-1))
                que.append(x + str(p))
que = deque([])
for i in range(1,10):
    que.append(str(i))
bfs(que)
ans.sort()
print(ans[k-1])

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

# 次の桁の生成ルール ex. 1 -> 10, 11, 12
def next_int(n):
    if n == 0:
        return [0, 1]
    elif n == 9:
        return [8, 9]
    else:
        return [n-1, n, n+1]

K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # とりあえず 1 桁目を初期値にとる
heapify(queue)

for _ in range(K-1):
    now = heappop(queue)  # 最小値を取り出す
    # 取り出した値を使って次の桁を生成し queue に投げる
    for next_i in next_int(now%10):
        heappush(queue, now*10 + next_i)

print(queue[0])  # K 回目に取り出す最小値

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
q = deque(range(1, 10))
for _ in range(k):
    x = q.popleft()
    r = x % 10
    if r != 0:
        q.append(10*x + (r - 1))
    q.append(10*x+r)
    if r != 9:
        q.append(10*x + (r + 1))
print(x)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
Q = list(range(1, 10))

for i in range(K):
    x = Q[i]
    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)

print(Q[K-1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
que = deque([i for i in range(1, 10)])
i = 0
while True:
    i += 1
    num = que.popleft()
    if i == k:
        print(num)
        exit()
    if num % 10 > 0:
        que.append(num * 10 + ((num % 10) - 1))
    que.append(num * 10 + (num % 10))
    if num % 10 < 9:
        que.append(num * 10 + ((num % 10) + 1))

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
if K <= 9:
    print(K)
else:
    que = deque([9,8,7,6,5,4,3,2,1])
    count = 0

    while True:
        x = que.pop()
        count += 1
        if count == K:
            break
        if x%10 != 0:
            que.appendleft(x*10+x%10-1)
        que.appendleft(x*10+x%10)
        if x%10 != 9:
            que.appendleft(x*10+x%10+1)
    
    




            

    print(x)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

# 次の桁の生成ルール ex. 1 -> 10, 11, 12
def next_int(n):
    nums = {0: [0, 1],
            1: [0, 1, 2],
            2: [1, 2, 3],
            3: [2, 3, 4],
            4: [3, 4, 5],
            5: [4, 5, 6],
            6: [5, 6, 7],
            7: [6, 7, 8],
            8: [7, 8, 9],
            9: [8, 9]}
    return nums[n]

K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # とりあえず 1 桁目を初期値にとる
heapify(queue)

for _ in range(K-1):
    now = heappop(queue)  # 最小値を取り出す
    # 取り出した値を使って次の桁を生成し queue に投げる
    for next_i in next_int(now%10):
        heappush(queue, now*10 + next_i)

print(queue[0])  # K 回目に取り出す最小値

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-1):
  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(q.get())

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
queue = deque(range(1, 10))

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

print(x)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

# 次の桁の生成ルール ex. 1 -> 10, 11, 12
def next_int(n):
    nums = {0: [0, 1],
            1: [0, 1, 2],
            2: [1, 2, 3],
            3: [2, 3, 4],
            4: [3, 4, 5],
            5: [4, 5, 6],
            6: [5, 6, 7],
            7: [6, 7, 8],
            8: [7, 8, 9],
            9: [8, 9]}
    return nums[n]

K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # とりあえず 1 桁目を初期値にとる
heapify(queue)

for _ in range(K-1):
    now = heappop(queue)  # 最小値を取り出す
    # 取り出した値を使って次の桁を生成し queue に投げる
    for next_i in next_int(now%10):
        heappush(queue, now*10 + next_i)

print(heappop(queue))  # K 回目に取り出す最小値

Submission status: Accepted

Solution code:
import queue

def resolve():
    k = int(input())

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

    for i in range(k):
        x = int(q.get())
        mod = x % 10

        if mod != 0:
            q.put(10 * x + mod - 1)
        
        q.put(10 * x + mod)

        if mod != 9:
            q.put(10 * x + mod + 1)

    print(x)
    
resolve()

Submission status: Accepted

Solution code:
import heapq as hq
import sys

k=int(input())
if k<10:
    print(k)

else:
    A=[1,2,3,4,5,6,7,8,9]
    hq.heapify(A)
    now=9
    while True:
        a=hq.heappop(A)
        r=a%10
        if r==0:
            for i in range(2):
                p=a*10+i
                hq.heappush(A,p)
                now+=1
                if k==now:
                    print(p)
                    sys.exit()
        elif r==9:
            for i in range(2):
                p=a*10+8+i
                hq.heappush(A,p)
                now+=1
                if k==now:
                    print(p)
                    sys.exit()
        else:
            for i in range(3):
                p=a*10+r+i-1
                hq.heappush(A,p)
                now+=1
                if k==now:
                    print(p)
                    sys.exit()

Submission status: Accepted

Solution code:
import queue

k = int(input())

q = queue.Queue()

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

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

# 次の桁の生成ルール ex. 1 -> 10, 11, 12
def next_int(n):
    nums = {0: [0, 1],
            1: [0, 1, 2],
            2: [1, 2, 3],
            3: [2, 3, 4],
            4: [3, 4, 5],
            5: [4, 5, 6],
            6: [5, 6, 7],
            7: [6, 7, 8],
            8: [7, 8, 9],
            9: [8, 9]}
    return nums[n]

K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # とりあえず 1 桁目を初期値にとる
heapify(queue)

for _ in range(K-1):
    now = heappop(queue)  # 最小値を取り出す
    # 取り出した値を使って次の桁を生成し queue に投げる
    for next_i in next_int(int(str(now)[-1])):
        heappush(queue, int(str(now)+str(next_i)))

print(heappop(queue))  # K 回目に取り出す最小値

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
K = int(input())
d = deque([1,2,3,4,5,6,7,8,9])
for i in range(K-1):
    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(d.popleft())

Submission status: Accepted

Solution code:
def jud(n1,n2):
	if abs(n1-int(str(n2)[0]))<=1:
		return 1
	else:
		return 0

rnrn = [[1,2,3,4,5,6,7,8,9],[10,11,12,21,22,23,32,33,34,43,44,45,54,55,56,65,66,67,76,77,78,87,88,89,98,99]]

for div in range(1,10):
	rnrn.append([])
	for i in range(len(rnrn[div])):
		y = str(rnrn[div][i])
		x = int(y[-1])
		if x-1!=-1:
			rnrn[div+1].append(int(y+str(x-1)))
		rnrn[div+1].append(int(y+str(x)))
		if x+1!=10:
			rnrn[div+1].append(int(y+str(x+1)))
		
rnrn2 = []
for i in range(len(rnrn)):
	rnrn2.extend(rnrn[i])

print(rnrn2[int(input())-1])

Submission status: Accepted

Solution code:
N = int(input())
tmp = [i for i in range(1, 10)]
ans = list(tmp)
for i in range(10):
    tmp2 = []
    for x in tmp:
        k = int(str(x)[-1])
        if k != 0:
            ans.append(10*x-1 + k)
            tmp2.append(10*x-1 + k)
        if k != 9:
            tmp2.append(10*x+1 + k)
            ans.append(10*x+1 + k)
        tmp2.append(10*x + k)
        ans.append(10*x + k)
    tmp = list(tmp2)

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

Submission status: Accepted

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

K = int(input())
for _ in range(K - 1):
    i = d.pop()
    if i % 10 != 0:
        d.appendleft(i * 10 + i % 10 - 1)
    d.appendleft(i * 10 + i % 10)
    if i % 10 != 9:
        d.appendleft(i * 10 + i % 10 + 1)
print(d.pop())

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

for _ in range(K):
    x = q.popleft()
    y = x % 10
    if y > 0:
        q.append(10 * x + y - 1)
    q.append(x * 10 + y)
    if y < 9:
        q.append(10 * x + y + 1)

print(x)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = []
    A = [[] for j in range(10)]
    for i in range(1, 10):
        A[0].append(i)

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

    ans = []
    for a in A:
        for b in a:
            ans.append(b)
    ans.sort()

    print(ans[K - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
q = deque(range(1,10))
while k:
    k-=1
    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 heapq
K = int(input())


def fun(h, n):
    tmp = n % 10
    if tmp != 0:
        heapq.heappush(h, 10 * n + tmp - 1)
    heapq.heappush(h, 10 * n + tmp)
    if tmp != 9:
        heapq.heappush(h, 10 * n + tmp + 1)


h = list(range(1, 10))
while K > 0:
    n = heapq.heappop(h)
    fun(h, n)
    K -= 1
else:
    print(n)

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  k= int(readline())
  l = [1,2,3,4,5,6,7,8,9]
  q = deque(l)
  x = 0
  for _ in range(k):
    x = q.popleft()
    sue = x%10
    if sue != 0:
      q.append(10*x+sue-1)
    q.append(10*x+sue)
    if sue!=9:
      q.append(10*x+sue+1)
  print(x)
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import queue

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

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

num = 0
while num < K:
        emp = A.get()
        var = emp % 10
        if var != 0:
                A.put(emp*10+var-1)
        A.put(10*emp+var)
        if var != 9:
                A.put(emp*10+var+1)
        num += 1

print(emp)

Submission status: Accepted

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

Submission status: Accepted

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

if (k < 10):
    print(ans1[k - 1])
else:
    while (ite < k):
        ans2 = []
        for num in ans1:
            keta1 = num % 10
            if (keta1 == 0):
                ans2.append(num * 10)
                ite += 1
                if (ite == k):
                    break
                ans2.append(num * 10 + 1)
                ite += 1
                if (ite == k):
                    break
                # ans2.append(num * 10 + 9)
                # ite += 1
                # if (ite == k):
                #     break
            elif (keta1 == 9):
                # ans2.append(num * 10)
                # ite += 1
                # if (ite == k):
                #     break
                ans2.append(num * 10 + keta1 - 1)
                ite += 1
                if (ite == k):
                    break
                ans2.append(num * 10 + keta1)
                ite += 1
                if (ite == k):
                    break
            else:
                ans2.append(num * 10 + keta1 - 1)
                ite += 1
                if (ite == k):
                    break
                ans2.append(num * 10 + keta1)
                ite += 1
                if (ite == k):
                    break
                ans2.append(num * 10 + keta1 + 1)
                ite += 1
                if (ite == k):
                    break
        ans1 = ans2[:]
    print(ans2[-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k = int(input())

from collections import deque

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

x = 0
while 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)
    k -= 1

print(x)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
K  =int(input())
from collections import deque
cnt = 1
q = deque([])
for i in range(1,10):
    q.append(i)
# print(q)
cnt = 0
while True:
    cnt += 1
    a = q.popleft()
    if a%10 > 0:
        q.append(10*a+a%10-1)
    q.append(10*a+a%10)
    if a%10 < 9:
        q.append(10*a+a%10+1)
    # print(a)
    if cnt == K:
        print(a)
        exit()

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):
  p=q.get()
  p1=p%10
  
  if p1!=0:
    q.put(10*p+p1-1)
  q.put(10*p+p1)
  if p1!=9:
    q.put(10*p+p1+1)
    
print(p)

Submission status: Accepted

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

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs():
    from collections import deque

    que = deque()
    cnt = 1
    memo = {}
    for i in range(1, 10):
        que.append(str(i))
        memo[cnt] = str(i)
        cnt += 1
    while que:
        x = que.popleft()
        last = int(x[-1])
        if last != 0:
            que.append(x+str(last-1))
            memo[cnt] = x + str(last-1)
            cnt += 1
        que.append(x+str(last))
        memo[cnt] = x+str(last)
        cnt += 1
        if last != 9:
            que.append(x+str(last+1))
            memo[cnt] = x + str(last+1)
            cnt += 1
        if cnt > K:
            return memo

K = INT()

res = bfs()
print(res[K])

Submission status: Accepted

Solution code:
k = int(input())
l = ['1','2','3','4','5','6','7','8','9']
lf = l.copy()
sum = 9
while sum < k:
    lff = []
    for i in lf:
        if i[-1] == '0':
            lff.append(i+'0')
            lff.append(i+'1')
        elif i[-1] == '9':
            lff.append(i+'8')
            lff.append(i+'9')
        else:
            lff.append(i+str(int(i[-1])-1))
            lff.append(i+str(int(i[-1])))
            lff.append(i+str(int(i[-1])+1))
    lf = lff
    l += lff
    sum += len(lff)
print(int(l[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])

num = 0

while True:
    x = q.popleft()
    num += 1
    if num == k:
        break
    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)

print(x)

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

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

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

print(x)

Submission status: Accepted

Solution code:
K = int(input())
a = []
def dfs(x):
    if x > 3234566667:
        return
    a.append(x)
    for i in range(10):
        if abs(x%10-i) <= 1:
            dfs(x*10+i)

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

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 _ in range(K):
    ans = q.get()
    if ans % 10 != 0:
        q.put(ans * 10 + ans % 10 - 1)
    q.put(ans * 10 + ans % 10)
    if ans % 10 != 9:
        q.put(ans * 10 + ans % 10 + 1)

print(ans)

Submission status: Accepted

Solution code:
import math
import random
import sys
import heapq
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, UserString
from functools import lru_cache, cmp_to_key
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)

sys.setrecursionlimit(10**7)
input = sys.stdin.readline
MAX_INT = 2**62-1


def main():
    k = int(input())
    queue = deque(list(range(1,10)))
    x = 0
    while k > 0:
        # print(queue)
        k -= 1
        x = queue.popleft()
        tail = x % 10
        if x % 10 != 0:
            queue.append(10*x + tail - 1)
        queue.append(10*x + tail)
        if x % 10 != 9:
            queue.append(10*x + tail + 1)
    print(x)

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K = int(input())
table = [n + 1 for n in range(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:
from copy import copy
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappush, heappop
setrecursionlimit(1000000)

# INF = float('inf')
INF = int(1e10)

def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    K = int(input())

    heap = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    heapify(heap)
    count = 0
    while True:
        count += 1
        v = heappop(heap)
        if v % 10 != 0:
            heappush(heap, 10 * v + (v % 10) - 1)
        heappush(heap, 10 * v + (v % 10))
        if v % 10 != 9:
            heappush(heap, 10 * v + (v % 10) + 1)

        if count == K:
            print(v)
            exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math as m

def is_lunlun(n):
    d=int(m.log10(n))

    for i in range(d):
        q = n // (10**(d-i))
        r = n % 10**(d-i)
        if i == 0:
            q_pre = q
        
        if abs(q_pre-q) >1:
            return False
        if i == d-1:
            if abs(r-q) > 1:
                return False
        n=r
        q_pre=q
    return True

K=int(input())

tbl = [[0]*10 for _ in range(10)]
accum = [[0]*10 for _ in range(10)]
cnt = 0
i=0
j=0
for j in range(10):
    if cnt >= K:
        break

    for i in range(10):
        if j == 0:
            tbl[i][j] = 1
        else:
            if i == 0:
                tbl[i][j] = tbl[i][j-1] + tbl[i+1][j-1]
            elif i==9:
                tbl[i][j] = tbl[i-1][j-1] + tbl[i][j-1]
            else:
                tbl[i][j] = tbl[i-1][j-1] + tbl[i][j-1] + tbl[i+1][j-1]

        if i != 0:
            cnt += tbl[i][j]
        accum[i][j]=cnt
        if cnt >= K:
            i_s=i
            j_s=j
            break

i=i_s
j=j_s

digit=str(i)

base=accum[i-1][j] if i>0 else accum[j-1][9]

while j > 0:
    j=j-1
    for itmp in [i-1,i,i+1]:
        if itmp < 0 or itmp >9:
            continue
        base += tbl[itmp][j]
        if base >= K:
            base -= tbl[itmp][j]
            break
    digit+=str(itmp)
    i=itmp
print(digit)

Submission status: Accepted

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

while(len(lun) < K):
  target = lun[cnt]
  num = target % 10
  if num != 0:
      lun.append(target * 10 + num - 1)
  lun.append(target * 10 + num)
  if num != 9:
      lun.append(target * 10 + num + 1)
  cnt += 1

print(lun[K-1])

Submission status: Accepted

Solution code:
K = int(input())
A = [1,2,3,4,5,6,7,8,9]
for i in range(len(A)):
    if A[i] != 9:
        for j in range(-1,2):
            a = int(str(A[i]) + str(A[i]+j))
            A.append(a)
    else:
        A.append(98)
        A.append(99)
A.append(100)
A.append(101)
L1 = 10
L2 = len(A.copy())
for i in range(8):
    for i in range(L1,L2):
        B = A[i]
        if B % 10 == 0:
            A.append(int(str(B) + '0'))
            A.append(int(str(B) + '1'))
        elif B % 10 == 9:
            A.append(int(str(B) + '8'))
            A.append(int(str(B) + '9'))
        else:
            for j in range(-1, 2):
                a = int(str(B) + str((B % 10) + j))
                A.append(a)
    L1 = L2
    L2 = len(A.copy())
print(A[K-1])

Submission status: Accepted

Solution code:
def add(n):
    l = []
    if(n%10 == 0):
        l.append(n*10)
        l.append(n*10+1)
    elif(n%10 == 9):
        l.append(n*10+8)
        l.append(n*10+9)
    else:
        l.append(n*10+n%10-1)
        l.append(n*10+n%10)
        l.append(n*10+n%10+1)
    return l
k = int(input())
list = [1,2,3,4,5,6,7,8,9]
i = 0
while(len(list)<k):
    list += add(list[i])
    i += 1
print(list[k-1])

Submission status: Accepted

Solution code:
K = int(input())

q = [1,2,3,4,5,6,7,8,9]
i = 0
n = 9
while n < K:
    x = q[i]
    m = x % 10
    if m > 0:
        q.append(x * 10 + m - 1)
        n += 1
    q.append(x * 10 + m)
    n += 1
    if m < 9:
        q.append(x * 10 + m + 1)
        n += 1
    i += 1
print(q[K-1])

Submission status: Accepted

Solution code:
import queue
K = int(input())
number = queue.Queue()
number_list = list()
for i in range(1, 10):
    number.put(i)
    number_list.append(i)
vector = [-1, 0, 1]
while len(number_list) <= K:
    n = number.get()
    amari = n % 10
    for v in vector:
        dn = amari + v
        N = n * 10 + dn
        if 0 <= dn <= 9:
            number.put(N)
            number_list.append(N)

print(number_list[K-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
q = deque([9,8,7,6,5,4,3,2,1])
while K>1:
    a = q.pop()
    if a % 10 != 0:
        q.appendleft(10*a + ((a%10)-1))
    q.appendleft(10*a + a%10)
    if a % 10 != 9:
        q.appendleft(10*a + ((a%10)+1))
    K -= 1

print(q.pop())

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
q = deque(list(range(1, 10)))
ans = 0
for _ in range(K):
  ans = q.popleft()
  if ans % 10 != 0:
    q.append(ans*10+ans%10-1)
  q.append(ans*10+ans%10)
  if ans % 10 != 9:
    q.append(ans*10+ans%10+1)
print(ans)

Submission status: Accepted

Solution code:
k = int(input())

# キュー
from collections import deque

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

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

print(tmp)

Submission status: Accepted

Solution code:
from queue import Queue


def solve():

    K = int(input())

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
K = int(input())
lunlun = []

for i in range(1,10):
    lunlun.append(i)
for i in lunlun:
    if len(lunlun)>K:
        break
    x = i % 10
    for j in range(max(0,x-1), min(x+2,10)):
        lunlun.append(i*10+j)
 
print(lunlun[K-1])

Submission status: Accepted

Solution code:
def d():
    k = int(input())

    val = 0
    hits = 0
    hit_tails = {}
    while hits < k:
        val += 1
        if len(str(val)) == 1:
            hits += 1
            hit_tails[val] = int(str(val)[-1])
            # print('====', hits, val)
            pass
        else:
            lst = list(map(int, str(val)))
            # print('before:', lst)
            for i in range(len(lst) - 1):
                if lst[i] > lst[i+1] + 1:
                    lst[i+1] = lst[i] - 2
                    if(i < len(lst) - 2):
                        lst[i+2:] = [9] * len(lst[i+2:])
                    val = int(''.join(map(str, lst)))
                    # print('after1:', lst)
                    break
                elif lst[i] < lst[i+1] - 1:
                    lst[i+1:] = [9] * len(lst[i+1:])
                    val = int(''.join(map(str, lst)))
                    # print('after2:', lst)
                    break
                elif i == len(lst) - 2:
                    hits += 1
                    hit_tails[val] = int(str(val)[-1])
                    # print('====', hits, val)
                    pass

    print(val)


##########
if __name__ == "__main__":
    d()

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

cnt = 1

while cnt < K:
    c = q.popleft()
    if c % 10 != 0:
        q.append(c * 10 + c % 10 - 1)
    q.append(c * 10 + c % 10)
    if c % 10 != 9:
        q.append(c * 10 + c % 10 + 1)
    cnt += 1

print(q.popleft())