Problem:


Score : 400 points

Problem Statement

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

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

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

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

Constraints

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer.

Sample Input 1

15

Sample Output 1

23

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

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

Thus, the answer is 23.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

13

Sample Output 3

21

Sample Input 4

100000

Sample Output 4

3234566667

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



Sample input:
15


Sample output:
23

Submission status: Accepted

Solution code:
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))
def all_subset(li):
    s = []
    n = len(li)
    for bit in range(0, (1<<(n+1))):
        ss = set()
        for i in range(0, n):
            if (bit & (1 << i)):
                ss.add(li[i])
        s.append(ss)
    return s
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
def mCn(m, n):
    def factorial_ntimes(m, n):
        r = 1
        while n:
            r *= m
            m -= 1
            n -= 1
        return r
    return int(factorial_ntimes(m, n) / factorial(n))


k = load()
q = deque()

li = list()

for i in range(1, 10):
    li.append(str(i))
    q.append(str(i))
    if len(li) >= k:
        print(li[-1])
        exit()

while True:
    e = q.popleft()
    for i in range(-1, 2, 1):
        next = int(e[-1]) + i
        if next >= 0 and next < 10:
            li.append(e + str(next))
            q.append(e + str(next))
        if len(li) >= k:
            print(li[-1])
            exit()

Submission status: Accepted

Solution code:
def main():
    from functools import lru_cache
    import sys

    sys.setrecursionlimit(10 ** 7)

    @lru_cache(maxsize=None)
    def make_number(digit, p=0):
        if digit == 0:
            memo.append(p)
            if len(memo) == k + 1:
                print(p)
                exit()
            return

        if p == 0:
            # 前の位がない
            for x in range(1, 10):
                make_number(digit - 1, x)

        else:
            r = p % 10
            # 前の位がある
            for x in range(max(0, r - 1), min(9, r + 1) + 1):
                make_number(digit - 1, p * 10 + x)

    k = int(input())

    memo = []

    for digit in range(11):
        make_number(digit)


if __name__ == '__main__':
    main()

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

List = [str(i) for i in range(0, 10)]
prev_num = 10
K = int(input())
if K <= 9:
    print(List[K])
else:
    while True:
        List2 = []
        for i in List:
            if i != "0":
                List2.append(i + str(i[-1]))
                if i[-1] != "9":
                    List2.append(i + str(int(i[-1]) + 1))
                if i[-1] != "0":
                    List2.append(i + str(int(i[-1]) - 1))
        List = List2
        if prev_num + len(List)-1 >= K:
            List = list(map(int, List))
            List.sort()
            print(List[K - prev_num])
            sys.exit()
        prev_num += len(List)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    K=int(input())
    l=[0]*10**6
    for i in range(9):
        l[i]=i+1
    left=0
    right=9
    a=[[0,1],[0,1,2],[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9]]
    while True:
        tmp=[]
        for x in l[left:right]:
            for y in a[x%10]:
                tmp.append(x*10+y)
        tmp.sort()
        l[right:right+len(tmp)]=tmp
        left=right
        right+=len(tmp)
        if right>K:
            print(l[K-1])
            break

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def nex(s):
    ketsu = int(s[-1])
    if ketsu ==0: return ['0','1']
    elif ketsu ==9: return ['8','9']
    else:return list(map(str,[ketsu-1,ketsu,ketsu+1]))



k = int(input())
runrun = ['1','2','3','4','5','6','7','8','9']
point = 0
while True:
    if len(runrun) >= k: break
    else:
        run = runrun[point]
        for i in nex(run):
            runrun.append(run+i)
        point +=1

print(runrun[k-1])

Submission status: Accepted

Solution code:
#d
k=int(input())

tree = list(range(1,10))
ans = [tree[:]]
koremade= 0
while koremade<=k:
    tree_next = []
    for t in tree:
        t_last = t%10
        if t_last==9:
            tt = [t*10+t%10-1, t*10+t%10]
        elif t_last==0:
            tt = [t*10+t%10, t*10+t%10+1]
        else:
            tt = [t*10+t%10-1, t*10+t%10, t*10+t%10+1]
        tree_next.extend(tt)
    tree=tree_next[:]
    ans.append(tree_next)
    koremade = sum(len(aa) for aa in ans)
#    print(koremade,k)

fans = []
for aa in ans:
    fans.extend(aa)
print(fans[k-1])

Submission status: Accepted

Solution code:
k = int(input())

def runrun(n):
  if n == 1:
    return([int(x) for x in range(1, 10)])
  key = runrun(n-1)
  key_2 = []
  for value in key:
    p = value%10
    for t in range(-1, 2):
      if 0 <= p+t <= 9:
        key_2.append(value*10+p+t)
  return key_2

runrun_list = []
for i in range(1, 11):
  runrun_list = runrun_list+runrun(i)
  runrun_list.sort()
print(runrun_list[k-1])

Submission status: Accepted

Solution code:
import heapq

k = int(input())

que = []
for i in range(1, 10):
    heapq.heappush(que, i)

ans = -1
for _ in range(k):
    ans = que[0]
    n = ans
    heapq.heappop(que)

    last = n % 10
    if last == 0:
        heapq.heappush(que, n * 10)
        heapq.heappush(que, n * 10 + 1)
    elif last == 9:
        heapq.heappush(que, n * 10 + 8)
        heapq.heappush(que, n * 10 + 9)
    else:
        heapq.heappush(que, n * 10 + last - 1)
        heapq.heappush(que, n * 10 + last)
        heapq.heappush(que, n * 10 + last + 1)

print(ans)

Submission status: Accepted

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

K = int(input())
print(ans[K-1])

Submission status: Accepted

Solution code:
K = int(input())
N = 10

S = [[] for _ in range(N + 1)]
for i in range(1, 10):
    S[1].append(i)

if K < 10:
    print(S[1][K - 1])
    exit()

cnt = 9
for i in range(2, N + 1):
    for j in S[i - 1]:
        k = j % 10
        if 1 <= k <= 8:
            T = [-1, 0, 1]
        elif k == 0:
            T = [0, 1]
        else:
            T = [-1, 0]
        for t in T:
            S[i].append(j * 10 + (k + t))
            cnt += 1
            if cnt == K:
                print(S[i][-1])
                exit()

Submission status: Accepted

Solution code:
k = int(input())
ans = [str(i) for i in range(1, 10)]
tmp = [str(i) for i in range(1, 10)]
cnt = 10
if k<=9:
    print(k)
else:
    while cnt<=k:
        ap = []
        for t in tmp:
            if t[-1]=='0':
                ap.append(t+'0')
                ap.append(t+'1')
            elif t[-1]=='9':
                ap.append(t+'8')
                ap.append(t+'9')
            else:
                l = int(t[-1])
                ap.append(t+str(l-1))
                ap.append(t+str(l))
                ap.append(t+str(l+1))
        cnt += len(ap)
        tmp = ap
    print(tmp[k-cnt])

Submission status: Accepted

Solution code:
base = list(map(str, range(1, 10)))
# print(base)
K = int(input())
count = 9
if K <= count:
    print(base[K-1])
else:
    while count < K:
        tmp = []
        for b in base:
            for i in range(max(0, int(b)%10-1), min(int(b)%10+2, 10)):
                tmp += [b + str(i)]
                count += 1
                if count == K:
                    break
            if count == K:
                break
        base = tmp
    print(tmp[-1])

Submission status: Accepted

Solution code:
N = int(input())
lun = ["1","2","3","4","5","6","7","8","9"]
ruiseki = 0
oldlevel = 9
nowlevel = 0
while len(lun) < N:
  for _ in range(oldlevel):
    if lun[ruiseki][-1] != "0":
      lun.append(lun[ruiseki] + str(int(lun[ruiseki][-1]) - 1))
      nowlevel += 1
    lun.append(lun[ruiseki] + lun[ruiseki][-1])
    nowlevel += 1
    if lun[ruiseki][-1] != "9":
      lun.append(lun[ruiseki] + str(int(lun[ruiseki][-1]) + 1))
      nowlevel += 1
    ruiseki += 1
  oldlevel = nowlevel
  nowlevl = 0
print(lun[N - 1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
K = int(input())

def Lunlun(K):
  if K<=9:
    return K
  q = [i for i in range(1,10)]
  now_index = 0
  while len(q)<K:
    now_number = q[now_index]
    now_1 = now_number%10
    if now_1==0:
      q.append(now_number*10)
      q.append(now_number*10+1)
    elif now_1==9:
      q.append(now_number*10+8)
      q.append(now_number*10+9)
    else:
      q.append(now_number*10+now_1-1)
      q.append(now_number*10+now_1)
      q.append(now_number*10+now_1+1)
    now_index += 1
  return q[K-1]

print(Lunlun(K))

Submission status: Accepted

Solution code:
k = int(input())
nums = [i for i in range(1,10)]
if k < 10:
    print(k)
    exit(0)
    
for x in nums:
    d = x%10
    if d != 0:nums.append(x*10+d-1)
    if len(nums) == k:
        print(nums[-1])
        break
    nums.append(x*10+d)
    if len(nums) == k:
        print(nums[-1])
        break
    if d !=9:nums.append(x*10+d+1)
    if len(nums) == k:
        print(nums[-1])
        break

Submission status: Accepted

Solution code:
k = int(input())
ls=[list() for _ in range(10)]

for i in range(10):
    ls[0].append(i)

for digit in range(1,10):
    for n in ls[digit-1]:
        fst=n//10**(digit-1)
        if fst>0:
            ls[digit].append((fst-1)*10**digit+n)
        if fst<9:
            ls[digit].append((fst+1)*10**digit+n)
        ls[digit].append((fst)*10**digit+n)

ansls=set()
for l in ls:
    ansls = ansls.union(set(l))

ansls=list(ansls)
ansls.sort()
print(ansls[k])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
num = []
def dfs(n, curnum):
    if n == 0:
        num.append(curnum)
        return
    last = int(curnum[-1])
    next_digits = []
    for k in [-1, 0, 1]:
        if 9 >= last + k >= 0:
            next_digits.append(str(last + k))
    for dig in next_digits:
        dfs(n-1, curnum + dig)

def main():
    K = I()
    for i in range(0, 100):
        for j in range(1, 10):
            dfs(i, str(j))
            if len(num) > K:
                print(num[K-1])
                return


main()

Submission status: Accepted

Solution code:
import copy as cp

K = int(input())

ans = ["1","2","3","4","5","6","7","8","9"]
old = cp.copy(ans)
num = len(ans)
while True:
    new = []
    for elem in old:
        if elem[-1] != "0":
            new.append(elem + str(int(elem[-1])-1))
        new.append(elem + elem[-1])
        if elem[-1] != "9":
            new.append(elem + str(int(elem[-1])+1))
    ans += new
    old = cp.copy(new)
    num = len(ans)
    if num >= 100000:
        break
print(ans[K-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
k=int(input())
ansl=[1,2,3,4,5,6,7,8,9]
l=["0","1","2","3","4","5","6","7","8","9"]
def f(x,p):
    if int(x+p)>3234566668:
        return
    x+=p
    ansl.append(int(x))
    if p=="0":
        f(x,"0")
        f(x,"1")
    elif p=="9":
        f(x,"9")
        f(x,"8")
    else:
        y=int(p)
        f(x,l[y-1])
        f(x,l[y])
        f(x,l[y+1])

for i in range(1,10):
    x=str(i)
    if x=="0":
        f(x,"0")
        f(x,"1")
    elif x=="9":
        f(x,"9")
        f(x,"8")
    else:
        y=int(x)
        f(x,l[y-1])
        f(x,l[y])
        f(x,l[y+1])
ansl.sort()
print(ansl[k-1])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
def even(n): return 1 if n%2==0 else 0

k = int(readline())
lst1 = []
#最大10桁であることが保証される
def func(num,now):
    if num[0] != "0":
        lst1.append(int(num))
    if now == 10:
        return
    s = num[0]
    s = int(s)
    if s == 0:
        func("0"+num,now+1)
        func("1"+num,now+1)
    elif s == 9:
        func("8"+num,now+1)
        func("9"+num,now+1)
    else:
        for i in range(s-1,s+2):
            func(str(i)+num,now+1)

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


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

    def lunlun(step=9, path=0):
        if step < 0:
            if path > 0:
                yield path
            return
        prev = (path // 10 ** (step + 1)) % 10
        for i in range(max(prev - 1, 0), min(prev + 1 if path else 9, 9) + 1):
            for x in lunlun(step - 1, path + i * 10 ** step):
                yield x
    
    for _, x in zip(range(k), lunlun()):
        pass
    print(x)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
################### <----------------------  Quicksilver_ ---------------------> ####################
arr=[['1','2','3','4','5','6','7','8','9']]
x=[9]
while sum(x)<100010:
    temp=[]
    for a in arr[-1]:
        z=int(a[-1])
        if z-1>=0:
            temp.append(a+str(z-1))
        temp.append(a+str(z))
        if z+1<10:
            temp.append(a+str(z+1))
    x.append(len(temp))
    arr.append(temp)
glob=[]
for a in arr:
    for b in a:
        glob.append(b)
n=int(input())
print(glob[n-1])

Submission status: Accepted

Solution code:
k = int(input())

ans = []
def solve(num):
    if num[0] != "0":
        ans.append(int(num))
    if len(num) == 10:
        return
    top = int(num[0])
    for i in range(max(top - 1, 0), min(top + 2, 10)):
        solve(str(i) + num)

for i in range(10):
    solve(str(i))
ans = sorted(ans)

print(ans[k - 1])

Submission status: Accepted

Solution code:
n=int(input())

count=0
i=1

#if n<10:
#    print(n)
#else:

now=[1]
for i in range(n-1):
    j=0
    tmp_len=len(now)
    while True:
        if j == tmp_len-1:
            if now[j]==9:
                for k in range(tmp_len):
                    now[k]=0
                now.append(1)
            else:
                now[j]+=1
                for k in reversed(range(tmp_len-1)):
                    now[k] = now[k+1]-1 if now[k+1] > 0 else 0
            break
        else:
            if now[j] <= now[j+1] and now[j]<9:
                now[j]+=1
                for k in reversed(range(j)):
                    now[k] = now[k+1]-1 if now[k+1] > 0 else 0
                break
            else:
                j+=1
print("".join(list(map(str,reversed(now)))))

Submission status: Accepted

Solution code:
import queue
K=int(input())
que=queue.Queue()
for i in range(1,10):
    que.put(i)
cnt=0
while True:
    x=que.get()
    y=x%10
    cnt+=1
    if cnt==K:
        print(x)
        break
    if y==0:
        que.put(10*x)
        que.put(10*x+1)
    elif y==9:
        que.put(10*x+8)
        que.put(10*x+9)
    else:
        que.put(10*x+y-1)
        que.put(10*x+y)
        que.put(10*x+y+1)

Submission status: Accepted

Solution code:
K = int(input())

cnt = 0
lst = [1,2,3,4,5,6,7,8,9]
def makeRunrun(s):
    if len(s) > 9:
        return
    for i in range(10):
        if abs(int(s[-1])-i) <= 1:
            ns = s+str(i)
            lst.append(int(ns))
            makeRunrun(ns)

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

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

Submission status: Accepted

Solution code:
ans = [1, 2, 3, 4, 5, 6, 7, 8, 9]
K = int(input())
if K <=9:
    print(K)
    exit()

b_num = 9
while True:
    num = 0
    tmp_ans = []
    for a in ans:
        if a%10 == 0:
            tmp_ans.append(a*10)
            tmp_ans.append(a*10+1)
            num += 2
        elif a % 10 == 9:
            tmp_ans.append(a*10+8)
            tmp_ans.append(a*10+9)
            num += 2
        else:
            k = a%10
            tmp_ans.append(a*10+k-1)
            tmp_ans.append(a*10+k)
            tmp_ans.append(a*10+k+1)
            num += 3
        if num+b_num >= K:
            tmp = K-b_num
            print(tmp_ans[tmp-1])
            exit()
    ans = tmp_ans
    b_num += num

Submission status: Accepted

Solution code:
# t=int(input(""))
t=1
for _ in range(t):
    k=int(input(""))
    A=[1,2,3,4,5,6,7,8,9]
    i=0
    while(len(A)<=k):
        if(A[i]%10==0):
            A.append(A[i]*10+(A[i])%10)
            A.append(A[i]*10+(A[i]+1)%10) 
        elif(A[i]%10==9):
            A.append(A[i]*10+(A[i]-1)%10)
            A.append(A[i]*10+(A[i])%10)
        else:
            A.append(A[i]*10+(A[i]-1)%10)
            A.append(A[i]*10+(A[i])%10)
            A.append(A[i]*10+(A[i]+1)%10)
        i+=1
    # print(A)
    print(A[k-1])

Submission status: Accepted

Solution code:
K = int(input())

from collections import deque

def dfs():
    ans = set()

    tmp = deque([str(n) for n in range(1,10)])
    ans = set()
    while len(ans) <= 10 ** 5 + 1000:
        num = tmp.popleft()
        ans.add(int(num))
        if num[-1] == "0":
            tmp.append(num + "0")
            tmp.append(num + "1")
        elif num[-1] == "9":
            tmp.append(num + "8")
            tmp.append(num + "9")
        else:
            tmp.append(num + str(int(num[-1]) - 1))
            tmp.append(num + str(int(num[-1])))
            tmp.append(num + str(int(num[-1]) + 1))
    
    return list(ans)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    K = int(rl())
    
    rnrn = [i for i in range(1, 10)]
    
    def calc(a):
        if 3234566667 < int(a):
            return
        
        if a[-1] == '0':
            tmp = a + '0'
            rnrn.append(int(tmp))
            calc(tmp)
            tmp = a + '1'
            rnrn.append(int(tmp))
            calc(tmp)
        elif a[-1] == '9':
            tmp = a + '9'
            rnrn.append(int(tmp))
            calc(tmp)
            tmp = a + '8'
            rnrn.append(int(tmp))
            calc(tmp)
        else:
            tmp = a + str(int(a[-1]) + 1)
            rnrn.append(int(tmp))
            calc(tmp)
            tmp = a + a[-1]
            rnrn.append(int(tmp))
            calc(tmp)
            tmp = a + str(int(a[-1]) - 1)
            rnrn.append(int(tmp))
            calc(tmp)
    
    for i in range(1, 10):
        calc(str(i))
    
    rnrn.sort()
    print(rnrn[K - 1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
k = int(input())

res = []
start = ["1","2","3","4","5","6","7","8","9"]
now = []
for times in range(9):
    for i in start:
        if i[-1] == "0":
            now.append(i + "0")
            now.append(i + "1")
        elif i[-1] != "9":
            now.append(i + str(int(i[-1]) - 1))
            now.append(i + str(int(i[-1])))
            now.append(i + str(int(i[-1]) + 1))
        elif i[-1] == "9":
            now.append(i + "8")
            now.append(i + "9")
    res.extend(start)
    start = now[:]
    now = []

res.extend(start)
print(res[k - 1])

Submission status: Accepted

Solution code:
def d_lunlun_number():
    import sys
    sys.setrecursionlimit(10**6)
    K = int(input())

    ans = []

    def dfs(num, current, digit_max):
        if current == digit_max:
            ans.append(num)
            return None
        for n in range(10):
            if abs((num % 10) - n) >= 2:
                continue
            dfs(num * 10 + n, current + 1, digit_max)

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

print(d_lunlun_number())

Submission status: Accepted

Solution code:
k=int(input())
from collections import deque
d=deque()
e=deque()

d.append(1)


d.append(2)


d.append(3)


d.append(4)


d.append(5)


d.append(6)



d.append(7)

d.append(8)


d.append(9)

cnt=0

while cnt<10**5+100:
    x=d.popleft()
    st=str(x)
    last=int(st[-1])
    if last==0:      
        e.append(x)
        d.append(10*x)
        cnt+=1
        d.append(10*x+1)
        cnt+=1

    elif last==9:
        e.append(x)
        d.append(10*x+8)
        cnt+=1
        d.append(10*x+9)
        cnt+=1

    else:
        e.append(x)
        d.append(10*x+last-1)
        cnt+=1
        d.append(10*x+last)
        cnt+=1
        d.append(10*x+last+1)
        cnt+=1
f=list(e)+list(d)
print(f[k-1])

Submission status: Accepted

Solution code:
def solve(k):

    if k <= 9:
        return k
    cnt = 9
    tmp = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    tmp_new = []
    while True:
        for p in tmp:
            m = p % 10
            if m == 0:
                tmp_new.append(p * 10)
                cnt += 1
                if cnt == k:
                    return tmp_new[-1]
                tmp_new.append(p * 10 + 1)
                cnt += 1
                if cnt == k:
                    return tmp_new[-1]
            elif m == 9:
                tmp_new.append(p * 10 + 8)
                cnt += 1
                if cnt == k:
                    return tmp_new[-1]
                tmp_new.append(p * 10 + 9)
                cnt += 1
                if cnt == k:
                    return tmp_new[-1]
            else:
                tmp_new.append(p * 10 + m - 1)
                cnt += 1
                if cnt == k:
                    return tmp_new[-1]
                tmp_new.append(p * 10 + m)
                cnt += 1
                if cnt == k:
                    return tmp_new[-1]
                tmp_new.append(p * 10 + m + 1)
                cnt += 1
                if cnt == k:
                    return tmp_new[-1]
        tmp = tmp_new
        tmp_new = []

    return 0


def main():
    k = int(input())
    res = solve(k)
    print(res)


def test():
    assert solve(15) == 23
    assert solve(1) == 1
    assert solve(13) == 21
    assert solve(100000) == 3234566667


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
def make(n, now):
    global cnt, k
    # print(n, now, cnt)
    if n == 0:
        cnt += 1
        if cnt == k:
            return now
        return
    # print(n, now, cnt)
    for i in range(max(0, now[-1] - 1), min(10, now[-1] + 2)):
        ans = make(n - 1, now + [i])
        if ans:
            return ans


k = int(input())
cnt = 0
n = 0
ans = [1]
while cnt < k:
    for i in range(1, 10):
        ans = make(n, [i])
        if ans:
            break
    n += 1
# print(ans)
for i in ans:
    print(i, end = "")

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

arr = ["1","2","3","4","5","6","7","8","9"]
bases = [0,1,2,3,4,5,6,7,8,9]
cnt = 9
q = deque(arr)

while cnt < K:
    num = q.popleft()
    idx = int(num[-1])
    for i in range(idx-1, idx+2):
        if i < 0 or i > 9:
            continue

        q.append(num + str(i))
        arr.append(num + str(i))
        cnt += 1

print(arr[K-1])

Submission status: Accepted

Solution code:

def get_runrun(runruns):
    newrunrun = []
    for runrun in runruns:
        last = runrun % 10
        if last != 0:
            newrunrun .append(runrun*10+last-1)
        if last != 9:
            newrunrun .append(runrun*10+last+1)
        newrunrun .append(runrun*10+last)
    return newrunrun




def resolve():
    K= int(input())
    runruns = list(range(1,10))

    if K < 10:
        print(K)
        return
    
    while True:
        if len(runruns) >= K:
            break
        K -= len(runruns)
        runruns= get_runrun(runruns)
        runruns.sort()

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



if __name__ == "__main__":

    resolve()

Submission status: Accepted

Solution code:
k=int(input())
ans=[1,2,3,4,5,6,7,8,9]
def r(a):
    if a%10==0:
        return a*10,a*10+1
    elif a%10==9:
        return a*10+8,a*10+9
    else:
        x=a*10+(a%10)
        return x-1,x,x+1
t=0
while len(ans)<k:
    ans.extend(r(ans[t]))
    t+=1
print(ans[k-1])

Submission status: Accepted

Solution code:
K = int(input())

lunlun = [[] for _ in range(11)]
lunlun[1] = list(range(1, 10))

for i in range(2, 11):
    tmp = []
    for j in lunlun[i-1]:
        x = int(str(j)[-1])
        if 1 <= x <= 8:
            tmp.extend([int(str(j) + str(x-1)), int(str(j) + str(x)), int(str(j) + str(x+1))])
        elif int(str(j)[-1]) == 0:
            tmp.extend([int(str(j) + str(x)), int(str(j) + str(x+1))])
        else:
            tmp.extend([int(str(j) + str(x-1)), int(str(j) + str(x))])
    lunlun[i] = list(set(tmp))

lunlun_flat = []
for x in lunlun:
    for y in x:
        lunlun_flat.append(y)
lunlun_flat = list(set(lunlun_flat))
lunlun_flat.sort()

print(lunlun_flat[K-1])

Submission status: Accepted

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

sys.setrecursionlimit(10**7)

k = int(input())
data = [1,2,3,4,5,6,7,8,9]
def dfs(prenum,numberstr):
  if int(numberstr) > 3234566667:return
  if prenum - 1 >= 0:
    data.append(int(numberstr+str(prenum-1)))
    dfs(prenum-1,numberstr+str(prenum-1))
  data.append(int(numberstr+str(prenum)))
  dfs(prenum,numberstr+str(prenum))
  if prenum +1 <= 9:
    data.append(int(numberstr+str(prenum+1)))
    dfs(prenum+1,numberstr+str(prenum+1))
for i in range(1,10):
  dfs(i,str(i))
data.sort()
print(data[k-1])
# print(data[:20])
# print(len(data))

Submission status: Accepted

Solution code:
k=int(input())
cand=[[1,2,3,4,5,6,7,8,9]]
for _ in range(9):
    tmp=[]
    for val in cand[-1]:
        s=str(val)
        if s[-1]=='0':
            tmp.append(val*10)
            tmp.append(val*10+1)
        elif s[-1]=='9':
            tmp.append(val*10+8)
            tmp.append(val*10+9)
        else:
            tmp.append(val*10+(int(s[-1])-1))
            tmp.append(val*10+(int(s[-1])))
            tmp.append(val*10+(int(s[-1])+1))
    cand.append(tmp)
ans=[]
for i in range(len(cand)):
    for val in cand[i]:
        ans.append(val)
ans=sorted(ans)
print(ans[k-1])