Problem:


Score : 400 points

Problem Statement

A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:

In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1.

For example, 1234, 1, and 334 are lunlun numbers, while none of 31415, 119, or 13579 is.

You are given a positive integer K. Find the K-th smallest lunlun number.

Constraints

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer.

Sample Input 1

15

Sample Output 1

23

We will list the 15 smallest lunlun numbers in ascending order:

1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
21,
22,
23.

Thus, the answer is 23.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

13

Sample Output 3

21

Sample Input 4

100000

Sample Output 4

3234566667

Note that the answer may not fit into the 32-bit signed integer type.



Sample input:
15


Sample output:
23

Submission status: Accepted

Solution code:
import queue
def solved(n):
    if n <= 9:
        return n
    nums = queue.Queue()
    for i in range(1, 10):
        nums.put(i)
    cnt = 9
    for i in range(cnt, n):
        i_num = nums.get()
        ini_num = i_num % 10
        for j in range(max(0, ini_num - 1), min(10, ini_num + 2)):
            nums.put(i_num * 10 + j)
            cnt += 1
            if cnt == n:
                return i_num * 10 + j
k = int(input())
num = queue.Queue()
print(solved(k))

Submission status: Accepted

Solution code:
from collections import deque

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

ans = 0
while True:
    v = dque.popleft()
    ans += 1
    if ans == K:
        print(v)
        exit(0)

    for i in range(-1, 2):
        # 10で割った余りを取得して、iを足す
        tmp = v % 10+i
        if not(0 <= tmp <= 9):
            continue
        dque.append(v*10+tmp)

Submission status: Accepted

Solution code:
k = int(input())

runrun = []

import queue
q = queue.Queue()
for i in range(1,10,1):
    q.put(i)
num = 0
while num <= 3234566667:
    num = q.get()
    runrun.append(num)
    tale = str(num)
    if(tale[-1] == '0'):
        same_tale = tale + '0'
        same_tale = int(same_tale)
        q.put(same_tale)

        max_tale =  tale + '1'
        max_tale = int(max_tale)
        q.put(max_tale)
    elif(tale[-1] == '9'):
        min_tale = tale + '8'
        min_tale = int(min_tale)
        q.put(min_tale)

        same_tale = tale + '9'
        same_tale = int(same_tale)
        q.put(same_tale)
    else:
        v = int(tale[-1])
        min_tale = tale + str(v-1)
        min_tale = int(min_tale)
        q.put(min_tale)

        same_tale = tale + str(v)
        same_tale = int(same_tale)
        q.put(same_tale)

        max_tale =  tale + str(v+1)
        max_tale = int(max_tale)
        q.put(max_tale)

print(runrun[k-1])

Submission status: Accepted

Solution code:
k = int(input())

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

for i in lunlun:
    stri = str(i)
    if stri[-1] == '0':
        tmp = stri + '0' 
        lunlun.append(int(tmp))
        tmp = stri + '1'
        lunlun.append(int(tmp))
        if len(lunlun) >= k:
            print(lunlun[k-1])
            exit()
    elif stri[-1] == '9':
        tmp = stri + '8'
        lunlun.append(int(tmp))
        tmp = stri + '9'
        lunlun.append(int(tmp))
        if len(lunlun) >= k:
            print(lunlun[k-1])
            exit()
    else:
        tmp = stri + str(int(stri[-1]) - 1)
        lunlun.append(tmp)
        tmp = stri + str(int(stri[-1]))
        lunlun.append(tmp)
        tmp = stri + str(int(stri[-1]) + 1)
        lunlun.append(tmp)
        if len(lunlun) >= k:
            print(lunlun[k-1])
            exit()

Submission status: Accepted

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

def generator(n):
    end = n % 10
    for i in range(-1,2):
        i += end
        if 0 <= i <= 9:
            yield l*10+i

ans = list(range(1,10))

while len(ans) < K:
    l = q.get()
    for i in generator(l):
        q.put(i)
        ans.append(i)

print(ans[K-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc161/tasks/abc161_d
from collections import deque

K = int(input())
ans = 0
count = 0
queue = deque()
for i in range(1, 10):
    queue.append(i)

while True:
    count += 1
    a = queue.popleft()
    if count == K:
        print(a)
        exit(0)

    for i in range(-1, 2):
        d = a % 10 + i
        if d < 0 or d > 9:
            continue
        queue.append(a * 10 + d)

Submission status: Accepted

Solution code:
import collections
k=int(input())
if k<=9:
    print(k)
else:
    k-=9
    l =list(range(9,0,-1))
    #print(l)
    q = collections.deque(l)
    counter=0
    while counter<k:
        x=q.pop()
        xrem=x%10
        if xrem!=0:
            q.appendleft(10*x+xrem-1)
            counter+=1
            if counter>=k:
                break
        q.appendleft(10*x+xrem)
        counter+=1
        if counter>=k:
                break
        if xrem!=9:
            q.appendleft(10*x+xrem+1)
            counter+=1
    print(q[0])

Submission status: Accepted

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

cnt = 9
ans = 0
while True:
    if K <= cnt:
        print(K)
        break
    l = q.get()
    end = l % 10
    for i in range(-1,2):
        i += end
        if 0 <= i <= 9:
            q.put(l*10+i)
            cnt += 1
            if cnt == K:
                ans = l*10+i

    if cnt >= K:
        print(ans)
        break

Submission status: Accepted

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

que = deque(map(str, range(1, 10)))
while K > 1:
    n = que.popleft()
    K -= 1
    R = int(n[-1])
    for r in (R - 1, R, R + 1):
        if 0 <= r <= 9:
            que.append(n + str(r))

print(que[0])

Submission status: Accepted

Solution code:
def main():
    k = int(input())
    lunluns = [i for i in range(1, 10)]
    if k <= len(lunluns):
        print(lunluns[k - 1])
        return

    while True:
        if k <= len(lunluns):
            print(lunluns[k - 1])
            return
        k -= len(lunluns)
        olds = lunluns
        lunluns = []
        for old in olds:
            for i in (-1, 0, 1):
                digit_next = old % 10 + i
                if digit_next < 0 or digit_next > 9:
                    continue
                new = old * 10 + digit_next
                lunluns.append(new)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def solve():

    K = int(input())

    dq = deque()
    # 一桁のケース
    for i in range(9):
        dq.append(i+1)

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

    print(num)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

while q:
  e = q.popleft()
  counter += 1 
  
  if counter >= K:
    print(e)
    break
  
  for i in [-1, 0, 1]:
    d = e % 10 + i
    if 0 <= d <= 9:
      q.append(e * 10 + d)

Submission status: Accepted

Solution code:
#import sys
#sys.setrecursionlimit(1000000000)

from collections import deque

def main():
    k = int(input())
    lst = []
    bfs("",k,lst)
    print(lst[k-1])


def bfs(s,k,lst=[]):
    d = deque()
    for c in "0123456789":
        d.append(c)
    while d:
        if len(lst) > k:
            return
        now = d.popleft()
        if now=="0":
            continue
        lst.append(now)
        for nxt in [int(now[-1])-1,int(now[-1]),int(now[-1])+1]:
            if nxt < 0 or nxt > 9:
                continue
            d.append(now+str(nxt))



if __name__ == '__main__':
    main()

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()
    right = x % 10
    for j in range(max(0, right-1), min(right+2, 10)):
        q.put(x*10 + j)

print(x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    lunlun = [[] for i in range(11)]
    lunlun[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    cnt = 9
    if n < 10:
        print(n)
        exit()
    for j in range(0, 10):
        for a in lunlun[j]:
            for b in range(10):
                if abs((a % 10) - b) < 2:
                    lunlun[j + 1].append(10 * a + b)
                    cnt += 1
                    if cnt == n:
                        print(10 * a + b)
                        exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
K=int(input())
d=deque([_ for _ in range(1,10)])
if K<=9:
  print(K)
  exit()
i=0
while True:
  a=d.popleft()
  i+=1
  if i==K:
    print(a)
    exit()
  if a%10!=0 and a%10!=9:
    d.extend([10*a+(a%10)+i for i in range(-1,2)])
  elif a%10==0:
     d.extend([10*a+i for i in range(2)])
  elif a%10==9:
     d.extend([10*a+i for i in range(8,10)])

Submission status: Accepted

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

#queue = list(range(1,10))
queue = deque(list(range(1,10)))

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

print(lunlun)

Submission status: Accepted

Solution code:
k = int(input())

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

def gene_lunlun(x):
    last = x % 10
    if last - 1 >= 0:
        yield x * 10 + last - 1
    yield x * 10 + last
    if last + 1 <= 9:
        yield x * 10 + last + 1

p = 0
while len(lunlun) < k:
    for new_lunlun in gene_lunlun(lunlun[p]):
        lunlun.append(new_lunlun)
    p += 1

print(lunlun[k-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from queue import deque
k = int(input())
Q = deque([ i for i in range(1, 10) ])
for _ in range(k):
    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)

Submission status: Accepted

Solution code:
import copy
k=int(input())
ans=[[str(i+1) for i in range(9)]]
l2=[]
for i in range(9):
  l=ans[-1]
  l2=[]
  for j in range(len(l)):
    if int(l[j][-1])!=0:
      l2.append(l[j]+str(int(l[j][-1])-1))
    l2.append(l[j]+str(int(l[j][-1])))
    if int(l[j][-1])!=9:
      l2.append(l[j]+str(int(l[j][-1])+1))
  ans.append(l2)
  l=copy.copy(l2)
a=[]
for i in range(10):
  a=a+ans[i]
print(a[k-1])

Submission status: Accepted

Solution code:
k=int(input())
anss=[i for i in range(1,10)]

for i in range(12):
  if len(anss)>k:
    print(anss[k-1])
    break
  new_anss=[]
  for ans in anss:
    if ans%10 != 0:
      new_anss.append(ans*10+ans%10-1)
    new_anss.append(ans*10+ans%10)
    if ans%10 != 9:
      new_anss.append(ans*10+ans%10+1)
  k -= len(anss)
  anss = new_anss

Submission status: Accepted

Solution code:
from collections import deque

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

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

print(lst.popleft())

Submission status: Accepted

Solution code:
import queue

k = int(input())

q = queue.Queue()
for i in range(1, 10):
  q.put(i)
for i in range(k-1):
  a = q.get()
  b = a % 10  #aの一の位
  if b != 0:
    q.put(10*a + b - 1)
  q.put(10*a + b)
  if b != 9:
    q.put(10*a + b + 1)

print(q.get())

Submission status: Accepted

Solution code:
k = int(input())
anss = [1,2,3,4,5,6,7,8,9]
for i in range(12):
    if len(anss) > k:
        print(anss[k-1])
        break
    new_anss = []
    for ans in anss:
        if ans % 10 != 0:
            new_anss += [ans*10+ans%10-1]
        new_anss += [ans*10+ans%10]
        if ans % 10 != 9:
            new_anss += [ans*10+ans%10+1]
    k -= len(anss)
    anss = new_anss

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

d = [-1, 0, 1]

lun = deque([1,2,3,4,5,6,7,8,9])
cnt = 9
while cnt < K:
    a = lun.popleft()
    b = str(a)[-1]
    if b not in ('0', '9'):
        lun.append(int(str(a) + str(int(b) - 1)))
        lun.append(int(str(a) + b))
        lun.append(int(str(a) + str(int(b) + 1)))
        cnt += 3
    elif b == '0':
        lun.append(int(str(a) + b))
        lun.append(int(str(a) + str(int(b) + 1)))
        cnt += 2
    elif b == '9':
        lun.append(int(str(a) + str(int(b) - 1)))
        lun.append(int(str(a) + b))
        cnt += 2

print(lun[K-cnt-1])

Submission status: Accepted

Solution code:
from collections import deque
K = int(input()) - 1
todo = deque(range(1, 10))
ans = []
counter = 0
while counter <= K:
    seed = todo.popleft()
    ans.append(seed)
    counter += 1
    last_dig = int(str(seed)[-1])
    for i in range(max(0, last_dig-1), min(10, last_dig+2)):
        todo.append(int(str(seed) + str(i)))
print(ans[-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

idx = 1
while idx < K:
    x = dq.popleft()
    idx += 1

    r = x % 10

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

    nx = (x * 10) + (r)
    dq.append(nx)

    if r < 9:
        nx = (x * 10) + (r + 1)
        dq.append(nx)

ans = dq.popleft()
print(ans)

Submission status: Accepted

Solution code:
k=int(input());l=list(range(1,10))
for i in l:
  for j in range(max(i%10-1,0),min(i%10+2,10)):l+=[i*10+j]
  if len(l)>k:break
print(l[k-1])

Submission status: Accepted

Solution code:
# Assumed solution

from collections import deque


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

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

    l = 0
    for _ in range(k):
        l = queue.popleft()
        r = l % 10
        if r != 0:
            queue.append(l * 10 + r - 1)
        queue.append(l * 10 + r)
        if r != 9:
            queue.append(l * 10 + r + 1)
    print(l)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k=int(input());l=list(range(1,10))
for i in l:
  if len(l)>k: break
  for j in range(max(i%10-1,0),min(i%10+2,10)): l.append(i*10+j)
print(l[k-1])

Submission status: Accepted

Solution code:
import sys
k = int(input())
old = [1,2,3,4,5,6,7,8,9]
new = []
count = 9
if k <= count:
    print(old[k-1])
    sys.exit()
else:
    while count < k:
        if len(old) > 0:
            i = old.pop(0)
            last = i%10
            if last != 0:
                new.append(i*10 + (last-1))
                count += 1
                if count == k:
                    break
            new.append(i*10 + last)
            count += 1
            if count == k:
                break
            if last != 9:
                new.append(i*10 + (last+1))
                count += 1
                if count == k:
                    break
        else:
            old = new
            new = []
    print(new[-1])

Submission status: Accepted

Solution code:
k=int(input())

from collections import deque
q = deque(range(1,10))

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

Submission status: Accepted

Solution code:
from collections import *
k=int(input());q=deque(range(1,10));c=0
while c<k:
  t=q.popleft()
  for j in range(max(t%10-1,0),min(t%10+2,10)): q+=[t*10+j]
  c+=1
print(t)

Submission status: Accepted

Solution code:
from collections import deque


K = int(input())
q = deque()
for i in range(1, 10):
    q.append(i)

while K > 0:
    p = q.popleft()
    K -= 1
    r = p % 10
    if r != 0:
        q.append(10 * p + r - 1)
    q.append(10 * p + r)
    if r != 9:
        q.append(10 * p + r + 1)

print(p)

Submission status: Accepted

Solution code:
from collections import deque

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

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

    count = 0
    while (True):
        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)
        if count == K-1:
            print(x)
            break
        count += 1

if __name__ == '__main__':
    main()

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(x*10 + x % 10 - 1)
    q.put(x*10 + x % 10)
    if x % 10 < 9:
        q.put(x*10 + x % 10 + 1)

print(x)

Submission status: Accepted

Solution code:
k=int(input())
 
from collections import deque
q = deque(range(1, 10))

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

Submission status: Accepted

Solution code:
K = int(input())
 
from collections import deque
q = deque(range(1, 10))
for _ in range(K - 1):
    d = q.popleft()
    if d % 10 > 0:
        q.append(d * 10 + d % 10 - 1)
    q.append(d * 10 + d % 10)
    if d % 10 < 9:
        q.append(d * 10 + d % 10 + 1)
print(q.popleft())

Submission status: Accepted

Solution code:
n=int(input());l=list(range(1,10));c=1
for i in l:
  c+=1
  if c>n: print(i); break
  for j in range(max(i%10-1,0),min(i%10+2,10)): l+=[i*10+j]

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def isOk(x):
    prev = x%10
    x = x//10
    while x > 0:
        y = x%10
        if abs(y - prev) > 1:
            return False
    
    return True


k = int(input())

# if k <= 10:
#     print(k)
#     exit()

count = 0

def dfs(X,n):
    global count

    # log(X, n)

    if n == 0:
        count += 1
        if count == k:
            print("".join(map(str,X)))
            exit()
        # else:
            # log(count, "".join(map(str,X)))
        return
    
    if len(X) == 0:
        for y in range(1,10):
            dfs([y], n-1)
        return

    last = X[-1]
    for y in range(max(0,last-1), min(9,last+1)+1):
        dfs(X + [y], n-1)


dfs([], 1)
dfs([], 2)
dfs([], 3)
dfs([], 4)
dfs([], 5)
dfs([], 6)
dfs([], 7)
dfs([], 8)
dfs([], 9)
dfs([], 10)

Submission status: Accepted

Solution code:
K=int(input())
ans=[]
for i in range(1,10):
    ans.append(i)
i=0

while True:
    if ans[i]%10==0:
        ans.append(10*ans[i])
        ans.append(10*ans[i]+1)
    elif ans[i]%10==9:
        ans.append(10*ans[i]+8)
        ans.append(10*ans[i]+9)
    else:
        ans.append(10*ans[i]+(ans[i]%10-1))
        ans.append(10 * ans[i] + (ans[i] % 10 ))
        ans.append(10 * ans[i] + (ans[i] % 10+1))
    if len(ans)>K:
        break
    i+=1

print(ans[K-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

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

    def check(x):
        x = str(x)
        dp = [[0] * 2 for _ in range(10)]
        
        s = int(x[0])
        for i in range(1, s):
            dp[i][1] = 1
        dp[s][0] = 1

        x = x[1:]
        for s in x:
            s = int(s)
            ndp = [[0] * 2 for _ in range(10)]
            for d, lt in product(range(10), range(2)):
                for nd in [d-1, d, d+1]:
                    if not (0 <= nd <= 9):
                        continue
                    if lt == 0 and s < nd:
                        continue
                    nlt = max(lt, s > nd)
                    ndp[nd][nlt] += dp[d][lt]
            for d in range(1, 10):
                ndp[d][1] += 1
            dp = ndp
        return sum(dp[d][lt] for d, lt in product(range(10), range(2))) >= k

    print(bisection(1, 10**18+1, check, left=False))
resolve()

Submission status: Accepted

Solution code:
k = int(input())
a = list()
old = list()
for i in range(1,10):
    a.append(i)
while(True):
    if k <= len(a):
        print(a[k - 1])
        break
    k -= len(a)
    old.clear()
    a,old = old,a
    for i in old:
        for d in range(-1,2):
            last_num = i % 10 + d
            if (last_num >= 0) and (last_num <= 9):
                new = 10 * i + last_num
                a.append(new)

Submission status: Accepted

Solution code:
K = int(input())
lunlun = [n for n in range(10)]
if K < 10:
    print(K)
else:
    tmp = 9
    pre_top = 1
    pre_bottom = 9
    while(1):
        for j in range(pre_top, pre_bottom+1):
            for k in range(10):
                if abs(lunlun[j]%10 - k) < 2:
                    lunlun.append(lunlun[j]*10+k)
                    tmp += 1
                    if tmp == K:
                        break
            if tmp == K:
                break
        pre_top = pre_bottom + 1
        pre_bottom = tmp
        if tmp == K:
            break

    print(lunlun[-1])

Submission status: Accepted

Solution code:
def func(n):
    if (n==0):return [n,n+1]
    if (n==9):return [n-1,n]
    return [n-1,n,n+1]
k = int(input())
k_su = 0
lunlun_fl = [1,2,3,4,5,6,7,8,9]
while True:
    k_su += 1
    lunlun_fl_ = lunlun_fl
    #print('{} 桁目探索開始'.format(k_su+1))
    for i in lunlun_fl_:
        if (len(str(i)) != k_su):
            continue
        lunlun_n = list(map(lambda x:int(str(i)+str(x)),func(int(str(i)[-1]))))
        lunlun_fl.extend(lunlun_n)
        if (len(lunlun_fl) >= k):break
    #print(lunlun_fl)
    if (len(lunlun_fl) >= k):break
print(lunlun_fl[k-1])

Submission status: Accepted

Solution code:
nstr=["0","1","2","3","4","5","6","7","8","9"]

k=int(input())
#k=100000
k=k-1

kcnt=-1
m=[]
ms=[""]*100000

for ii in range(1,10):
    kcnt=kcnt+1
    ms[kcnt]=nstr[ii]
#    m.append(nstr[ii])
#    print(kcnt,ms[kcnt])
    if kcnt>=k:
        print(ms[k])
        break                

ked=-1
while kcnt<k:
    kst=ked+1
    ked=kcnt
    for i in range(kst,ked+1):
        i2=int(ms[i][-1])
        for ii in range(max(i2-1,0),min(i2+1,9)+1):
            kcnt=kcnt+1
            ms[kcnt]=ms[i]+nstr[ii]
#            print(kcnt,ms[kcnt])
            if kcnt>=k:
                print(ms[k])
                break                
        if kcnt>=k:
#            print(k)
            break

Submission status: Accepted

Solution code:
lun_luns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
k = int(input())
index = 0
while True:
	if len(lun_luns) >= k:
		break
	num = lun_luns[index]
	mod = num % 10
	n = num * 10
	if mod == 9:
		lun_luns.extend([n+mod-1, n+mod])
	elif mod == 0:
		lun_luns.extend([n, n+1])
	else:
		lun_luns.extend([n+mod-1, n+mod, n+mod+1])
	index += 1
print(lun_luns[k-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

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

    def check(x):
        if 1 <= x <= 9:
            return x >= k
        x = str(x)
        dp = [[0] * 2 for _ in range(10)]
        s = int(x[0])
        for i in range(1, s):
            dp[i][1] = 1
        dp[s][0] = 1

        x = x[1:]
        for s in x:
            s = int(s)
            ndp = [[0] * 2 for _ in range(10)]
            for d, lt in product(range(10), range(2)):
                for nd in [d-1, d, d+1]:
                    if not (0 <= nd <= 9):
                        continue
                    if lt == 0 and s < nd:
                        continue
                    nlt = max(lt, s > nd)
                    ndp[nd][nlt] += dp[d][lt]
            for d in range(1, 10):
                ndp[d][1] += 1
            dp = ndp
        return sum(dp[d][lt] for d, lt in product(range(10), range(2))) >= k


    print(bisection(1, 10**18+1, check, left=False))
resolve()

Submission status: Accepted

Solution code:
k=int(input())

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


for s in l0:
    temp=str(s)
    x=int(temp[-1])

    if x==0:
        l0.append(int(temp+"0"))
        l0.append(int(temp+"1"))
        #l0.append(int(temp+"9"))
    if x>=1 and x<=8:
        l0.append(int(temp+str(x-1)))
        l0.append(int(temp+str(x)))
        l0.append(int(temp+str(x+1)))
    if x==9:
        #l0.append(int(temp+"0"))
        l0.append(int(temp+"8"))
        l0.append(int(temp+"9"))
    
    if len(l0)>100002:
        break


print(l0[k-1])

Submission status: Accepted

Solution code:
K = int(input())

from collections import deque
q = deque(range(1, 10))
for _ in range(K - 1):
    d = q.popleft()
    if d % 10 > 0:
        q.append(d * 10 + d % 10 - 1)
    q.append(d * 10 + d % 10)
    if d % 10 < 9:
        q.append(d * 10 + d % 10 + 1)
print(q.popleft())

Submission status: Accepted

Solution code:
cands = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def add_v(v):
  global cands
  global K
  v0 = v % 10
  if v0 == 0:
    cands += [v*10, v*10+1]
    K -=2
  elif v0 == 9:
    cands += [v*10+8, v*10+9]
    K -= 2
  else:
    cands += [v*10+v0-1, v*10+v0, v*10+v0+1]
    K -= 3

K = int(input())
idk = K
K -= 9
idx = 0
while K >= 0:
  add_v(cands[idx])
  idx += 1

print(cands[idk-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
que = deque()
for i in range(1, 10):
    que.append(i)
count = 0
while 1:
    count += 1
    x = que.popleft()
    for i in range(-1, 2):
        d = x % 10 + i
        if (d < 0 or 9 < d):
            continue
        que.append(x * 10 + d)
    if (count == K):
        print(x)
        break

Submission status: Accepted

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

    def make_lunlun(number):
        min = str(number)[-1]
        new_lunlun = number * 10 + int(min)
        if min == "0":
            return (new_lunlun, new_lunlun + 1)
        elif min == "9":
            return (new_lunlun - 1, new_lunlun)
        else:
            return (new_lunlun - 1, new_lunlun, new_lunlun + 1)

    index = 0
    while True:
        if len(lun_luns) >= k:
            break
        num = lun_luns[index]
        lun_luns.extend(make_lunlun(num))
        index += 1
    print(lun_luns[k - 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# D - Lunlun Number


def main():
    K = int(input())
    queue = list(range(1, 10))
    i = 0
    while len(queue) < K:
        x = queue[i]
        remainder = x % 10
        if remainder:
            queue.append(10 * x + remainder - 1)
        queue.append(10 * x + remainder)
        if remainder != 9:
            queue.append(10 * x + remainder + 1)
        i += 1
    ans = queue[K - 1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
count = 0
arr  = [1,2,3,4,5,6,7,8,9]

while len(arr)<n:
    lastnum = int(str(arr[count])[-1])
    if lastnum == 0:
        arr.append(int(str(arr[count])+'0'))
        arr.append(int(str(arr[count])+'1'))
    elif 1 <= lastnum <= 8:
        arr.append(int(str(arr[count])+str(lastnum-1)))
        arr.append(int(str(arr[count])+str(lastnum)))
        
        arr.append(int(str(arr[count])+str(lastnum+1)))
    else:
        arr.append(int(str(arr[count])+'8'))
        arr.append(int(str(arr[count])+'9'))
    count += 1

print(arr[n-1])

Submission status: Accepted

Solution code:
from collections import deque

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

ans = 0
while True:
    v = dque.popleft()
    ans += 1
    if ans == K:
        print(v)
        exit(0)

    strv = str(v)
    if strv[-1] == '0':
        dque.append(int(strv+'0'))
        dque.append(int(strv+'1'))
    elif strv[-1] == '9':
        dque.append(int(strv+'8'))
        dque.append(int(strv+'9'))
    else:
        endv = int(strv[-1])
        dque.append(int(strv+str(endv-1)))
        dque.append(int(strv+str(endv)))
        dque.append(int(strv+str(endv+1)))

Submission status: Accepted

Solution code:
from collections import deque


def D(K):
    d = deque()
    c = 0

    for i in range(1, 10):
        d.append(i)
        c += 1
        if c == K:
            return d

    while True:
        num = d.popleft()
        mod = num % 10
        
        if mod != 0:
            d.append(num * 10 + mod - 1)
            c += 1
            if c == K:
                return d
            
        d.append(num * 10 + mod)
        c += 1
        if c == K:
            return d
        
        if mod != 9:
            d.append(num * 10 + mod + 1)
            c += 1
            if c == K:
                return d
              
              
K = int(input())
print(D(K).pop())