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:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)


def main():
    K = I()
    q = deque()
    for i in range(1, 10):
        q.append(i)
    for _ in range(K):
        x = q.popleft()
        if x % 10 != 0:
            q.append(10 * x + x % 10 - 1)
        q.append(10 * x + x % 10)
        if x % 10 != 9:
            q.append(10 * x + x % 10 + 1)
    print(x)


main()

Submission status: Accepted

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

def dfs(d,now,lunluns):
    lunluns.append(now)

    if d == 10:
        return
    
    for i in [-1,0,1]:
        add = now % 10 + i

        if 0 <= add <= 9:
            dfs(d+1,now*10+add, lunluns)
        
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque
def bfs(k):
    lunlun = []
    q = deque()
    count = 0
    for i in range(1, 10):
        lunlun.append(i)
        q.append(i)
        count += 1

    if count >= k:return lunlun[k - 1]

    while True:
        num = q.popleft()
        tail = num % 10
        for i in [-1, 0, 1]:
            temp = tail + i
            if temp == -1 or temp == 10:continue
            q.append(num * 10 + temp)
            lunlun.append(num * 10 + temp)
            count += 1
            if k == count:return lunlun[k - 1]

k = int(input())
print(bfs(k))

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())

if n < 10:
    print(n)
else:
    check_box = deque([1,2,3,4,5,6,7,8,9])
    check_num = 9
    while True:
        add_num = check_box.popleft()
        add_num = str(add_num)

        if int(add_num[-1]) - 1 >= 0:
            check_box.append(int(add_num + str(int(add_num[-1]) - 1)))
            check_num += 1
            if check_num == n:
                    print(add_num + str(int(add_num[-1]) - 1))
                    exit()

        check_num += 1
        check_box.append(int(add_num + add_num[-1]))
        if check_num == n:
                print(add_num + add_num[-1])
                exit()

        if int(add_num[-1]) + 1 <= 9:
            check_box.append(int(add_num + str(int(add_num[-1]) + 1)))
            check_num += 1
            if check_num == n:
                    print(add_num + str(int(add_num[-1]) + 1))
                    exit()

Submission status: Accepted

Solution code:
K = int(input())

l = []

def c(depth, a, d):
    ans = 0
    if depth == d:
        l.append(a)
        return
    if int(a[-1]) - 1 >= 0:
        c(depth + 1, a + str(int(a[-1]) - 1), d)
    c(depth + 1, a + a[-1], d)
    if int(a[-1]) + 1 <= 9:
        c(depth + 1, a + str(int(a[-1]) + 1), d)
    return

for d in range(10):
    for i in range(1, 10):
        c(0, str(i), d)
        
print(l[K - 1])

Submission status: Accepted

Solution code:
k = int(input())

al = []
def f(d, v, al):
    
    al.append(v)
    
    if d == 10:
        return
    
    for i in range(-1,2):
        add = (v%10) + i
        if add >= 0 and add <= 9:
            f(d+1, v*10+add, al)
            
            
for i in range(1,10):
    f(0, i, al)
    
al = sorted(al)

print(al[k-1])

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

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())-10
q=deque(range(1,10))
while n>=0:
    a=str(q.popleft())
    a=int(a+a[-1])
    for i in range(a-1,a+2):
        if str(i)[-2]==str(a)[-1]:
            q.append(i)
            n-=1
print(q[n])
#print(q,n)

Submission status: Accepted

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

def SUM(num,cnt,keta):
    global luncnt
    if luncnt > 10**5:
        return
    if int(cnt) > int(keta):
        lunlun.append(int(num))
        luncnt += 1
        return


    if len(num) == 0:
        for i in range(1,10):
            SUM(num+str(i),str(int(cnt)+1),keta)
    else:
        min = int(num[(len(num)-1)])-1
        max = min + 3
        for i in range(min,max):
            if i < 0 or i > 9:
                continue
            SUM(num+str(i),str(int(cnt)+1),keta)

keta = 0
while True:
    SUM('','0',str(keta))
    if luncnt > 10**5:
        break
    keta += 1

print(lunlun[K-1])

Submission status: Accepted

Solution code:
k=int(input())

def dfs(keta, val):
  lunlun.append(val)

  if keta==10:
    return

  for i in range(-1,2):
    add=(val%10)+i
    if 0<=add<=9:
      dfs(keta+1, val*10+add)

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

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

Submission status: Accepted

Solution code:
k=int(input())
from collections import deque
q=deque([])
i=0
while True:
  if i<=8:
    q.append(i+1)
    i+=1
    if i==k:break
    continue
  
  x=q.popleft()
  
  if x%10!=0:
    q.append(x*10+x%10-1)
    i+=1
    if i==k:break
    
  q.append(x*10+x%10)
  i+=1
  if i==k:break
  
  if x%10!=9:
    q.append(x*10+x%10+1)
    i+=1
    if i==k:break
      
print(q.pop())

Submission status: Accepted

Solution code:
K = int(input())

#再帰で実装できそう？

memo = set([])

PM = [-1,0,1]

def rec(n):
    if n > 3234566667:
        return
    ichi = n % 10
    for pm in PM:
        if (ichi + pm) != -1 and (ichi + pm) != 10:
            m = n*10 + ichi + pm
            if m not in memo:
                # print(m)
                # if m == 9900:
                #     print(n,ichi + pm)
                memo.add(m)
                rec(m)
    return

for i in range(1,10):
    memo.add(i)
    rec(i)



# rec(9)



memo = list(memo)
memo.sort()

# print(memo[:100])
# print(len(memo))
            
print(memo[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 i in range(k):
    x = q.get()
    if x % 10 != 0:
        num = 10 * x + (x % 10) - 1
        q.put(num)
    num = 10 * x + (x % 10)
    q.put(num)
    if x % 10 != 9:
        num = 10 * x + (x % 10) + 1
        q.put(num)
print(x)

Submission status: Accepted

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

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

for i in range(1,K+1):
    ans = X.popleft()
    if ans%10!=0:
        temp = ans*10 + (ans%10)-1
        X.append(temp)

    temp = ans*10 + (ans%10)
    X.append(temp)
    
    if ans%10!=9:
        temp = ans*10 + (ans%10)+1
        X.append(temp)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

if K <= 9:
  print(K)
else:
  for i in range(K):
    num = d[0]
    d.popleft()
    plus = int(10*num + num%10)
    if num % 10 != 0:
      d.append(plus-1)
    d.append(plus)
    if (i<K) and (num%10!=9):
      d.append(plus+1)
  print(num)

Submission status: Accepted

Solution code:
from functools import lru_cache

(K,) = [int(x) for x in input().split()]


def solve(K):
    def getNext(x):
        if x == 0:
            return [0, 1]
        if x == 9:
            return [8, 9]
        return [x - 1, x, x + 1]

    @lru_cache(maxsize=None)
    def getNum(begin, digits):
        if digits == 0:
            assert False
            return 0
        if digits == 1:
            return 1
        ans = 0
        for x in getNext(begin):
            ans += getNum(x, digits - 1)
        return ans

    ans = []
    count = 0
    for digits in range(1, 30):
        for i in range(1, 10):
            delta = getNum(i, digits)
            if count < K <= count + delta:
                ans.append(i)
                while digits > 1:
                    for x in getNext(ans[-1]):
                        delta = getNum(x, digits - 1)
                        if count < K <= count + delta:
                            ans.append(x)
                            digits -= 1
                            break
                        count += delta
                return "".join(map(str, ans))

            count += delta


print(solve(K))

Submission status: Accepted

Solution code:
K = int(input())
l = list(range(1,10))

for x in l:
    if x > 3234566667: break
    back = int(str(x)[-1])
    for b in [back-1, back, back+1]:
        if 0 <= b <= 9:
            l.append(10*x + b)

print(l[K-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


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


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


K = z()
lunlun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
if (K <= 9):
    print(lunlun[K-1])
    exit()
while len(lunlun) < K:
    for lun in lunlun:
        right = int(str(lun)[-1])
        if (right == 0):
            add = [0, 1]
        elif (right == 9):
            add = [8, 9]
        else:
            add = [right-1, right, right+1]
        for ad in add:
            # print(lun*10 + ad)
            lunlun.append(lun * 10 + ad)
        if (len(lunlun) >= K):
            break_flg = True
            break

# print(lunlun)
print(lunlun[K-1])

Submission status: Accepted

Solution code:
K = int(input())
ans_list = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
nex = ans_list.copy()


def resp(n):
    if n == "0":
        return ["0", "1"]
    elif n == "9":
        return ["8", "9"]
    else:
        n_tmp = int(n)
        return [n, str(n_tmp + 1), str(n_tmp - 1)]


for j in range(1000):
    tmp = nex.copy()
    nex = []
    for i in tmp:
        nex += [i + x for x in resp(i[-1])]
    ans_list += nex
    if len(ans_list) > 10 ** 5:
        break

ans_list = list(map(int, ans_list))
ans_list.sort()
print(ans_list[K - 1])

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
def solve():
  count = 0
  stack_strings = deque([str(i) for i in range(9, -1, -1)])
  for _ in range(10):
    for _ in range(len(stack_strings)):
      lunstring = stack_strings.pop()
      if lunstring[0] != "0":
        count += 1
        if count == k:
          return(int(lunstring))
      right_char = lunstring[-1]
      if right_char == "0":
        [stack_strings.appendleft(lunstring+x) for x in ["0", "1"]]
      elif right_char == "9":
        [stack_strings.appendleft(lunstring+x) for x in ["8", "9"]]
      else:
        [stack_strings.appendleft(lunstring+x) for x in [str(int(right_char)-1), right_char, str(int(right_char)+1)]]
print(solve())

Submission status: Accepted

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

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

print(x)

Submission status: Accepted

Solution code:
# 初期入力
from copy import copy
K = int(input())

#
lunlun_start =["1","2","3","4","5","6","7","8","9"]
lunlun_roop =copy(lunlun_start)
lunlun =[]
ans =copy(lunlun_start)
x=""
while len(ans) <K:
#for i in range(1,10):
    lunlun =[]
    for i in lunlun_roop:
        if i[-1] =="0":
            lunlun.append(i+"0")
            lunlun.append(i+"1")
        elif i[-1] =="9":
            lunlun.append(i+"8")
            lunlun.append(i+"9")
        else:
            x =int(i+i[-1])-1
            lunlun.append((str(x) ))
            x +=1
            lunlun.append((str(x) ))
            x +=1
            lunlun.append((str(x) ))
        if len(lunlun) >K:
            break
    lunlun_roop =copy(lunlun)
    ans.extend(lunlun)
print(ans[K-1])

Submission status: Accepted

Solution code:
k = int(input())
from collections import deque
q = deque() # FIFOキューの作成
for i in range(1,10):
    q.append(str(i))


for i in range(k-1):
    a = q.popleft()
    last = int(a[-1:])
    if last == 0:
        q.append(a+"0")
        q.append(a + "1")
    elif last ==9:
        q.append(a+"8")
        q.append(a + "9")
    else:
        q.append(a + str(last - 1))
        q.append(a + str(last ))
        q.append(a + str(last + 1))

print(q.popleft())

Submission status: Accepted

Solution code:
k = int(input())
nums = set()


def rec(past: int, num: int):
    nums.add(num)
    if num > 10**10:
        return
    if past > 0:
        rec(past - 1, num * 10 + past - 1)
    rec(past, num * 10 + past)
    if past < 9:
        rec(past + 1, num * 10 + past + 1)


for i in range(1, 10):
    rec(i, i)
ans = sorted(nums)
print(ans[k - 1])

Submission status: Accepted

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


if __name__ == '__main__':
    main()

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

Submission status: Accepted

Solution code:
from collections import deque
K=int(input())
queue=deque(list(range(1,10)))
for i in range(K):
    k=queue.popleft()
    mod=k%10
    for diff in range(mod-1,mod+2):
        if diff<0 or 9<diff:
            continue
        queue.append(10*k+diff)
print(k)

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    ans = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    count = 9
    if K <= count:
        print(ans[K-1])
    else:
        for x in ans:
            mod = x % 10
            base = 10*x + mod

            if mod != 0:
                ans.append(base-1)
                count += 1

            ans.append(base)
            count += 1

            if mod != 9:
                ans.append(base+1)
                count += 1

            if count >= K:
                break
        print(ans[K-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    ans = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    count = 9
    if K <= count:
        print(ans[K-1])
    else:
        for x in ans:
            mod = x % 10
            base = 10*x + mod

            if mod != 0:
                ans.append(base-1)
                count += 1

            ans.append(base)
            count += 1

            if mod != 9:
                ans.append(base+1)
                count += 1

            if count >= K:
                break
        print(ans[K-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
from collections import deque
K = int(input())
queue = deque([1,2,3,4,5,6,7,8,9])
def rec(queue,i):
    x = queue[i]
    if x >= 3234566667:
        return queue
    r = x % 10
    if (r != 0):
        new_x = x * 10 + (r) - 1
        queue.append(new_x)
    new_x = x * 10 + (r)
    queue.append(new_x)
    if (r != 9):
        new_x = x * 10 + r + 1
        queue.append(new_x)
    return rec(queue,i+1)
res = rec(queue,0)
print(res[K-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

n=int(input())
L=deque([i for i in range(1,10)])
if n<=9:
    ans = L[n-1]
else:
    cnt = 9
    for i in range(1,n):
        c=L.popleft()
        
        if c%10!=0:
            L.append(c*10+(c%10)-1)
            cnt+=1
            if cnt>=n:
                break
        L.append(c*10+(c%10))
        cnt+=1
        if cnt>=n:
            break
        
        if c%10!=9:
            L.append(c*10+(c%10)+1)
            cnt+=1
            if cnt>=n:
                break
    ans = L[-1]
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

n=int(input())
L=deque(list(range(1,10)))
if n<=9:
    ans = L[n-1]
else:
    cnt = 9
    for i in range(1,n):
        c=L.popleft()
        
        if c%10!=0:
            L.append(c*10+(c%10)-1)
            cnt+=1
            if cnt>=n:
                break
        L.append(c*10+(c%10))
        cnt+=1
        if cnt>=n:
            break
        
        if c%10!=9:
            L.append(c*10+(c%10)+1)
            cnt+=1
            if cnt>=n:
                break
    ans = L[-1]
print(ans)

Submission status: Accepted

Solution code:
def chk(l):
  s=0
  for r in l:
    s+=r
    if (s<0)|(s>9):
      return False
  return True
def nml(l):
  ln=len(l)
  for i in range(1,ln):
    if l[-i]==2:
      l[-i]=-1
      l[-i-1]+=1
  if l[0]==10:
    return True
  return False


a=[1]
for i in range(int(input())-1):
  while True:
    if len(a)==1:
      a[0]+=1
      if a[0]==10:
        a=[1,-1]
    else:
      a[-1]+=1
      if nml(a):
        a=[1]+[-(j==0) for j in range(len(a))]
    if chk(a):
      break
rt=""
ss=0
for i in a:
  ss+=i
  rt+=str(ss)
print(rt)

Submission status: Accepted

Solution code:
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
q=deque(list(range(1,10)))
c=0
while c<a:
  t=q.popleft()
  c+=1
  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:
from heapq import heappop, heappush, heapify
k = int(input())
def next_num(n):
  if n == 0:
    return [0, 1]
  elif n == 9:
    return [8, 9]
  else:
    return [n-1, n, n+1]
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]
heapify(queue)
for _ in range(k-1):
  now = heappop(queue)
  for next_i in next_num(now%10):
    heappush(queue, now*10 + next_i)
    
print(heappop(queue))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    K = Scanner.int()
    d = deque()
    for i in range(1, 10):
        d.append(i)
    MAX = 10 ** 5 + 100
    for i in range(MAX):
        n = d[i]
        a = int(str(n)[-1])
        if a != 0:
            d.append(n * 10 + (a - 1))
        d.append(n * 10 + a)
        if a != 9:
            d.append(n * 10 + (a + 1))
        if len(d) >= K:
            print(d[K - 1])
            return


def main():
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k = int(input())

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

for i in range(9):
    for x in list(lunlun):
        iti = int(str(x)[-1])
        l = x*10 + (iti-1)
        m = x*10 + (iti+0)
        n = x*10 + (iti+1)

        lunlun.add(m)
        if iti != 9:
            lunlun.add(n)
        if iti != 0:
            lunlun.add(l)

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

Submission status: Accepted

Solution code:
from collections import deque


def solver(K):
    q = deque([i for i in range(1, 10)])

    if K <= 9:
        ans = q[K - 1]

    else:
        cnt = 9
        for i in range(1, K):
            c = q.popleft()

            if c % 10 != 0:
                q.append(c * 10 + (c % 10) - 1)
                cnt += 1
                if cnt >= K:
                    break

            q.append(c * 10 + (c % 10))
            cnt += 1
            if cnt >= K:
                break

            if c % 10 != 9:
                q.append(c * 10 + (c % 10) + 1)
                cnt += 1
                if cnt >= K:
                    break

        ans = q[-1]
    return ans


def run():
    K = int(input())
    ans = solver(K)

    print(ans)


run()

Submission status: Accepted

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

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

for i in range(N-1):
  num=q.pop()
  if num%10!=0:
    q.appendleft(num*10+num%10-1)
  q.appendleft(num*10+num%10)
  if num%10!=9:
    q.appendleft(num*10+num%10+1)

print(q.pop())

Submission status: Accepted

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

    K = int(input())
    if K <= 9:
        print(K)
        return
    
    q = deque()
    for i in range(1, 10):
        q.append(i)
    
    count = 9
    while True:
        get_num = q.popleft()
        for i in range(-1, 2):
            add_num = get_num % 10 + i
            if 0 <= add_num and add_num <= 9:
                q.append(get_num * 10 + add_num)
                count += 1
                if count == K:
                    print(q.pop())
                    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
k=int(input())
logl=len(str(k))

def bfs(nowres, result=[]):
  if len(result) >= k:
    return sorted(result)
  rescand=[]
  for res in nowres:
    eq=res*10+res%10
    rescand.append(eq)
    if eq % 10>0:
      rescand.append(eq-1)
    if eq % 10<9:
      rescand.append(eq+1)
  return bfs(rescand, result+nowres)

res=bfs(list(range(1,10)))
#print(res)
print(res[k-1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

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

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

print(s)

Submission status: Accepted

Solution code:
from collections import deque
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

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

Submission status: Accepted

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

i = 0
while i<9:
    X = []
    for L in lis:
        if i == 0 or L >= 10**i:
            s = str(L)
            if s[-1] == "0":
                X.append(10*L)
                X.append(10*L+1)
            elif s[-1] == "9":
                X.append(10*L+8)
                X.append(10*L+9)
            else:
                X.append(10*L+int(s[-1])-1)
                X.append(10*L+int(s[-1]))
                X.append(10*L+int(s[-1])+1)
    for x in X:
        lis.append(x)
    i += 1
print(lis[k-1])

Submission status: Accepted

Solution code:
k = int(input())

queue = [1,2,3,4,5,6,7,8,9]
cnt = 0
while cnt + len(queue) < k:
  cnt += 1
  n = queue.pop(0)
  if n%10 != 0:
    queue.append(n*10+n%10-1)
  queue.append(n*10+n%10)
  if n%10 != 9:
    queue.append(n*10+n%10+1)
print(queue[k-cnt-1])

Submission status: Accepted

Solution code:
k = int(input())
cand = [[1,2,3,4,5,6,7,8,9]]
for i in range(9):
  tmp = []
  for val in cand[-1]:
    if val % 10 != 0:
      tmp.append(val*10 + (val%10 - 1))
    tmp.append(val*10 + (val % 10))
    if val % 10 != 9:
      tmp.append(val*10 + (val%10 + 1))
  cand.append(tmp)

ans = []
for j in range(len(cand)):
  for val in cand[j]:
    ans.append(val)
ans = sorted(ans)

print(ans[k - 1])

Submission status: Accepted

Solution code:
from collections import deque
dq = deque([1,2,3,4,5,6,7,8,9])
ans = []
while dq:
    p = dq.popleft()
    ans.append(p)
    if p <= 323456666:
        q = p % 10
        if not q in [0,9]:
            for i in range(-1,2):
                dq.append(10*p+q+i)
        else:
            if q == 9:
                dq.append(10*p+8)
                dq.append(10*p+9)
            else:
                dq.append(10*p)
                dq.append(10*p+1)
ans.sort()
#print(ans)
print(ans[int(input())-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
Q = deque()
for i in range(1, 10):
    Q.append(i)
temp = 0
for i in range(K):
    temp = Q.popleft()
    if temp%10 != 0:
        Q.append(temp*10+temp%10-1)
    Q.append(temp*10+temp%10)
    if temp%10 != 9:
        Q.append(temp*10+temp%10+1)
print(temp)

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    K=int(input())
    lunlun=[1,2,3,4,5,6,7,8,9]
    ind=0
    lll=9
    for dig in range(12):
        l=lll
        for i in lunlun[ind:]:
            s=str(i)
            x=int(s[dig])
            if 0<=x-1<=9:
                lunlun+=[int(s+str(x-1))]
                lll+=1
            if 0<=x<=9:
                lunlun+=[int(s+str(x))]
                lll+=1
            if 0<=x+1<=9:
                lunlun+=[int(s+str(x+1))]
                lll+=1
            if lll>K:
                break
        ind=l
    lunlun.sort()
    print(lunlun[K-1])
    
    
if __name__=="__main__":
    main()

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

Submission status: Accepted

Solution code:
k=int(input())
result = []
def dfs(pos, val):
  result.append(val)

  if pos == 10:
    return
  
  for i in range(-1,2):
    add_num = (val % 10) + i
    if 0 <= add_num <= 9:
      dfs(pos+1, val*10+add_num)

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

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
q = deque()
def main():
    for i in range(1, 10):
        q.append(i)
    for _ in range(k):
        x = q.popleft()
        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)
    print(x)

        
if __name__ == '__main__':
    main()