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
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

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

K=II()
for i in range(K-1):
    v = deq.popleft()
    last = v % 10
    if last == 0:
        deq.append(10*v)
        deq.append(10*v + 1)
    elif last == 9:
        deq.append(10*v + 8)
        deq.append(10*v + 9)
    else:
        deq.append(10*v + last-1)
        deq.append(10*v + last)
        deq.append(10*v + last+1)

print(deq.popleft())

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

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

K=II()
for i in range(K-1):
    v = deq.popleft()
    last = int(v[-1])
    if last == 0:
        deq.append(v + "0")
        deq.append(v + "1")
    elif last == 9:
        deq.append(v + "8")
        deq.append(v + "9")
    else:
        deq.append("{}{}".format(v, last-1))
        deq.append("{}{}".format(v, last))
        deq.append("{}{}".format(v, last+1))

print(deq.popleft())

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
count = 0

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

while True:
    num = deq.popleft()
    count += 1
    if num % 10 != 0:
        deq.append((10 * num) + (num % 10) - 1)
    deq.append((10 * num) + (num % 10))
    if num % 10 != 9:
        deq.append((10 * num) + (num % 10) + 1)
    
    if count == K:
        ans = num
        break

print(ans)

Submission status: Accepted

Solution code:
k = int(input())

lunlun = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
for i in range(11):
    last = lunlun[-1]
    add = []
    for x in last:
        c = x % 10
        add.append(x*10+c)
        if c != 0:
            add.append(x*10+c-1)
        if c != 9:
            add.append(x*10+c+1)
    lunlun.append(add)

all = []
for i in range(11):
    for x in lunlun[i]:
        all.append(x)
all.sort()
print(all[k-1])

Submission status: Accepted

Solution code:
k = int(input())
n = list(map(str, range(10)))

i = 0
while len(n) < k+1:
    i += 1
    # -1, 0, 1
    for j in range(-1, 2):
        # 一の位
        m = n[i][-1]
        if j == -1 and m == "0":
            continue
        if j == 1 and m == "9":
            break
        p = n[i] + n[int(m)+j]
        n.append(p)


print(n[k])

Submission status: Accepted

Solution code:
k=int(input())
l=[1,2,3,4,5,6,7,8,9]
n=1 #桁数
s=0; e=8 #start&end
p=9
q=9
if k<10:
    print(l[k-1])
else:
    while k>p:
        for m in range(s,e+1):
            I=str(l[m])[n-1] #lの要素の一の位の数
            if I=="0":
                l.append(str(l[m])+"0")
                p+=1
                l.append(str(l[m])+"1")
                p+=1
            elif I != "9":
                l.append(str(l[m])+str(int(I)-1))
                p+=1
                l.append(str(l[m])+str(int(I)))
                p+=1
                l.append(str(l[m])+str(int(I)+1))
                p+=1
            else:
                l.append(str(l[m])+"8")
                p+=1
                l.append(str(l[m])+"9")
                p+=1
        q=p-q
        s=e+1
        e=s+q-1
        q=p
        n+=1

    print(l[k-1])

Submission status: Accepted

Solution code:
K = int(input())

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

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

print(V[K-1])

Submission status: Accepted

Solution code:
from queue import Queue

K = int(input())

q = Queue()

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

for _ in range(K):
    ans = q.get()
    if ans % 10 == 0:
        q.put(ans*10)
        q.put(ans*10+1)
    elif ans % 10 == 9:
        q.put(ans*10+8)
        q.put(ans*10+9)
    else:
        d = ans % 10
        q.put(ans*10+d-1)
        q.put(ans*10+d)
        q.put(ans*10+d+1)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque

K = int(stdin.readline())

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

for i in range(K - 1):
    s = deque.popleft()
    for j in range(-1, 2):
        add = (s % 10) + j
        if 0 <= add <= 9:
            deque.append(s * 10 + add)

print(deque.popleft())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k = int(input())

lun = [[0] * 12 for _ in range(10)]
for i in range(1, 11):
    lun[0][i] = 1
for i in range(1, 10):
    for j in range(1, 11):
        lun[i][j] = lun[i - 1][j - 1] + lun[i - 1][j] + lun[i - 1][j + 1]

res = []
i = 0
start = 1
while k > 0 and i < 10:
    for j in range(start, 11):
        if not res and j == 1:
            continue
        if k == lun[i][j] == 1:
            res.append(j - 1)
            k = 0
            break
        if k > lun[i][j]:
            k -= lun[i][j]
            continue
        res.append(j - 1)
        start = j - 1
        i -= 1
        break
    else:
        i += 1


print(*res, sep="")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import queue
num=int(input())
q=queue.Queue()
for i in range(1,10):
  q.put(i)
for j in range(num):
  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:
K = int(input())
queue = [1,2,3,4,5,6,7,8,9]
i = 0
flag = 1
while(flag==1):
    if K<len(queue):
        flag = 0
        break
    else:
        x = queue[i]
        if x%10 != 0:
            queue.append(x*10+x%10-1)
        queue.append(10*x+x%10)

        if x%10 != 9:
            queue.append(10*x+x%10+1)

    i+=1

print(queue[K-1])

Submission status: Accepted

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

q = queue.Queue()

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


for cnt in range(1, target):
  num = q.get()
  mod = int(num) % 10
  
  if mod == 0:
    q.put(num + "0")
    q.put(num + "1")
  elif mod == 9:
    q.put(num + "8")
    q.put(num + "9")
  else:
    q.put(num + str(mod - 1))
    q.put(num + str(mod))
    q.put(num + str(mod + 1))

print(q.get())

Submission status: Accepted

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

import sys

sys.setrecursionlimit(10 ** 6)

input_line = input()
inputs = input_line.split(' ')
K, = [int(s) for s in inputs]

# 1000

if K<=9:
    print(K)
else:
    pre = list(range(1, 10))
    sp = [0]
    digit = 0
    num = 9
    while True:
        lunluns = []

        for pp in sp:
            num += 1
            lunlun = (10**(digit+1))+pp
            if K==num:
                print(lunlun)
                quit()
            lunluns.append(lunlun)

        for i in range(1, 10):

            for p in pre:
                s = p // (10**digit)
                if i==1 and s==1:
                    sp.append(p)
                if abs(i-s)<=1:
                    num += 1
                    lunlun = i*(10**(digit+1))+p
                    if K==num:
                        print(lunlun)
                        quit()
                    lunluns.append(lunlun)
        pre = lunluns
        digit += 1

Submission status: Accepted

Solution code:
K=int(input())
lunlun=[1,2,3,4,5,6,7,8,9]
flag=1
i=0
if K<10:
  pass
else:
  while flag==1 :
    if len(lunlun)>=K:
        flag=0
        break
    else:
      x=lunlun[i]
      if x % 10 != 0:
        lunlun.append(x*10+x%10-1)
    
      lunlun.append(x*10+x%10)
    
      if x % 10 != 9:
        lunlun.append(x*10+x%10+1) 
	
    i+=1
        
print(lunlun[K-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

dq = deque([])

cnt = 0
for i in range(1, 10):
    dq.append(str(i))


while cnt < K:
    val = dq.popleft()
    cnt += 1

    if cnt == K:
        print(val)
        exit()

    if val[-1] == '0':
        dq.append(val + '0')
        dq.append(val + '1')
    elif val[-1] == '9':
        dq.append(val + '8')
        dq.append(val + '9')
    else:
        prev = int(val[-1]) - 1
        nex = int(val[-1]) + 1

        dq.append(val + str(prev))
        dq.append(val + val[-1])
        dq.append(val + str(nex))

Submission status: Accepted

Solution code:
import queue
K = int(input())
q = queue.Queue()
for k in range(1,10):
    q.put(k)

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

Submission status: Accepted

Solution code:
K=int(input())
queue=[1,2,3,4,5,6,7,8,9]
i=0
flag=1
while(flag==1):
  if K<=len(queue):
    flag=0
    break
  else:

    x=queue[i]
    if x % 10!=0:
      queue.append(x*10+(x%10)-1)
    queue.append(10*x+(x%10))

    if x%10!=9:
      queue.append(10*x+(x%10)+1)
    
  
  i+=1



print(queue[K-1])

Submission status: Accepted

Solution code:
from collections import deque

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

K = int(input())

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

Submission status: Accepted

Solution code:
K = int(input())

from collections import deque

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

for i in range(K-1):
  x = d[0]
  if not x % 10 == 0:
    d.append((10 * x) + (x % 10) - 1)
    
  d.append((10 * x) + (x % 10))
  
  if not x % 10 == 9:
    d.append((10 * x) + (x % 10) + 1)
    
  d.popleft()

print(d[0])

Submission status: Accepted

Solution code:
#123..9 9
#10,11,12,21,22,23...89,98,99 9*3-1
#100,101,110,111,112,121,122,123
#210,211,212,221,222,223,232,233,234
k = int(input())

l = [1,2,3,4,5,6,7,8,9]
for i in range(k):
    a = l[i] % 10
    if a >= 1: 
        l.append(10*l[i] + a - 1)
    l.append(10*l[i] + a)
    if a <= 8:
        l.append(10*l[i] + a + 1)
print(l[k-1])

Submission status: Accepted

Solution code:
import queue

#K = list(map(int, input().split()))
K = int(input())

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

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

Submission status: Accepted

Solution code:
# データ構造queueを用いて解く問題となっている.
from collections import deque
k = int(input())

def solve(k):
    q = deque()
    ans = 0
    for i in range(1,10):
        q.append(i)
    count = 0
    while count < k:
        val = q.popleft()
        tmp = val % 10
        if tmp != 0:
            q.append(10*val + tmp - 1)
        q.append(10*val + tmp)
        if tmp != 9:
            q.append(10*val + tmp + 1)
        ans = val
        count += 1
    return ans
print(solve(k))

Submission status: Accepted

Solution code:
k=int(input())
#n,p=map(int,input().split())
#al=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
#素因数分解した結果を2次元配列にして返す

all_list=[]

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

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

Submission status: Accepted

Solution code:
import queue
import sys

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

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

n = 0
while True:
    n += 1
    val = q.get()
    if n == K:
        print(val)
        sys.exit()

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

Submission status: Accepted

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

def solve(K):
    q = deque()
    for i in range(1, 10):
        q.append(i)
    
    # print(q)
    previousval = 0
    idx = 0
    while(idx < K):
        val = q.popleft()
        rem = val%10
        if rem != 0:
            q.append(10*val + rem - 1)
        q.append(10*val + rem)
        if rem != 9:
            q.append(10*val + rem + 1)
        
        previousval = val
        
        idx += 1
    return previousval

print(solve(K))

Submission status: Accepted

Solution code:
K=int(input())
arr=[[1,2,3,4,5,6,7,8,9]]
for _ in range(9):
    tmp=[]
    for v in arr[-1]:
        if v%10!=0:
            tmp.append(v*10+(v%10-1))
        tmp.append(v*10+(v%10))
        if v%10!=9:
            tmp.append(v*10+(v%10+1))
    arr.append(tmp)
ans=[]
for i in range(len(arr)):
    for v in arr[i]:
        ans.append(v)
ans=sorted(ans)
print(ans[K-1])

Submission status: Accepted

Solution code:
import queue
K = int(input())
q = queue.Queue()
for i in range(1,10):
    q.put(i)

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

Submission status: Accepted

Solution code:
import sys
from math import sqrt
from collections import Counter, defaultdict, deque

input = sys.stdin.readline


def I():
    return int(input())


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


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    k = I()

    q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
    for i in range(1, 10 ** 5 + 1):
        ln = q.popleft()

        if i == k:
            print(ln)
            break

        r = ln % 10
        new_ln = ln * 10 + r
        if r != 0:
            q.append(new_ln - 1)
        q.append(new_ln)
        if r != 9:
            q.append(new_ln + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K = int(input())
num = 0

import itertools

Lun = [[] for _ in range(11)]
Lun[1] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(2, 11):
    for j in Lun[i-1]:
        j_mod = j % 10
        if j_mod != 0:
            Lun[i].append(j * 10 + j_mod - 1)
        Lun[i].append(j * 10 + j_mod)
        if j_mod != 9:
            Lun[i].append(j * 10 + j_mod + 1)

Lunlun = list(itertools.chain.from_iterable(Lun))
print(Lunlun[K-1])

Submission status: Accepted

Solution code:
import collections
ans=[]
s=collections.deque()
k=int(input())
ans.append(1)
for i in range(1,k):
    for x in str(ans[i-1]):
        s.append(int(x))
    ls=len(s)-1
    while ls>=0 and s[ls]==9:
        s[ls]=0
        ls-=1
    if ls==-1:s.appendleft(1)
    else:s[ls]+=1
    while True:
        b=-1
        for i in range(0,len(s)-1):
            if abs(s[i+1]-s[i])>1:
                b=i
                break
        if b==-1:break
        if s[b+1]>s[b]:s[b]+=1
        l=max(s[b]-1,0)
        for i in range(b+1,len(s)):
            s[i]=l
            l=max(l-1,0)
    #print(s)
    t=0
    while len(s)>=1:
        x=s.popleft()
        #print("*",x)
        t=t*10+x
    ans.append(t)
print(ans[k-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import queue


def main():
    K = int(input())
    number_list = queue.Queue()
    for i in range(1, 10):
        number_list.put(i)
    count = 0
    number = 0
    while(count != K):
        number = number_list.get()
        if number % 10 != 0:
            number_list.put((10 * number) + (number % 10) - 1)
        number_list.put(10 * number + number % 10)
        if number % 10 != 9:
            number_list.put(10 * number + (number % 10) + 1)
        count += 1
    print(number)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue

n = int(input())


q = queue.Queue()

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

x = 0
for i in range(n):
    x = q.get()
    l = x % 10
#    print(x,l)
    if l != 0:
        q.put(x*10 + l - 1)
    q.put(x*10 + l)
    if l != 9:
        q.put(x*10 + l + 1)
        
#while not q.empty():
#    print (q.get())
    
print(x)

Submission status: Accepted

Solution code:
K = int(input())

ans = [i + 1 for i in range(9)]

i = 0
while len(ans) <= K:
    s = str(ans[i])
    t = int(s[-1])
    d = [-1, 0, 1]
    if t == 0:
        d = [0, 1]
    elif t == 9:
        d = [-1, 0]

    for x in d:
        ans.append(s + str(t + x))
    i += 1
print(ans[K-1])

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

Submission status: Accepted

Solution code:
# Problem D - Lunlun Number

from collections import deque

# input
K = int(input())

# initialization
num_queue = deque()
k = 1

# count
while True:
    if k>=1 and k<=9:
        num_queue.append(k)
        k += 1
    else:
        num = str(num_queue.popleft())
        num_str = int(num[-1])
        if num_str==0:
            for i in range(2):
                tmp = str(i)
                num_queue.append(int(num + tmp))
                k += 1
                if k-1==K:
                    break
        elif num_str==9:
            for i in range(8,10):
                tmp = str(i)
                num_queue.append(int(num + tmp))
                k += 1
                if k-1==K:
                    break
        else:
            for i in range(num_str-1, num_str+2):
                tmp = str(i)
                num_queue.append(int(num + tmp))
                k += 1
                if k-1==K:
                    break

    if k-1==K:
        break

# output
print(num_queue[-1])

Submission status: Accepted

Solution code:
import heapq
l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
heapq.heapify(l)

def f(x):
    # xの最後の数値だけ取り出す
    min_x = int(list(str(x))[-1])
    x = str(x)
    if min_x == 0:
        yield int(x + "0")
        yield int(x + "1")
    elif min_x == 9:
        yield int(x + "8")
        yield int(x + "9")
    else:
        yield int(x + str(min_x - 1))
        yield int(x + str(min_x))
        yield int(x + str(min_x + 1))

K = int(input())
ans = 1
for i in range(K):
    if i == K - 1:
        ans = heapq.heappop(l)
        break
    for y in f(heapq.heappop(l)):
        heapq.heappush(l, y)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

k = int(input())

q = []

for i in range(9):
    heappush(q, i+1)

for _ in range(k - 1):
    x = heappop(q)
    if x % 10 != 0:
        heappush(q, 10 * x + (x % 10) - 1)
    if x % 10 != 9:
        heappush(q, 10 * x + (x % 10) + 1)
    heappush(q, 10 * x + (x % 10))

print(heappop(q))

Submission status: Accepted

Solution code:
from collections import deque


k = int(input())
d = deque([1,2,3,4,5,6,7,8,9])

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

print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import deque

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

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

print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

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

Submission status: Accepted

Solution code:
import collections

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

K = int(input())

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

Submission status: Accepted

Solution code:
k = int(input())

i = 1
q = []
while i <= k :
    if(i < 10) :
        q.append(i)
    else :
        x = q.pop(0)
        tmp = 10 * x + (x % 10)
        if x % 10 != 0 :
            q.append(tmp-1)
            i+=1
        q.append(tmp)
        if x % 10 != 9 :
            q.append(tmp+1)
            i+=1
    i+=1
print(q.pop(k-i))

Submission status: Accepted

Solution code:
K=int(input())

if K<=10:
    print(K)
else:
    K=K-10
    lun=[n for n in range(1,10)]
    i=0

    for e in lun:

        a=e%10-1
        b=e%10
        c=e%10+1

        if a>=0:
            lun.append(10*e+a)
            i+=1
            if i>K:
                print(lun[-1])
                break

        lun.append(10*e+b)
        i+=1
        if i>K:
            print(lun[-1])
            break

        if c<10:
            lun.append(10*e+c)
            i+=1
            if i>K:
                print(lun[-1])
                break

Submission status: Accepted

Solution code:
K = int(input())
l = [1,2,3,4,5,6,7,8,9]
#while K>0:
#    if len(l) > K:
#        print(l[K-1])
#        break
#    else:
#        K -= len(l)
#        newl = []
#        for i in l:
#            if i%10 == 0:
#                newl.append(10*i)
#                newl.append(10*i + 1)
#                newl.append(10*i + 8)
#                newl.append(10*i + 9)
#            else:
#                newl.append(10*i + i%10 - 1)
#                newl.append(10*i + i%10 )
#                newl.append(10*i + i%10 + 1)
#        l = newl
for i in range(K):
    a = l[i]
    b = a%10
    for j in [b-1, b, b+1]:
        if j<0 or j>9:
            continue
        else:
            l.append(10*a + j)
print(l[K-1])

Submission status: Accepted

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

K = int(input())


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

x = 0
i = 0
# K回繰り返す
while i < K:
    # x = dequeue
    x = q.get()

    one = x % 10
    # xの一桁目が0でなければ(x * 10 + xの一桁目に1加算した値)をenqueue
    if one != 0:
        q.put(x * 10 + one - 1)

    # x * 10をenqueue
    q.put(x * 10 + one)

    # xの一桁目が9でなければ(x * 10 - xの一桁目から1減算した値)をenqueue
    if one != 9:
        q.put(x * 10 + one + 1)

    i += 1

# xが答え
print(x)

Submission status: Accepted

Solution code:
k=int(input())
#a,b=map(int,input().split())
#l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

from collections import deque

q=deque([1,2,3,4,5,6,7,8,9])
ansl=[]
s=1
while len(str(s))<=10:
    s=q.popleft()
    ansl.append(s)
    sl=list(str(s))
    last_digit=int(sl[-1])
    for digit in range(max(0,last_digit-1),min(last_digit+1,9)+1):
        newval=int(str(s)+str(digit))
        #ansl.append(int(str(s)+str(digit)))
        q.append(newval)
print(ansl[k-1])

Submission status: Accepted

Solution code:
K = int(input())
l = [1,2,3,4,5,6,7,8,9]
while K>0:
    if len(l) > K:
        print(l[K-1])
        break
    else:
        K -= len(l)
        newl = []
        for i in l:
            if i%10 == 0:
                newl.append(10*i)
                newl.append(10*i + 1)
            elif i%10 == 9:
                newl.append(10*i + 8)
                newl.append(10*i + 9)
            else:
                newl.append(10*i + i%10 - 1)
                newl.append(10*i + i%10 )
                newl.append(10*i + i%10 + 1)
        l = newl

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
a = deque([1,2,3,4,5,6,7,8,9])
count=0
while count !=k:
  b = a.popleft()
  count += 1
  if b%10==0:
    a.append(b*10)
    a.append(b*10+1)
  elif b%10==9:
    a.append(b*10+8)
    a.append(b*10+9)
  else:
    a.append(b*10+b%10-1)
    a.append(b*10+b%10)
    a.append(b*10+b%10+1)
print(b)

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
queue = deque()
for i in range(1,10):
    queue.append(i)
#print(queue)
#queue = [1,2,3,4,5,6,7,8,9]
x = 0
for i in range(k):
    x = queue.popleft()
    #print(x)
    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:
from collections import deque

def main():
    K = int(input())
    
    # bfs
    q = deque(range(1, 10))
    for _  in range(K-1):
        now = q.popleft()
        d1 = now % 10
        base = 10 * now
        
        for suffix in [d1 - 1, d1, d1 + 1]:
            if suffix not in [-1, 10]:
                new = base + suffix
                q.append(new)

    ans = q.popleft()
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    K = int(input())
    
    # bfs
    count = 0
    q = deque(range(1, 10))
    while count < K-1:
        now = q.popleft()
        count += 1

        d1 = now % 10
        base = 10 * now
        for suffix in [d1 - 1, d1, d1 + 1]:
            if suffix not in [-1, 10]:
                new = base + suffix
                q.append(new)

    ans = q.popleft()
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k=int(input())
a=[i+1 for i in range(9)]
while (1):
  if k<=len(a):
    print(a[k-1])
    f=1
    break
  
  k=k-len(a)
  #print(k)
  b=[]
  for x in a:
    for i in [-1,0,1]:
      d=x%10+i
      #print(d)
      if d<0 or d>=10: continue
      b.append(x*10+d)
  a=b.copy()
  #print(a)

Submission status: Accepted

Solution code:
import queue

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

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:
k=int(input())
a=[]
def judge(x):
    if x> 3234566667:
        return
    a.append(x)
    for i in range(10):
        if abs(x%10-i)<=1:
            judge(x*10+i)

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
K = int(input())
RUN = {
    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]
}
cnt = -1

def dfs(i, s, p, cnt):
    if i == 0:
        cnt += 1
        if cnt == K:
            print(s)
            exit()
        else:
            return cnt
    if s == 0:
        for ii in range(10):
            cnt = dfs(i-1, s+ii*10**(i-1), ii, cnt)
    else:
        for ii in RUN[p]:
            cnt = dfs(i-1, s+ii*10**(i-1), ii, cnt)

    return cnt

dfs(10, 0, 0, cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
K = int(input())
RUN = {
    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]
}
cnt = 0

def dfs(i, s, p, cnt):
    if i == 0:
        if s == 0:
            return cnt        
        cnt += 1
        if cnt == K:
            print(s)
            exit()
        else:
            return cnt
    if s == 0:
        for ii in range(10):
            cnt = dfs(i-1, s+ii*10**(i-1), ii, cnt)
    else:
        for ii in RUN[p]:
            cnt = dfs(i-1, s+ii*10**(i-1), ii, cnt)

    return cnt

dfs(10, 0, 0, cnt)

Submission status: Accepted

Solution code:
k=int(input())

from heapq import heappush, heappop,heappushpop,heapify
ans=[1,2,3,4,5,6,7,8,9]
heapify(ans)

a=0
for i in range(k):
    a=heappop(ans)
    md=a%10
    if md != 0:
        heappush(ans,10*a + md-1)
    if md != 9:
        heappush(ans,10*a + md+1)
    heappush(ans,10*a+md)
print(a)