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:

k = int(input())
data = [str(i) for i in range(1,10)]
ans = [i for i in range(1,10)]
for i in range(9):
    data2 = []
    for x in data:
        j = int(x[-1])
        if j-1>=0:
            y = x+str(j-1)
            data2.append(y)
            ans.append(int(y))
        y = x+str(j)
        data2.append(y)
        ans.append(int(y))
        if j+1<10:
            y = x + str(j+1)
            data2.append(y)
            ans.append(int(y))
    data = data2

print(ans[k-1])

Submission status: Accepted

Solution code:
n = int (input())
runrun = [i+1 for i in range(9)]
count = 9
if n < 10:
    print(runrun[n-1])
    exit(0)


def calc_next_runrun(runrun, count):
    new_runrun=[]
    for run in runrun:
        hitoketa = run % 10
        if hitoketa == 0:
            new_runrun.append(run*10 + 0)
            new_runrun.append(run*10 + 1)
        elif hitoketa == 9:
            new_runrun.append(run*10 + 8)
            new_runrun.append(run*10 + 9)
        else:
            new_runrun.append(run*10 + hitoketa -1)
            new_runrun.append(run*10 + hitoketa )
            new_runrun.append(run*10 + hitoketa +1)
    new_count = len(new_runrun)
    if new_count + count >= n:
        print(new_runrun[n-count-1])
    else:
        calc_next_runrun(new_runrun, new_count+count)

calc_next_runrun(runrun, count)

Submission status: Accepted

Solution code:
k=int(input())
l=[]
for i1 in range(10):
  l.append(i1)
  for i2 in range(max(i1-1,0),min(i1+2,10)):
    l.append(i1*(10**1)+i2)
    for i3 in range(max(i2-1,0),min(i2+2,10)):
      l.append(i1*(10**2)+i2*(10**1)+i3)
      for i4 in range(max(i3-1,0),min(i3+2,10)):
        l.append(i1*(10**3)+i2*(10**2)+i3*(10**1)+i4)
        for i5 in range(max(i4-1,0),min(i4+2,10)):
          l.append(i1*(10**4)+i2*(10**3)+i3*(10**2)+i4*(10**1)+i5)
          for i6 in range(max(i5-1,0),min(i5+2,10)):
            l.append(i1*(10**5)+i2*(10**4)+i3*(10**3)+i4*(10**2)+i5*(10**1)+i6)
            for i7 in range(max(i6-1,0),min(i6+2,10)):
              l.append(i1*(10**6)+i2*(10**5)+i3*(10**4)+i4*(10**3)+i5*(10**2)+i6*(10**1)+i7)
              for i8 in range(max(i7-1,0),min(i7+2,10)):
                l.append(i1*(10**7)+i2*(10**6)+i3*(10**5)+i4*(10**4)+i5*(10**3)+i6*(10**2)+i7*(10**1)+i8)
                for i9 in range(max(i8-1,0),min(i8+2,10)):
                  l.append(i1*(10**8)+i2*(10**7)+i3*(10**6)+i4*(10**5)+i5*(10**4)+i6*(10**3)+i7*(10**2)+i8*(10**1)+i9)
                  for i10 in range(max(i9-1,0),min(i9+2,10)):
                    l.append(i1*(10**9)+i2*(10**8)+i3*(10**7)+i4*(10**6)+i5*(10**5)+i6*(10**4)+i7*(10**3)+i8*(10**2)+i9*(10**1)+i10)

l=list(set(l))
l.sort()
print(l[k])

Submission status: Accepted

Solution code:
K = int(input())
A = "0123456789"
S = []
def f(n):
    global A,S
    if len(n)>10:return
    if n[-1]=="0":
        D=(n+"0",n+"1")
    elif n[-1]=="9":
        D=(n+"9",n+"8")
    else:
        a = A.index(n[-1])
        D=(n+A[a],n+A[a-1],n+A[a+1])
    for d in D:
        S.append(int(d))
        f(d)

for i in range(1,10):
    S.append(i)
    f(str(i))
S.sort()
print(S[K-1])

Submission status: Accepted

Solution code:
import sys

k = int(input())

count = 1
num = 1
l = [str(i+1) for i in range(9)]

if k < 10:
	print(l[k-1])
	sys.exit()

c = 0
while True:
	num = l[c]
	num = int(num[-1])
	if num != 0:
		l.append(l[c]+str(num-1))
	l.append(l[c]+str(num))
	if num != 9:
		l.append(l[c]+str(num+1))

	c += 1
	if len(l) >= k:
		break

print(l[k-1])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
q = deque([str(i) for i in reversed(range(1,10,1))])

count = 0

while True:
    item = q.pop()
    last_int = int(item[-1])

    if last_int != 0:
        q.appendleft(item+str(last_int-1))
    q.appendleft(item+str(last_int))

    if last_int != 9:
        q.appendleft(item+str(last_int+1))

    count += 1
    if count == n:
        break

print(item)

Submission status: Accepted

Solution code:
K = int(input())

runrun = []
run = list(range(0,10))
runrun.extend(run)

for i in range(10):
    k = 10**i
    trun = []
    for r in run:
        t = r//k
        trun.append(t*10*k + r)
        if t > 0:
            trun.append((t-1)*10*k + r)
        if t < 9:
            trun.append((t+1)*10*k + r)
    runrun.extend(trun)
    run = trun

runrun = list(set(runrun))
runrun.sort()
print(runrun[K])

Submission status: Accepted

Solution code:
from copy import deepcopy
def main():
    K = int( input())
    T = [[1,2,3,4,5,6,7,8,9]]
    for i in range(10):
        S = T[i]
        R = []
        for s in S:
            t = s%10
            if t == 0:
                R.append(s*10)
                R.append(s*10+1)
            elif t%10 == 9:
                R.append(s*10+9)
                R.append(s*10+8)
            else:
                R.append(s*10+t)
                R.append(s*10+t+1)
                R.append(s*10+t-1)
        T.append(R)
    ANS = []
    for t in T:
        ANS.extend(t)
    ANS.sort()
    print(ANS[K-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(lambda:defaultdict(list))

def cal(s,k):
    if k == 0:
        d[0][s].append(str(s))
    else:
        m = max(0,s-1)
        M = min(9,s+1)
        for i in range(m,M+1):
            for j in d[k-1][i]:
                d[k][s].append(str(s)+j)

for k in range(10):
    for s in range(10):
        cal(s,k)

ans = []
for k in range(10):
    for s in range(10):
        for i in d[k][s]:
            ans.append(int(i))

ans = list(set(ans))
ans.sort()
ans = ans[1:]
k = int(input())
print(ans[k-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def solve(K: int):
    s = set(range(1, 10))
    while len(s) <= 10 ** 5:
        ss = set(s)
        for n in s:
            t = n % 10
            ss.add(n * 10 + t)
            if t != 0:
                ss.add(n * 10 + t - 1)
            if t != 9:
                ss.add(n * 10 + t + 1)
        s = ss
    s = sorted(s)
    print(s[K-1])


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def lunlun(head,keta,now):
    if keta==1:
        A.append(int(now))
        return 0
    else:
        for i in range(-1,2):
            if 0<=head+i<=9:
                lunlun(head+i,keta-1,now+str(head+i))
A = []
for i in range(1,10):
    for j in range(1,11):
        lunlun(i,j,str(i))
#print(A)
#print(len(A))
A.sort()
K = int(input())
print(A[K-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from queue import Queue
k = int(input()) + 1
q = Queue()
q.put(0)
while not q.empty():
    n = q.get()
    k -= 1
    if k == 0:
        print(n)
        exit()
    if n == 0:
        for i in range(9):
            q.put(i + 1)
    else:
        last = int(str(n)[-1])
        if last > 0:
            q.put(n * 10 + last - 1)
        q.put(n * 10 + last)
        if last < 9:
            q.put(n * 10 + last + 1)

Submission status: Accepted

Solution code:
import sys

# import bisect
from collections import Counter, deque, defaultdict

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    run = [0] * 100000
    que = deque()

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

    cnt = 0
    while que:
        x = que.popleft()
        cnt += 1
        if cnt == k:
            print(int(x))
            sys.exit()

        xlast = x[-1]
        if xlast == "0":
            for i in ("0", "1"):
                nx = x + i
                que.append(nx)
        elif xlast == "9":
            for i in ("8", "9"):
                nx = x + i
                que.append(nx)
        else:
            for i in range(int(xlast) - 1, int(xlast) + 2):
                nx = x + str(i)
                que.append(nx)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k = int(input())


def make_runrun(n, depth):
    r = [n]
    if depth == 0:
        return r
    x = n % 10

    if x >= 1:
        r.extend(make_runrun(n * 10 + x - 1, depth - 1))
    r.extend(make_runrun(n * 10 + x, depth - 1))
    if x < 9:
        r.extend(make_runrun(n * 10 + x + 1, depth - 1))
    
    return r

r = []
for i in range(1, 10):
    r.extend(make_runrun(i, 10))
r = sorted(r)
print(r[k - 1])

Submission status: Accepted

Solution code:
k = int(input())

cnt = 9
LIM = 10**5+5
gen = [ [1, 2, 3, 4, 5, 6, 7, 8, 9] ]
other = [1,2,3,4,5,6,7,8,9]

while cnt < LIM:
	nw = []
	i = gen[-1]
	for j in i:
		dig = j % 10
		if( dig > 0 ):
			num = j * 10 + (dig-1)
			nw.append(num)
			other.append(num)
			cnt += 1
		num = j * 10 + dig
		nw.append(num)
		other.append(num)
		cnt += 1
		if dig < 9:
			num = j * 10 + (dig + 1)
			nw.append(num)
			other.append(num)
			cnt += 1
	gen.append(nw)
other = sorted(other)
print(other[k-1])

Submission status: Accepted

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

res = [1, 2, 3, 4, 5, 6, 7, 8, 9]
def dfs(x, k):
  global res
  if k == 0:
    res.append(x)
    return
  for i in range(3):
    y = i - 1 + (x % 10)
    if y in range(10):
      dfs(x * 10 + y, k - 1)
for t in range(1, 11):
  for x in range(1, 10):
    dfs(x, t)
res.sort()
print(res[K - 1])

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    K = iip(False)

    rl = []
    rl_next = list(range(1, 10))
    while True:
        rl_current = [i for i in rl_next]
        rl_next = []
        if len(rl) > 10 ** 5 + 10000:
            break
        for i in rl_current:
            rl.append(i)
            i0 = i * 10
            i1 = i % 10

            if i1 != 0:
                rl_next.append(i0+i1-1)
            rl_next.append(i0+i1)
            if i1 != 9:
                rl_next.append(i0+i1+1)

    #print(rl[:10])
    return rl[K-1]



#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    k=II()
    run=list(range(1,10))
    cur=list(range(1,10))
    while len(run)<k:
        nxt=[]
        for r in cur:
            e=r%10
            nxt.append(r*10+e)
            run.append(r*10+e)
            if e!=0:
                nxt.append(r*10+e-1)
                run.append(r*10+e-1)
            if e!=9:
                nxt.append(r*10+e+1)
                run.append(r*10+e+1)
        cur=nxt
    run.sort()
    print(run[k-1])

main()

Submission status: Accepted

Solution code:
K=int(input())

one=['1','2','3','4','5','6','7','8','9']
for i in range(10**5+1):
    if one[i][-1]=='0':
        one.append(one[i]+'0')
        one.append(one[i]+'1')
    elif 1<=int(one[i][-1])<=8:
        one.append(one[i]+str(int(one[i][-1])-1))
        one.append(one[i]+str(int(one[i][-1])))
        one.append(one[i]+str(int(one[i][-1])+1))
    else:
        one.append(one[i]+'8')
        one.append(one[i]+'9')

print(one[K-1])

Submission status: Accepted

Solution code:
k = int(input())

count = 0
i = 1
while True:
    s = str(i)
    for j in range(len(s) - 1):
        if abs(int(s[j]) - int(s[j+1])) > 1:
            i += 10 ** (len(s)-j-2)
            break
    else:
        count += 1
        if count == k:
            break
        i += 1

print(i)

Submission status: Accepted

Solution code:
from collections import deque
K = [int(i) for i in input().split()][0]

que = deque()
for i in range(1, 10):
  que.append(i)
k = 0
while k < K:
  k += 1
  p = que.popleft()
  i = p % 10
  if len(que) + k < K:
      if i > 0:
        que.append(p*10 + i -1)
      que.append(p*10 + i)
      if i < 9:
        que.append(p*10 + i + 1)
  
print(p)

Submission status: Accepted

Solution code:
import copy
K = int(input())
ans, nex = [i for i in range(1, 10)], [i for i in range(1, 10)]
for i in range(10):
    pre, nex = copy.deepcopy(nex), []
    for p in pre:
        if p % 10 != 0:
            ans.append(p * 10 + p % 10 - 1)
            nex.append(p * 10 + p % 10 - 1)
        ans.append(p * 10 + p % 10)
        nex.append(p * 10 + p % 10)
        if p % 10 != 9:
            ans.append(p * 10 + p % 10 + 1)
            nex.append(p * 10 + p % 10 + 1)

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

Submission status: Accepted

Solution code:
k = int(input())

r = [[i,i] for i in range(1, 10)]
l = [0]
cnt = len(r)
if k <= cnt:
    print(k)
    exit()

k -= 1
k -= cnt
for _ in range(100):
    nr = []
    x = 10**(_+1)
    for i in l:
        nr.append([x+i, 1])
    for i, start in r:
        for j in range(start-1,start+2):
            if j == 0:
                l.append(i)
            elif 10 > j > 0:
                nr.append([j*x+i, j])

    if len(nr) > k:
        nr.sort()
        print(nr[k][0])
        exit()
    k -= len(nr)
    r = nr

Submission status: Accepted

Solution code:
k = int(input())

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

count = 0
for _ in range(k):
    i = d.popleft()
    dd = [i * 10 + (i % 10) + j - 1 for j in range(3)]
    dd = dd[1:] if i % 10 == 0 else dd[:2] if i % 10 == 9 else dd
    for j in dd:
        d.append(j)

else:
    print(i)

Submission status: Accepted

Solution code:
K = int(input())
runrun = [[] for _ in range(11)]
runrun[1] = [i for i in range(1, 10)]
for i in range(1, 10):
    run = runrun[i]
    for r in run:
        t = r%10
        if t != 0:
            runrun[i+1].append(r*10+t-1)
        runrun[i+1].append(r*10+t)
        if t != 9:
            runrun[i+1].append(r*10+t+1)
for i in range(11):
    if len(runrun[i]) <= K:
        K -= len(runrun[i])
        continue
    print(runrun[i][K-1])
    break

Submission status: Accepted

Solution code:
def solve():
    K = int(input())
    cnt = 0
    n_digit = 1
    numbers = []
    while cnt < K:
        numbers = []
        dfs("", numbers, n_digit)
        cnt += len(numbers)
        n_digit += 1
    
    print(numbers[-(cnt - K + 1)])
    
def dfs(now, numbers, n_digit):
    if len(now) == n_digit:
        numbers.append(now)
        return
    
    if now == "":
        for i in range(1,10):
            dfs(now+str(i), numbers, n_digit)
    else:
        last_num = int(now[-1])
        if last_num - 1 >= 0:
            dfs(now+str(last_num-1), numbers, n_digit)

        dfs(now+str(last_num), numbers, n_digit)

        if last_num + 1 <= 9:
            dfs(now+str(last_num+1), numbers, n_digit)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
K = int(input())

N = [0]

for _ in range(K):
    i = 0
    while i < len(N) and N[i] == 9:
        i += 1
    while i+1 < len(N) and N[i] == N[i+1]+1:
        i += 1
    if i == len(N):
        N = [0]*len(N) + [1]
    else:
        N[i] += 1
        i -= 1
        while i >= 0:
            N[i] = max(N[i+1]-1,0)
            i -= 1

print(*reversed(N),sep='')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from queue import Queue

K = int(input())

q = Queue()
if K<10:
    print(K)
    sys.exit()

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

idx = 9

while idx<=K and not(q.empty()):
    cur = q.get()
    num = cur%10
    if num==0:
        for i in range(2):
            nxt = cur*10 + (num+i)
            if idx+1==K:
                ans = nxt
                break
            idx += 1
            q.put(nxt)
        else:
            continue
        break

    elif num==9:
        for i in range(2):
            nxt = cur*10 + (num+i-1)
            if idx+1==K:
                ans = nxt
                break
            idx += 1
            q.put(nxt)
        else:
            continue
        break
        
    else:
        for i in range(3):
            nxt = cur*10 + (num+i-1)
            if idx+1==K:
                ans = nxt
                break
            idx += 1
            q.put(nxt)
        else:
            continue
        break

print(ans)

Submission status: Accepted

Solution code:
K = int(input())
r = [[] for _ in range(10)]
r[0] = list(range(1,10))
for i in range(9):
    for a in r[i]:
        s = str(a)
        d = a%10
        for j in range(d-1,d+2):
            if not 0 <= j <= 9: continue
            r[i+1].append(int(s+str(j)))

for i in range(10):
    if K >= len(r[i]):
        K -= len(r[i])
    else:
        print(r[i][K-1])
        break

Submission status: Accepted

Solution code:
k=int(input())
k-=1
z=[]
zz=[]
for i in range(1,10):
    z.append(str(i))
zz+=z
for i in range(9):
    tmp=[]
    for j in z:
        e=int(j[-1])
        for p in range(3):
            if 0<=e+(p-1)<=9:
                tmp.append(j+str(e+p-1))      
    z=tmp
    zz+=z
for i in range(len(zz)):
    zz[i]=int(zz[i])
zz.sort()

print(zz[k])

Submission status: Accepted

Solution code:
K = int(input())
W = 0
k = 0
while True:
    W += 1
    pool = [(i,0) for i in range(9,0,-1)]
    history = [None] * W
    while pool:
        n, w = pool.pop()
        history[w] = n
        if w == W-1:
            k += 1
            if k == K:
                for j in range(W):
                    print(history[j], end='')
                print()
                exit()
        else:
            if n < 9: pool.append((n+1,w+1))
            pool.append((n,w+1))
            if n > 0: pool.append((n-1,w+1))

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

k = 10**5
pp = [i+1 for i in range(9)]
kkk = [i+1 for i in range(9)]
while True:
    ad = []
    for i in pp:
        po = str(i)[-1]
        if po != "0":
            ad.append(i*10+int(po)-1)
            kkk.append(i*10+int(po)-1)
        if po != "9":
            ad.append(i*10+int(po)+1)
            kkk.append(i*10+int(po)+1)
        kkk.append(i*10+int(po))
        ad.append(i*10+int(po))
        pp = ad
        
    if len(kkk) >= 10**5:
        break
kkk.sort()
n = onem()
print(kkk[n-1])

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,boundary=1,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0



k=I()
c=0

m=list(range(1,10))
ans=[]
n=10
for i in range(n):
    nx=[]
    for j in m:
        d=j%10
        tmp=[j*10+d+x for x in range(-1,2)]
        if d==0:
            tmp=tmp[1:]
        elif d==9:
            tmp=tmp[:2]
        nx+=tmp
    ans+=m
    m=nx[:]
    
print(ans[k-1])

Submission status: Accepted

Solution code:
K = int(input())

if K < 10:
    print(K)
    exit()
K -= 9

prev = list(range(1, 10))
while True:
    lunlun = []
    for p in prev:
        if p % 10 == 0:
            lunlun.append(p * 10 + 0)
            lunlun.append(p * 10 + 1)
        elif p % 10 == 9:
            lunlun.append(p * 10 + 8)
            lunlun.append(p * 10 + 9)
        else:
            for i in range(p % 10 - 1, p % 10 + 2):
                lunlun.append(p * 10 + i)
    if K <= len(lunlun):
        print(lunlun[K-1])
        break
    K -= len(lunlun)
    prev = lunlun

Submission status: Accepted

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

K = int(input())

# 末端桁がjの時のやつ
dp = [[] for i in range(10)]
answer = []
for j in range(1, 10):
    dp[0].append(j)
    answer.append(j)

cnt = 10
for i in range(1, 100):
    for d in dp[i - 1]:
        dd = d % 10
        for j in range(10):
            if j == dd - 1 or j == dd or j == dd + 1:
                dp[i].append(d * 10 + j)
                answer.append(d * 10 + j)
    if len(answer) > 10 ** 5:
        break
answer.sort()
print(answer[K - 1])

Submission status: Accepted

Solution code:
from collections import deque
INF=3234566667
X=[]
q=deque([i for i in range(1,10)])
D=[[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(len(q)>0):
    r=q.popleft()
    X.append(r)
    for m in D[r%10]:
        p=r*10+m
        if p<=INF:
            q.append(p)
X.sort()
K=int(input())
print(X[K-1])

Submission status: Accepted

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

maxK = 10**5
#maxK = 20

K = int(input())

As = []
def dfs(i, maxD, x):
    if i == maxD:
        As.append(x)
        if len(As) >= maxK:
#            print(As)
            print(As[K-1])
            sys.exit()
    else:
        y = x%10
        x *= 10
        if y-1 >= 0:
            dfs(i+1, maxD, x+y-1)
        dfs(i+1, maxD, x+y)
        if y+1 <= 9:
            dfs(i+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
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

K = int(input())

d = {
    "0": [0, 1],
    "1": [0, 1, 2],
    "2": [1, 2, 3],
    "3": [2, 3, 4],
    "4": [3, 4, 5],
    "5": [4, 5, 6],
    "6": [5, 6, 7],
    "7": [6, 7, 8],
    "8": [7, 8, 9],
    "9": [8, 9],
}

cand = set(i for i in range(1, 10))
while True:
    if len(cand) >= K:
        ans = sorted(list(cand))[K - 1]
        break
    K -= len(cand)
    new = set()
    for s in cand:
        val = d[str(s)[-1]]
        for v in val:
            new.add(s * 10 + v)
    cand = new


print(ans)

Submission status: Accepted

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

count = 9
while True:
    cur = []
    for e in pre:
        last = e%10
        for i in [-1, 0, 1]:
            nxt = last+i
            if 0<=nxt<=9:
                count += 1
                value = 10*e + nxt
                if count == k:
                    print(value)
                    exit()
                cur.append(value)

    pre = cur

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
q = deque(tuple(range(1, 10)))
cnt = 0
while cnt < K:
    v = q.popleft()
    cnt += 1
    for i in [-1, 0, 1]:
        c = int(str(v)[-1]) + i
        if 0 <= c <= 9:
            q.append(v * 10 + c)

print(v)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    K = int(input())
    ans = list("123456789")
    tmp = ans.copy()
    while True:
        tmp2 = []
        for t in tmp:
            for i in range(int(t[-1]) - 1, int(t[-1]) + 2):
                if 0 <= i < 10:
                    tmp2.append(t + str(i))
        tmp = tmp2.copy()
        ans += tmp
        if len(ans) >= K:
            break

    print(ans[K - 1])


if __name__ == "__main__":
    main()