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 collections import deque
def runrun():
    count = 0
    while count <= k:
        run = quee.popleft()
        count += 1
        if count == k:
            print(run)
        last_digit = run%10
        if 0 < last_digit < 9:
            quee.extend([run * 10 + last_digit-1 , run * 10 + last_digit, run*10 + last_digit + 1])
        elif last_digit == 0:
            quee.extend([run * 10, run * 10 + 1])
        elif last_digit ==9:
            quee.extend([run*10 + 8, run*10 + 9])


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

Submission status: Accepted

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

    K = int(input())

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

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

        r = x % 10
        if r > 0:
            dq.append(x * 10 + r - 1)
        dq.append(x * 10 + r)
        if r < 9:
            dq.append(x * 10 + r + 1)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
k = int(input())
lunlun = list(range(1, 10))

for i in range(k - 1):
    a = lunlun[i]
    b = a * 10 + a % 10
    if a % 10 != 0:
        lunlun.append(b - 1)
    lunlun.append(b)
    if a % 10 != 9:
        lunlun.append(b + 1)
print(lunlun[k - 1])

Submission status: Accepted

Solution code:
k = int(input())
lunlun = list(range(1, 10))
 
for i in range(k-1):
    a = lunlun[i]
    b = a * 10 +  a % 10 
    if a % 10 != 0:
        lunlun.append(b - 1)
    lunlun.append(b)
    if a % 10 != 9:
        lunlun.append(b + 1)
 
print(lunlun[k-1])

Submission status: Accepted

Solution code:
def dfs(s,l):
  if s!="":
    if len(s)>10 or s[0]=="0":
      return
  if s!="":
    l.append(int(s))
  for c in "0123456789":
    if s!="":
      if abs(int(s[-1])-int(c))<=1:
        dfs(s+c,l)
    else:
      if c!="0":
        dfs(s+c,l)

k=int(input())
l=[]
dfs("",l)
l.sort()
print(l[k-1])

Submission status: Accepted

Solution code:
from collections import deque


K = int(input())

que = deque(["1","2","3","4","5","6","7","8","9"])
cnt = 0
while cnt < K:
    q = que.popleft()
    a = int(q[-1])
    q = int(q)
    cnt += 1 
    if a == 0:
        que.append(str(q*10+a))
        que.append(str(q*10+a+1))
    elif a == 9:
        que.append(str(q*10+a-1))
        que.append(str(q*10+a))
    else:
        que.append(str(q*10+a-1))
        que.append(str(q*10+a))
        que.append(str(q*10+a+1))
    ans = q

print(ans)

Submission status: Accepted

Solution code:
k = int(input())
pool = [i for i in range(1,10)]
i = 0
while len(pool) < k:
    n = int(str(pool[i]) + str(pool[i])[-1])
    if n%10 == 0:
        pool += [n, n+1]
    elif n%10 == 9:
        pool += [n-1, n]
    else:
        pool += [n-1, n, n+1]
    i += 1
print(pool[k-1])

Submission status: Accepted

Solution code:
k = int(input())
lunlun = list(range(1, 10))

for i in range(k-1):
    a = lunlun[i]
    b = a * 10 +  a % 10 
    if a % 10 != 0:
        lunlun.append(b - 1)
    lunlun.append(b)
    if a % 10 != 9:
        lunlun.append(b + 1)

print(lunlun[k-1])

Submission status: Accepted

Solution code:
from collections import deque

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

Submission status: Accepted

Solution code:
K = int(input())
start = 1

DP = [[1 for i in range(10)] for j in range(12)]

# 下からの桁数
for j in range(1, 12):
    # その位の数
    for i in range(10):
        DP[j][i] = DP[j-1][i]
        if i != 0:
            DP[j][i] += DP[j-1][i-1]
        if i != 9:
            DP[j][i] += DP[j-1][i+1]
s = 0
# 後ろから考える
res = ""
for j in range(12):
    for i in range(1, 10):
        prev = s
        s += DP[j][i]
        if s >= K:
            res += str(i)
            # print(i, j)
            break
    if s >= K:
        break

top = i
keta = j
sa = K - prev
for k in range(keta-1, -1, -1):
    t = 0
    for j in range(max(0, top-1), min(9, top+1)+1):
        # print("kj", k, j)
        t_prev = t
        t += DP[k][j]
        if t >= sa:
            res += str(j)
            sa -= t_prev
            top = j
            break
print(res)

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    LL = set()

    def dfs(s):
        if 3234566667 < int(s):
            return
        c = int(s[-1])
        for p in range(-1, 2):
            if c+p < 0 or 9 < c+p:
                continue
            LL.add(int(s+str(c+p)))
            dfs(s+str(c+p))

    for s in "123456789":
        LL.add(int(s))
        dfs(s)

    ans = sorted(LL)
    print(ans[K-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def generate(num):
    n = int(str(num)[-1])
    if n != 0:
        yield num * 10 + n - 1
    yield num * 10 + n
    if n < 9:
        yield num * 10 + n + 1

k = int(input())
lunlun = [i for i  in range(1, 10)]
p = 0
while len(lunlun) < k:
    for l in generate(lunlun[p]):
        lunlun.append(l)
    p += 1
print(lunlun[k - 1])

Submission status: Accepted

Solution code:
import queue

k=int(input())

cnt=0
q=queue.Queue()

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

while True:
    dq=q.get()
    if dq%10!=0:
        q.put(10*dq+dq%10-1)
    q.put(10*dq+dq%10)
    if dq%10!=9:
        q.put(10*dq+dq%10+1)
    cnt+=1
    if cnt==k:
        print(dq)
        break

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(x*10)
        q.append(x*10+1)
    elif r == 9:
        q.append(x*10+8)
        q.append(x*10+9)

    else:
        q.append(x*10+r-1)
        q.append(x*10+r)
        q.append(x*10+r+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
sys.setrecursionlimit(10 ** 7)

k = int(readline())
q = [(i + 1) for i in range(9)]
if k < 10:
    print(k)
    exit()
cnt = 9
while q:
    x = q.pop(0)
    y = int(str(x)[-1])
    if y != 0:
        cnt += 1
        if cnt == k:
            print(10 * x + y - 1)
            exit()
        q.append(10 * x + y - 1)
    cnt += 1
    if cnt == k:
        print(10 * x + y)
        exit()
    q.append(10 * x + y)
    if y != 9:
        cnt += 1
        if cnt == k:
            print(10 * x + y + 1)
            exit()
        q.append(10 * x + y + 1)

Submission status: Accepted

Solution code:
K=int(input())

#now: str
def bfs():
  
  q=[""]
  count=0
  while count<K:
    now=q.pop(0)
    if now=="":
      for n in range(1,10):
        new=now+str(n)
        q.append(new)
        count+=1
        if count==K:
          return new
    elif now[-1]=="0":
      for n in ["0","1"]:
        new=now+n
        q.append(new)
        count+=1
        if count==K:
          return new
    elif now[-1]=="9":
      for n in ["8","9"]:
        new=now+n
        q.append(new)
        count+=1
        if count==K:
          return new
    else:
      s=int(now[-1])
      for n in [s-1,s,s+1]:
        new=now+str(n)
        q.append(new)
        count+=1
        if count==K:
          return new
      
print(bfs())

Submission status: Accepted

Solution code:
def dfs(n):
    if int(n) >= 3234566668:
        return None
    else:
        li.append(int(n))
        if n[-1] == "0":
            dfs(n + n[-1])
            dfs(n + str(int(n[-1]) + 1))
        elif n[-1] == "9":
            dfs(n + str(int(n[-1]) - 1))
            dfs(n + n[-1])
        else:
            dfs(n + str(int(n[-1]) - 1))
            dfs(n + n[-1])
            dfs(n + str(int(n[-1]) + 1))
k = int(input())
l = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
li = []
for i in l:
    dfs(i)
li.sort()
print(li[k - 1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

que=deque([1,2,3,4,5,6,7,8,9])
lunlun=deque([])
while len(lunlun)<10**5:
    p=que.popleft()
    lunlun.append(p)
    if p%10!=0:
        que.append(p*10+(p%10-1))
    que.append(p*10+(p%10))
    if p%10!=9:
        que.append(p*10+(p%10+1))

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

Submission status: Accepted

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

Submission status: Accepted

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

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

while stack:
    n = stack.pop()
    count += 1
    if count == K:
        print(n)
        break
    if n%10 != 0:
        stack.appendleft(n*10+n%10-1)
    
    stack.appendleft(n*10+n%10)

    if n%10 != 9:
        stack.appendleft(n*10+n%10+1)

Submission status: Accepted

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

q = collections.deque([i for i in range(1, 10)])
count = 0
while(q):
    count += 1
    x = q.popleft()
    if count == K:
        print(x)
        break
    if x % 10 != 0:
        q.append(x*10 + (x % 10 - 1))
    q.append(x*10 + (x % 10))
    if x % 10 != 9:
        q.append(x*10 + (x % 10 + 1))

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

cnt  = 0


while q:
    x = q.popleft()

    cnt += 1
    if cnt == K:
        print(x)
        break

    y = x % 10
    z = 10*x+y
    if y != 0:
        q.append(z-1)
    q.append(z)
    if y != 9:
        q.append(z+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import deque
k=int(input())
ans=[]
d=deque([1,2,3,4,5,6,7,8,9])
c=0
while c<100100:
    q=d.popleft()
    ans.append(q)
    c+=1
    b=q%10
    if b!=0:
        d.append(q*10+b-1)
    d.append(q*10+b)
    if b!=9:
        d.append(q*10+b+1)
    
print(ans[k-1])

Submission status: Accepted

Solution code:
# import sys
# import math #sqrt,gcd
# import decimal
import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

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

def main():
    k = int(input())
    q = queue.Queue()
    for i in range(1,10):
        q.put(i)
    while not q.empty():
        x = q.get()
        k -= 1
        if k==0:
            print(x)
            return
        if x%10==0:
            q.put(x*10+(x%10))
            q.put(x*10+(x%10+1))
        elif x%10==9:
            q.put(x*10+(x%10-1))
            q.put(x*10+(x%10))
        else:
            q.put(x*10+(x%10-1))
            q.put(x*10+(x%10))
            q.put(x*10+(x%10+1))
    return

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import deque
k=int(input())
ans=[]
d=deque([1,2,3,4,5,6,7,8,9])
c=0
while c<11:
    q=d.popleft()
    ans.append(q)
    c=len(str(q))
    b=q%10
    if b!=0:
        d.append(q*10+b-1)
    d.append(q*10+b)
    if b!=9:
        d.append(q*10+b+1)
    
print(ans[k-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

K = I()
d = deque([i for i in range(1,10)])

cnt = 0
while True:
  num = d.popleft()
  cnt += 1
  if cnt == K:
    print(num)
    break
  tmp = int(str(num)[-1])
  for i in range(tmp-1,tmp+2):
    if i == -1 or i == 10:
      continue
    else:
      d.append(str(num) + str(i))

Submission status: Accepted

Solution code:
import sys
from collections import deque
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

lunlun=deque()

def dfs(now):
    if len(now)>10:return
    lunlun.append(int(now))
    l=now[-1]
    
    if l!="0":
        dfs(now+str(int(l)-1))
    if l!="9":
        dfs(now+str(int(l)+1))
    dfs(now+l)

k=int(input().rstrip())
for i in range(1,10):
    dfs(str(i))


print(sorted(lunlun)[k-1])

Submission status: Accepted

Solution code:
k = int(input())

num_list = [1,2,3,4,5,6,7,8,9]
num_a = ['0', '1']
num_b = ['8', '9']

for i in num_list:
    if str(i)[-1] == '0':
        for j in num_a:
            num_list.append(int(str(i)+j))
    elif str(i)[-1] == '9':
        for j in num_b:
            num_list.append(int(str(i)+j))
    else:
        num = int(str(i)[-1])
        for j in range(num-1, num+2):
            num_list.append(int(str(i)+str(j)))
    if len(num_list) > k:
        break

print(num_list[k-1])

Submission status: Accepted

Solution code:
K = int(input())

import queue
q = queue.Queue()

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

cnt = 0

while True:
    n = q.get()
    cnt += 1
    if cnt == K:
        break
    if n % 10 != 0:
        q.put(n * 10 + n % 10 - 1)
    q.put(n * 10 + n % 10)
    if n % 10 != 9:
        q.put(n * 10 + n % 10 + 1)
print(n)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

k = int(input())
ans = []
def dfs(string):
  if int(string) > 3234566667: return
  ans.append(int(string))
  botom = string[-1]
  intbotom = int(botom)
  if 0 <= intbotom -1 :
    dfs(string + str(intbotom-1))
  dfs(string+botom)
  if intbotom + 1 <= 9:
    dfs(string + str(intbotom+1))
for i in range(1,10):
  dfs(str(i))
ans .sort()

print(ans[k-1])

Submission status: Accepted

Solution code:
from collections import deque


def main():
    k = int(input())
    q = deque([i for i in range(1, 10)])
    answer = 0
    for i in range(k):
        now = q.popleft()
        answer = now
        if now % 10 != 0:
            q.append(10 * now + now % 10 - 1)
        q.append(10 * now + now % 10)
        if now % 10 != 9:
            q.append(10 * now + now % 10 + 1)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k = int(input())


ansl = []
def dfs(s):
    if len(s) == 12:
        return
    ansl.append(int(s))
    if s[-1] != "0":
        dfs(s + str(int(s[-1]) - 1))
    dfs(s+s[-1])
    if s[-1] != "9":
        dfs(s + str(int(s[-1]) + 1))

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

ansl = sorted(ansl)
print(ansl[k-1])

Submission status: Accepted

Solution code:
k=int(input())
a,b,c=['1','2','3','4','5','6','7','8','9'],[],[]
for i in range(10):
    c.extend(a)
    for j in range(len(a)):
        if int(a[j])>323456666:
            continue
        if a[j][-1]!='0':
            b.append(a[j]+str(int(a[j][-1])-1))
        b.append(a[j]+a[j][-1])
        if a[j][-1]!='9':
            b.append(a[j]+str(int(a[j][-1])+1))
    a=b
    b=[]
c.extend(a)
print(sorted(list(map(int,c)))[k-1])

Submission status: Accepted

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

res = set()
def dfs(x, s):
  global res
  res.add(int("".join(s)))
  if x == 10: return
  for i in range(3):
    if (int(s[-1]) + i - 1) in range(10):
      y = s + [str(int(s[-1]) + i - 1)]
      dfs(x + 1, y)
for i in range(1, 10): dfs(1, [str(i)])
res = sorted(res)
print(res[N - 1])

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

def next_num(n):
    if n == 0:
        return [0, 1]
    elif n == 9:
        return [8, 9]
    else:
        return [n-1, n, n+1]


K = int(input())

lunlun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
heapify(lunlun)

for _ in range(K-1):
    now = heappop(lunlun)
    for i in next_num(int(str(now)[-1])):
        heappush(lunlun, now*10+i)

print(lunlun[0])

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

k = ni()

def bfs():
    q = deque()
    for i in range(1, 10):
        q.append(i)
    cnt = 1
    while len(q):
        p = q.popleft()
        if cnt == k:
            return p
        if p % 10 != 0:
            q.append(p * 10 + (p % 10 - 1))
        q.append(p * 10 + p % 10)
        if p % 10 != 9:
            q.append(p * 10 + (p % 10 + 1))
        cnt += 1

print(bfs())

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    K = int(input())
    q = deque()
    for i in range(9): q.append((i + 1, i + 1))
    lunlun = 1
    while lunlun < K:
        nowNum, lastNum = q.popleft()
        if lastNum > 0: q.append((nowNum * 10 + lastNum - 1, lastNum - 1))
        q.append((nowNum * 10 + lastNum, lastNum))
        if lastNum < 9: q.append((nowNum * 10 + lastNum + 1, lastNum + 1))
        lunlun += 1
    ans, lastNum = q.popleft()
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

que = deque([i for i in range(1, 10)])
ans = []
while len(ans) <= K + 10:
    now = que.popleft()
    ans.append(now)

    b = now % 10
    for i in range(max(0, b - 1), min(10, b + 2)):
        que.append(now * 10 + i)

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

Submission status: Accepted

Solution code:
k = int(input())
que = []
for i in range(1,10):
  que.append(i)
ct = 0
while(len(que) < k):
  ct += 1
  value = que[0]
  que.remove(value)
  for i in [-1,0,1]:
    if 0 <= (value%10) + i and (value%10) + i <= 9:
      tmp = 10*value + (value%10) + i
      que.append(tmp)  
print(que[k-1-ct])

Submission status: Accepted

Solution code:
import queue
def main():
    q = queue.Queue()
    for i in range(1,10):
        q.put(i)
    
    k = int(input())
    q_list = []
    while(len(q_list) <= k):
        value = q.get()
        for i in [-1,0,1]:
            if 0 <= (value%10) + i and (value%10) + i <= 9:
                tmp = 10*value + (value%10) + i
                q.put(tmp)
        q_list.append(value)
    print(q_list[k-1])
    return 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K = int(input())
ans = []
def func(s):
    x = int(s)
    if x <= 3234566667:
        ans.append(x)
        tail = int(s[-1])
        for i in [-1, 0, 1]:
            p = i+tail
            if p not in list(range(10)):
                continue
            func(s+str(p))

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

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

Submission status: Accepted

Solution code:
# D - Lunlun Number

K = int(input())

N = [1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 0

while len(N) < K:
    n = int(str(N[i]) + str(N[i])[-1:])
    if str(n)[-1:] == '0':
        N += [n, n + 1]
    elif str(n)[-1:] == '9':
        N += [n - 1, n]
    else:
        N += [n - 1, n, n + 1]
    i += 1

print(N[K - 1])

Submission status: Accepted

Solution code:
# D - Lunlun Number

K = int(input())
stack = [1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 0
while len(stack) < K:
    first = int(str(stack[i])[-1:])
    if first == 0:
        stack.append(int(str(stack[i]) + str(first)))
        stack.append(int(str(stack[i]) + str(first + 1)))
    elif first == 9:
        stack.append(int(str(stack[i]) + str(first - 1)))
        stack.append(int(str(stack[i]) + str(first)))
    else:
        stack.append(int(str(stack[i]) + str(first - 1)))
        stack.append(int(str(stack[i]) + str(first)))
        stack.append(int(str(stack[i]) + str(first + 1)))        
    i += 1

print(stack[K - 1])

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
cnt=0
ans=0
q=deque()
q.extend([1,2,3,4,5,6,7,8,9])

while(cnt<k):
    ans=q.popleft()
    cnt+=1
#    print(ans,cnt)
    one_digit=ans%10
    if(one_digit==0):
        q.append(int(str(ans) + '0'))
        q.append(int(str(ans) + '1'))
    elif(one_digit==9):
        q.append(int(str(ans) + '8'))
        q.append(int(str(ans) + '9'))
    else:
        q.append(int(str(ans) + str(one_digit-1)))
        q.append(int(str(ans) + str(one_digit)))
        q.append(int(str(ans) + str(one_digit+1)))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
if K <= 9: ans = K
cnt = 9
dq = deque(list(range(1, 10)))

while cnt <= K:
    d = dq.popleft()
    for i in [-1, 0, 1]:
        if d % 10 == 0 and i == -1:continue
        if d % 10 == 9 and i == 1:continue
        dq.append(d * 10 + d % 10 + i)
        cnt += 1
        if cnt == K:
            ans = d * 10 + d % 10 + i
            break
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(str, (range(1, 10))))
total = a[:]
cnt = 9
while cnt < n:
    new = []
    for i in a:
        if i[-1] == "0":
            new.append(i + "0")
            new.append(i + "1")
            cnt += 2
            if cnt >= n:
                break
        elif i[-1] == "9":
            new.append(i + "8")
            new.append(i + "9")
            cnt += 2
            if cnt >= n:
                break
        else:
            new.append(i + str(int(i[-1]) -1))
            new.append(i + str(int(i[-1])))
            new.append(i + str(int(i[-1]) + 1))
            cnt += 3
            if cnt >= n:
                break
    total += new[:]
    a = new[:]
                
print(total[n-1])

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline
from collections import deque

def main():
    K = int(input())
    q = deque([])               #キュー
    for i in range(1,10):
        q.append(i) #初期値一桁のlunlun 1-9を登録
    ret = []
    while len(ret)<K:
        p = q.popleft()         #キュー取りだし（先頭）
        ret.append(p)
        pl = p%10
        if pl >= 1:
            q.append(p*10 + pl-1)
        q.append(p*10 + pl)
        if pl <= 8:
            q.append(p*10 + pl+1)
    print(ret[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import queue
import sys

k=int(input())
q=queue.Queue()
for i in range(1,10):
    q.put(i)
if k<10:
    print(k)
    sys.exit()
i=0
while i!=k:
    i+=1
    now=q.get()
    nowm=now%10
    if nowm!=0 and nowm!=9:
        q.put(now*10+nowm-1)
        q.put(now * 10 + nowm)
        q.put(now * 10 + nowm +1)
    elif nowm==0:
        q.put(now * 10 + nowm)
        q.put(now * 10 + nowm + 1)
    elif nowm==9:
        q.put(now * 10 + nowm - 1)
        q.put(now * 10 + nowm)
print(now)

Submission status: Accepted

Solution code:
k = int(input())
li =[i+1 for i in range(9)]

c = 0
while len(li) < k:
    if li[c]%10 != 0:
        li.append(li[c]*10+li[c]%10-1)
    li.append(li[c]*10+li[c]%10)
    if li[c]%10 != 9:
        li.append(li[c]*10+li[c]%10+1)
    c +=1
    
print(li[k-1])

Submission status: Accepted

Solution code:
def solver(d,num,A):
    A.append(num)
    if d == 10:
        return
    
    for x in range(-1,2):
        add = num%10 + x
        if add >=0 and add <=9:
            solver(d+1,(num*10+add),A)
A =[]
K = int(input())
if K <=9:
    print(K)
else:
    for t in range(1,10):
        solver(1,t,A)
    A.sort()
    print(A[K-1])

Submission status: Accepted

Solution code:
def solve(n):
    Mrepeat = 10
    seedlist = [[str(i+j-1) for i in range(3)] for j in range(10)]
    seedlist[0] = ['0', '1']
    seedlist[9] = ['8', '9']
    numbers = [[] for i in range(Mrepeat + 1)]
    numbers[0] = [i for i in range(1,10)]
    for i in range(Mrepeat):
        for num in numbers[i]:
            for tmp in seedlist[num % 10]:
                numbers[i+1].append(int(str(num) + tmp))
    ans = []
    for i in numbers:
        ans += i
    return ans[n-1]

def main():
    n = int(input())
    print(solve(n))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from queue import Queue

K = int(input())
Q = Queue()

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

lun = -1
for i in range(K):
    x = Q.get()
    # print(x)
    lun = x

    if x % 10 != 0:
        Q.put(10*x + (x%10) -1)
        # print("put1 {}".format(10*x + (x//10) -1))

    Q.put(10*x + (x%10))
    # print("put2 {}".format(10 * x + (x // 10)))

    if x%10 != 9:
        Q.put(10*x + (x%10) + 1)
        # print("put3 {}".format(10 * x + (x // 10) + 1))

# print("SSS")
print(lun)




# AR = []
#
# lun = -1
# count = 0
#
# for i in range(1,10000000000+1):
#     # print(lun)
#     if count == K:
#         break
#
#     if i < 10:
#         lun = i
#         # AR[0] = i
#         count += 1
#     else:
#
#         V = str(i)
#         digit = len(V)
#         absc = 0
#
#         for b in range(digit):
#             if b == 0:
#                 continue
#             elif abs(int(V[b]) - int(V[b-1])) <= 1:
#                 absc +=1
#             else:
#                 break
#
#         if absc == digit-1:
#             lun = i
#             count+=1
#
#
#
# print(lun)

Submission status: Accepted

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

q=Queue()

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

for k in range(K):
    a=q.get()
    #print(a)
    if k!=K-1:
        b=a%10
        for j in range(max(0,b-1),min(9,b+1)+1):
            q.put(int(str(a)+str(j)))
    else:
        print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import queue

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

k = int(input())
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:
N=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)
while N!=1:
    a=q.get()
    b=a%10
    c=[10*a+i for i in range(max(0,b-1),min(10,b+2))]
    for j in c:
        q.put(j)
    N-=1
print(q.get())

Submission status: Accepted

Solution code:
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)
N=int(input())
for i in range(N):
    a=q.get()
    b=a%10
    if b!=0:
        q.put(10*a+b-1)
    q.put(10*a+b)
    if b!=9:
        q.put(10*a+b+1)
print(a)

Submission status: Accepted

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

def main():
    K = int(input())
    if 0<=K<=10:
        print(K)
        exit()

    lunlun = [i for i in range(1,10)]
    m = 0

    while len(lunlun) < K:
        x = lunlun[m]
        btm = x % 10

        if btm - 1 >= 0:
            lunlun.append(10*x+btm-1)

        lunlun.append(10*x+btm)

        if btm + 1 < 10:
            lunlun.append(10*x+btm+1)

        m += 1

    print(lunlun[::-1][len(lunlun)-K])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def get_lcm(num):
    return reduce(lambda x,y:(x * y) // fractions.gcd(x, y), num, 1)

def main():
    K = int(input())
    if 0<=K<=10:
        print(K)
        exit()

    lunlun = [i for i in range(1,10)]
    m = 0

    while len(lunlun) < K:
        x = lunlun[m]
        btm = x % 10

        if btm - 1 >= 0:
            lunlun.append(10*x+btm-1)

        lunlun.append(10*x+btm)

        if btm + 1 < 10:
            lunlun.append(10*x+btm+1)

        m += 1

    print(lunlun[::-1][len(lunlun)-K])

if __name__ == "__main__":
  main()