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:
q=[]

k=int(input())

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

#print(q)
#Perform operations k times

if(k<10):
    print(q[k-1])
    exit()

ops=0
t=[]
while(ops<k):

    x = q.pop(0)
    t.append(x)
    if(x%10!=0):
        ops+=1
        q.append(10*x + x%10 -1)
    q.append(10*x+ x%10)
    ops+=1

    if(x%10!=9):
        q.append(10*x + x%10 + 1)
        ops+=1
final = t+q
#print(final)
print(final[k-1])

Submission status: Accepted

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

import sys
from itertools import accumulate

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

MAX = 3234566667
ans = []
def rec(x, di):
    if di == 10:
        return
    if int(x) > MAX:
        return
    ans.append(int(x))
    last = int(x[-1])
    rec(x+str(last), di+1)
    if last != 0:
        rec(x+str(last-1), di+1)
    if last != 9:
        rec(x+str(last+1), di+1)
    return

K = INT()

for i in range(1, 10):
    rec(str(i), 0)

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

Submission status: Accepted

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

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

    q = deque()
    for i in range(1, 10):
        q.append(i)
    now = 0
    for _ in range(N):
        now = q.popleft()
        tmp = now%10
        if tmp != 0:
            q.append(now * 10 + tmp - 1)
        q.append(now * 10 + tmp)
        if tmp != 9:
            q.append(now * 10 + tmp + 1)
    print(now)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

d = deque()

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

n=int(input())
if n<10:
    print(n)
else:
    i=0
    cnt=0
    now=d.popleft()
    while i<n-9:
        if cnt==0:
            if now%10!=0:
                d.append(now*10+now%10-1)
                i+=1
            cnt+=1
            continue
        if cnt==1:
            d.append(now*10+now%10)
            cnt+=1
            i+=1
            continue
        if cnt==2:
            if now%10!=9:
                d.append(now*10+now%10+1)
                i+=1
            cnt=0
            now=d.popleft()
    print(d.pop())

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

K = int(input())
hq = []
for i in range(1,10):
  heappush(hq,i)
cnt = 0
while(cnt < K):
  x = heappop(hq)
  cnt += 1
  for i in [-1,0,1]:
    d = (x%10)+i
    if 0 <= d <= 9:
      heappush(hq,x*10+d)
print(x)

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
q = deque()

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

while True:
    # print(q)
    if len(q)>= k:
        print(q[k-1])
        exit()
    k -= len(q)

    for _ in range(len(q)):
        x = q.popleft()
        for i in [-1, 0, 1]:
            d = x % 10 + i
            if d < 0 or d > 9:
                continue
            q.append(10 * x + d)

Submission status: Accepted

Solution code:
from collections import deque
lunlun=[i for i in range(1,10)]
def bfs(K):
    d=deque([1,2,3,4,5,6,7,8,9])
    while(len(lunlun)<K):
        s=d[0]
        d.popleft()
        n=[]
        if(s%10!=0):
            n.append((s%10-1)+s*10)
        n.append(s%10+s*10)
        if(s%10!=9):
            n.append((s%10+1)+s*10)
        lunlun.extend(n);d.extend(n)
K=int(input())
bfs(K)
print(lunlun[K-1])

Submission status: Accepted

Solution code:
k = int(input())

a = []

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

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

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

Submission status: Accepted

Solution code:
x = int(input())

p = [None for _ in range(100)]

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

def getByKeta(n):
    for i in p[n-1]:
        for j in range(-1, 2):
          d = i % 10 + j
          if d < 0 or d > 9:
              continue

          yield i * 10 + d

for i in range(2, 11):
    p[i] = tuple(getByKeta(i))

ans = 0
for i in range(1, 11):
    if x <= len(p[i]):
        ans = p[i][x-1]
        break
    x -= len(p[i])
print(ans)

# p = []
# for i in range(1, 10):
#   p.append(i)

# ans = 0
# index = x

# while 1:
#     if index <= len(p):
#       break
#     index -= len(p)
#     for i in p:
#       for j in range(-1, 2):
#           d = i % 10 + j
#           if d < 0 or d > 9:
#               continue

#           nx = i * 10 + d
#           p.append(nx)

# print(p)
# print(len(p))
# ans = p[1]
# print(ans)

Submission status: Accepted

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

q = queue.Queue()

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
 
k = int(input())
 
li = [str(i) for i in range(1,10)]
st_li = li[:]
q = collections.deque(li)
count = 0
n = 10 ** 10
 
for i in range(1, n):
    a = q.popleft()
    num = int(a[-1])
    if num != 0:
        aa = a + str(num-1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    aa = a + str(num)
    st_li.append(aa)
    q.append(aa)
    count += 1
    if num != 9:
        aa = a + str(num+1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    if count > k+1:
        print(st_li[k - 1])
        exit(0)

Submission status: Accepted

Solution code:
import collections

k = int(input())

li = [str(i) for i in range(1,10)]
st_li = li[:]
q = collections.deque(li)
count = 0
n = 10 ** 10

for i in range(1, n):
    a = q.popleft()
    num = int(a[-1])
    if num != 0:
        aa = a + str(num-1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    aa = a + str(num)
    st_li.append(aa)
    q.append(aa)
    count += 1
    if num != 9:
        aa = a + str(num+1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    if count > k+1:
        print(st_li[k - 1])
        exit(0)

Submission status: Accepted

Solution code:
a = int(input())
last_run_dict = {0:["0"],1:["1"],2:["2"],3:["3"],4:["4"],5:["5"],6:["6"],7:["7"],8:["8"],9:["9"]}
s = 9
"""
新しい桁の数に対して前の桁の前後1の辞書から値をとってきて頭に足したものを再度格納する

"""
if a <= 9:
    print(a)
else:
    flag = False
    answer = ""
    while True:
        keta = 2
        tmp_dict = {0:[],1:[],2:[],3:[],4:[],5:[],6:[],7:[],8:[],9:[]}
        #0についてはカウントせずに0と1に対して先に格納
        for i in last_run_dict[0]:
            tmp_dict[0].append("0"+i)
        for i in last_run_dict[1]:
            tmp_dict[0].append("0"+i)
        #1~8については前後1、9については前1に対して格納してカウントを一つ進める
        for i in range(1,10):
            if i != 9:
                for num in range(-1,2):
                    for j in last_run_dict[int(i)+num]:
                        tmp_dict[i].append(str(i) + j)
                        s += 1
                        if s == a:
                            flag = True
                            answer = str(i) + j
                            break
                    if flag:
                        break
            else:
                for num in range(-1,1):
                    for j in last_run_dict[int(i)+num]:
                        tmp_dict[i].append(str(i) + j)
                        s += 1
                        if s == a:
                            flag = True
                            answer = str(i) + j
                            break
                    if flag:
                        break
            if flag:
                break
        if flag:
            break
        last_run_dict = tmp_dict
    print(answer)

Submission status: Accepted

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


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def d_lunlun_number_dfs():
    K = int(input())

    def dfs(value, digit, digit_max=10):
        ans.append(value)

        if digit == digit_max:
            return  # 10 桁程度調べれば 10**5 個を超える Lunlun Number が得られる

        # 次の数字をつける
        for j in (-1, 0, 1):
            lsd = (value % 10) + j
            if 0 <= lsd <= 9:
                dfs(10 * value + lsd, digit + 1)

    ans = []
    for leading in range(1, 10):
        dfs(leading, 1)
    return sorted(ans)[K - 1]

print(d_lunlun_number_dfs())

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 functools import lru_cache
import bisect
import re
import queue
from decimal import *


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 [input() 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 [int(input()) 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


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 isOK(A):
    A.sort()
    for i in range(len(A) - 1):
        if A[i] + 1 != A[i + 1]:
            return False
    return True


def func(x):
    return 1


def solve():
    K = Scanner.int()
    q = queue.deque()
    for i in range(1, 9 + 1):
        q.append(i)
    for _ in range(K - 1):
        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(q.popleft())


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


def min_lunlun(lmd, dnum):
    # lmdが先頭にあり、最も小さいdnum桁のlunlun数をつくる
    lst = [lmd]
    for i in range(1, dnum):
        lst.append(max(0, lst[i - 1] - 1))
    return lst


def next_lunlun(lst):
    # lstから次のlunlun数を作る
    # 数を増やせる桁を確認する
    add_d = -1
    for i in reversed(range(1, len(lst))):
        if lst[i] < 9 and lst[i - 1] >= lst[i]:
            add_d = i
            break
    lst[add_d] = lst[add_d] + 1
    for i in range(add_d + 1, len(lst)):
        lst[i] = max(lst[i - 1] - 1, 0)

    return lst



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

    if k < 10:
        print(k)
        return

    # d[i][j] : i始まりのj桁のルンルン数の数
    d = [[0 for _ in range(11)] for _ in range(10)]
    for x in range(10):
        d[x][1] = 1

    for j in range(1, 10):
        for i in range(10):
            if 0 <= i - 1:
                d[i][j + 1] += d[i - 1][j]
            if i + 1 < 10:
                d[i][j + 1] += d[i + 1][j]
            d[i][j + 1] += d[i][j]

    total = 0
    lmd = dnum = -1
    for j in range(1, 11):
        for i in range(1, 10):
            if total + d[i][j] >= k:
                prev_total = total
                lmd = i
                dnum = j
                break
            total += d[i][j]
        if lmd > 0:
            break

    lst = min_lunlun(lmd, dnum)
    for i in range(k - prev_total - 1):
        next_lunlun(lst)
    print("".join(map(str, lst)))
    

submit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K=int(input())

idx=0
l=list(range(1,10))

while len(l)<K:
    m=l[idx]
    for i in (-1,0,1):
        n=(m%10)+i
        if n in{-1,10}:
            continue
        tmp=m*10+n
        l.append(tmp)
    idx=idx+1

print(l[K-1])

Submission status: Accepted

Solution code:
def main():
    k = int(input())
    ary = [1,2,3,4,5,6,7,8,9]
    cnt = 9
    now = 0
    up_tmp = 0
    if k < 10:
        print(k)
        return
    while True:
        tmp = []
        for i in range(up_tmp,len(ary)):
            a_i = ary[i]
            keta_1 = int(list(str(a_i))[-1])
            if keta_1 != 0:
                cnt += 1
                now = a_i * 10 + keta_1 - 1
                tmp.append(now)

                if cnt == k:
                    print(now)
                    # print(ary)
                    # print(tmp)
                    return
            cnt += 1
            now = a_i * 10 + keta_1
            tmp.append(now)
            if cnt == k:
                print(now)
                # print(ary)
                # print(tmp)
                return
            if keta_1 != 9:
                cnt += 1
                now = a_i * 10 + keta_1 + 1
                tmp.append(now)

                if cnt == k:
                    print(now)
                    # print(ary)
                    # print(tmp)
                    return
        up_tmp = len(ary)
        ary.extend(tmp)



if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

q = deque([])

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

count = 0

while count < k:
    p = q.popleft()
    
    rem = p % 10
    
    if rem != 0 and rem != 9:
        q.append(10*p + rem -1)
        q.append(10*p + rem)
        q.append(10*p + rem + 1)
    if rem == 0:
        q.append(10*p + rem)
        q.append(10*p + rem + 1)
    if rem == 9:
        q.append(10*p + rem -1)
        q.append(10*p + rem)
    
    count += 1

print(p)

Submission status: Accepted

Solution code:
from collections import deque


def nth_ll(k):
    if k < 10:
        return k
    queue = deque([i for i in range(1, 10)])
    cnt = 9
    while True:
        n = queue.popleft()
        first_d = n % 10
        for i in range(-1, 2):
            if first_d + i < 0 or first_d + i > 9:
                continue
            queue.append(10 * n + first_d + i)
            cnt += 1
            if cnt == k:
                return queue.pop()

print(nth_ll(int(input())))

Submission status: Accepted

Solution code:
_,*s=range(10)
for v in s:s+=[w+v*10for w in range(max(0,v%10-1),min(10,v%10+2))]*(v<4e8)
print(s[int(input())-1])

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
queue = deque()
for i in range(1,10):
    queue.append(i)

for i in range(k-1):
    x = queue.popleft()
    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)

lunlun = queue.popleft()
print(lunlun)

Submission status: Accepted

Solution code:
a={0}
_,*s=range(10)
while s:
  v=s.pop()
  a|={v}
  for w in range(max(0,v%10-1),min(10,v%10+2)):
    w+=v*10
    if w<4e9:s+=w,
print(sorted(a)[int(input())])

Submission status: Accepted

Solution code:
from collections import deque


def nth_ll(k):
    if k < 10:
        return k
    queue = deque([i for i in range(1, 10)])
    cnt = 9
    while True:
        n = queue.popleft()
        for i in range(-1 if n % 10 != 0 else 0, 2 if n % 10 != 9 else 1):
            queue.append(10 * n + n % 10 + i)
            cnt += 1
            if cnt == k:
                return queue.pop()

print(nth_ll(int(input())))

Submission status: Accepted

Solution code:
from collections import deque

k=int(input())
ans=deque([1,2,3,4,5,6,7,8,9])
if k<=9:
  print(ans[k-1])
  exit()
k-=9
while True:
  x=ans.popleft()
  r=x%10
  if r==0:
    q=x*10
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()
    q+=1
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()
  elif r!=0 and r!=9:
    q=x*10+r-1
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()
    q+=1
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()
    q+=1
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()
  elif r==9:
    q=x*10-1+r
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()
    q+=1
    ans.append(q)
    k-=1
    if k==0:
      print(q)
      exit()

Submission status: Accepted

Solution code:
k = int(input())

lunlun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 0

def generate_lunlun(n):
    last = n % 10
    if last - 1 >= 0:
        yield n * 10 + last - 1
    yield n * 10 + last
    if last + 1 < 10:
        yield n * 10 + last + 1

while len(lunlun) < k:
    for new_lunlun in generate_lunlun(lunlun[n]):
        lunlun.append(new_lunlun)
    n += 1

print(lunlun[k-1])

Submission status: Accepted

Solution code:
k = int(input())

from collections import deque

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

print(x)

Submission status: Accepted

Solution code:
K = int(input())


xs = [str(x) for x in range(1,10)]

def get_lunlun(xs):
    ret = []
    for x in xs:
        last = x[-1]
        if last ==  "0":
            ret.append(x+"0")
            ret.append(x+"1")
        elif last == "9":
            ret.append(x+"8")
            ret.append(x+"9")
        else:
            ret.append(x+ str(int(last)-1))
            ret.append(x+ str(int(last)))
            ret.append(x+ str(int(last)+1))
    return ret

while K > len(xs):
    K = K -  len(xs)
    xs = get_lunlun(xs)
print(xs[K-1])

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque


def get_result(data):
    K = data[0]
    lunlun_num_q = deque([str(i+1) for i in range(9)])
    cnt = 9
    while cnt < K:
        tmp_num = lunlun_num_q.popleft()
        if tmp_num[-1] == '0':
            lunlun_num_q.extend([tmp_num + '0', tmp_num + '1'])
            cnt += 2
        elif tmp_num[-1] == '9':
            lunlun_num_q.extend([tmp_num + '8', tmp_num + '9'])
            cnt += 2
        else:
            last_digit = int(tmp_num[-1])
            lunlun_num_q.extend(
                [tmp_num + str(last_digit-1), tmp_num + str(last_digit),
                 tmp_num + str(last_digit+1)])
            cnt += 3

    return lunlun_num_q[-1+K-cnt]


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)

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

Submission status: Accepted

Solution code:
from queue import Queue

k = int(input().strip())
if 1<= k <= 9:
    print(k)
    exit()

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

ans = 0
count = 9
while True:
    ne = Queue()
    while not q.empty():
        now = str(q.get())
        if now[-1] == '0':
            for i in range(0, 2):
                count += 1
                rep = int(now + str(i))
                if count == k:
                    ans = rep
                    break
                ne.put(rep)
        elif now[-1] == '9':
            for i in range(8, 10):
                count += 1
                rep = int(now + str(i))
                if count == k:
                    ans = rep
                    break
                ne.put(rep)
        else:
            cen = int(now[-1])
            for i in range(cen - 1, cen + 2):
                count += 1
                rep = int(now + str(i))
                if count == k:
                    ans = rep
                    break
                ne.put(rep)
        if ans != 0:
            break
    if ans != 0:
        break
    q = ne
print(ans)

Submission status: Accepted

Solution code:
K=int(input())
A=[1,2,3,4,5,6,7,8,9]
I=0
while I<=K:
    if not A[I]%10==0:
        A.append(A[I]%10+10*A[I]-1)
    A.append(A[I]%10+10*A[I])
    if not A[I]%10==9:
        A.append(A[I]%10+10*A[I]+1)
    if len(A)>=K:
      break
    I+=1
print(A[K-1])

Submission status: Accepted

Solution code:
k = int(input())

from collections import deque
que = deque()

for i in range(k+9):
	if i < 9:
		que.append(i+1)
	else:
		x = que.popleft()
		if x % 10 != 0:
			que.append(10*x + (x%10) - 1)
		que.append(10*x + (x%10))
		if x % 10 != 9:
			que.append(10*x + (x%10) + 1)
print(x)

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):
    x = Queue[0]
    Queue.popleft()
    oneplace = x % 10

    #(1の位の数)-1を付け加えた数を入れる
    if oneplace == 0: #xの1の位が0
        pass
    else:   #xの1の位が0でない
        enqueue = x * 10 + (oneplace - 1)
        Queue.append(enqueue)
    
    #1の位の数を付け加えた数を入れる
    enqueue = x * 10 + oneplace
    Queue.append(enqueue)

    #(1の位の数)+1を付け加えた数を入れる
    if oneplace == 9:   #xの1の位の数が9
        pass
    else:
        enqueue = x * 10 + (oneplace + 1)
        Queue.append(enqueue)

print(x)

Submission status: Accepted

Solution code:
def main():
  from collections import deque
  k=int(input())
  l=deque([1,2,3,4,5,6,7,8,9])
  x=1
  for _ in range(k-1):
    x=l[0]
    l.popleft()
    if x%10>0:
      l.append(10*x+x%10-1)
    l.append(10*x+x%10)
    if x%10<9:
      l.append(10*x+x%10+1)
  print(l[0])
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
#ABC161,D_LunLun Number

import queue
q = queue.Queue()

#[1~9]
for i in range(1,10):
    q.put(i)
K = int(input())


for k in range(K):
    #queueの最初を取り出す
    x =q.get()

    #last=1桁目の数字
    last = x % 10

    #1桁目が0ではないなら
    if last != 0:
        #1桁目-1の数字を末尾に加える
        q.put(10*x + last - 1)
    #末尾に1桁目と同じ数字を足す
    q.put(10*x + last)
    #もし1桁目が9ではないなら
    if last != 9:
        #末尾に1桁目+1の数字を加える
        q.put(10*x + last + 1)
print (x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
 
K = int(input())
 
lis = []
def dfs(nowD, maxD, x):
    if nowD == maxD:
        lis.append(x)
        if len(lis) >= K:
            print(lis[K-1])
            exit()
    else:
        y = x%10
        x *= 10
        if y-1 >= 0:
            dfs(nowD+1, maxD, x+y-1)
        dfs(nowD+1, maxD, x+y)
        if y+1 <= 9:
            dfs(nowD+1, maxD, x+y+1)
 
for d in range(1, 11):
    for x in range(1, 10):
        dfs(1, d, x)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
 
K = int(input())
 
lis = deque()
def dfs(nowD, maxD, x):
    if nowD == maxD:
        lis.append(x)
        if len(lis) >= K:
            print(lis.pop())
            exit()
    else:
        y = x%10
        x *= 10
        if y-1 >= 0:
            dfs(nowD+1, maxD, x+y-1)
        dfs(nowD+1, maxD, x+y)
        if y+1 <= 9:
            dfs(nowD+1, maxD, x+y+1)
 
for d in range(1, 11):
    for x in range(1, 10):
        dfs(1, d, x)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def solve(k):
	q = [1,2,3,4,5,6,7,8,9]
	last = 0
	i = 0
	while(k > 0):
		last = q[i]
		rem = last%10
		lower = 0
		bigger = 0
		if(rem != 0):
			lower = 10*last + rem - 1
		if(rem != 9):
			bigger = 10*last + rem + 1
		equal = 10*last + rem
		# print('last:',last,rem,'::',lower,equal,bigger)
		if(lower):
			q.append(lower)
		q.append(equal)
		if(bigger):
			# print(rem)
			q.append(bigger)
		i += 1
		k -= 1
	# print(len(q),len(set(q)))
	return last
	

K = int(stdin.readline())
ans = solve(K)
print(ans)

Submission status: Accepted

Solution code:
from queue import Queue

k = int(input())

q = Queue()

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

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

print(x)

Submission status: Accepted

Solution code:
from queue import Queue
q = Queue()

k = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

K = int(input())

q = [i for i in range(1, 10)]
heapq.heapify(q)
cnt = 0
while cnt < K:
    x = heapq.heappop(q)
    cnt += 1
    heapq.heappush(q, 10 * x + x % 10)
    if x % 10 != 0:
        heapq.heappush(q, 10 * x + x % 10 - 1)
    if x % 10 != 9:
        heapq.heappush(q, 10 * x + x % 10 + 1)
print(x)

Submission status: Accepted

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

while 1:
    x = len(a)
    if k <= x:
        print(a[k-1])
        sys.exit( )
    b=[]
    for z in a:
        if z[-1]!='0':
            b.append(z+str(int(z[-1])-1))
        b.append(z+z[-1])
        if z[-1]!='9':
            b.append(z+str(int(z[-1])+1))
    k-=x
    a=b[:]

Submission status: Accepted

Solution code:
import queue

q = queue.Queue()

num = int(input())
if num < 13:
    print(num)
    exit()
for _ in range(1,10):
    q.put(_)
for _ in range(num):
    x = q.get()
    t = x % 10

    if x % 10 != 0:
        q.put(10 * x -1 + t)
    q.put(10 * x + t)
    if x % 10 != 9:
        q.put(10 * x +1 + t)
print(x)

Submission status: Accepted

Solution code:
K = int(input())
A = [i for i in range(1, 10)]
count = 10
for i in range(0, K-1):
    if K >= 10:
        for j in range(0, 10):
            if abs(j - A[0] % 10) <= 1 and count <= K:
                A.append(A[0]*10+j)
                count += 1
        del A[0]
if K < 10:
    print(A[K-1])
else:
    print(A[-1])

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
d = deque()
for i in range(1, 10):
    d.append(i)
while k > 1:
    k -= 1
    temp = d.popleft()
    if temp % 10:
        d.append(10 * temp + (temp % 10)-1)
    d.append(10 * temp + (temp % 10))
    if temp % 10 != 9:
        d.append(10 * temp + (temp % 10) + 1)
print(d.popleft())