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:
def add():
    for i in ans[cnt-1]:
        i=str(i)
        last=i[-1]
        last=int(last)
        for j in range(last-1,last+2):
            if j==10 or j==-1:
                continue
            tmp=i
            tmp+=str(j)
            ans[cnt].append(int(tmp))

n=int(input())
ans=[[]for i in range(10)]
cnt=1
for i in range(1,10):
    ans[0].append(i)

for i in range(9):
    add()
    cnt+=1
merged=[]
for i in ans:
    merged+=i
merged=sorted(merged)
print(merged[n-1])

Submission status: Accepted

Solution code:
def MI():return map(int,input().split())
def LI():return list(MI())
K=int(input())#10**5
# import numpy as np
# def lunlun(x):
#     S=list(str(x))
#     nums=list(map(int,S))
#     a=np.diff(nums)
#     if (np.abs(a)<=1).all():
#         return True
#     else:
#         False

Ls=[1,2,3,4,5,6,7,8,9]
Ls2=[];Ls3=[];Ls4=[];Ls5=[];Ls6=[];Ls7=[];Ls8=[];Ls9=[];Ls10=[];
#max 3234566667 10keta
for i in Ls:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls2+=(i*10+8),
        Ls2+=(i*10+9),
    elif migihaji=="0":
        Ls2+=(i*10+1),
        Ls2+=(i*10+0),
    else:
        Ls2+=(i*10+int(migihaji)+1),
        Ls2+=(i*10+int(migihaji)+0),
        Ls2+=(i*10+int(migihaji)-1),
# print(sorted(Ls2))

for i in Ls2:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls3+=(i*10+8),
        Ls3+=(i*10+9),
    elif migihaji=="0":
        Ls3+=(i*10+1),
        Ls3+=(i*10+0),
    else:
        Ls3+=(i*10+int(migihaji)+1),
        Ls3+=(i*10+int(migihaji)+0),
        Ls3+=(i*10+int(migihaji)-1),



for i in Ls3:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls4+=(i*10+8),
        Ls4+=(i*10+9),
    elif migihaji=="0":
        Ls4+=(i*10+1),
        Ls4+=(i*10+0),
    else:
        Ls4+=(i*10+int(migihaji)+1),
        Ls4+=(i*10+int(migihaji)+0),
        Ls4+=(i*10+int(migihaji)-1),





for i in Ls4:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls5+=(i*10+8),
        Ls5+=(i*10+9),
    elif migihaji=="0":
        Ls5+=(i*10+1),
        Ls5+=(i*10+0),
    else:
        Ls5+=(i*10+int(migihaji)+1),
        Ls5+=(i*10+int(migihaji)+0),
        Ls5+=(i*10+int(migihaji)-1),





for i in Ls5:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls6+=(i*10+8),
        Ls6+=(i*10+9),
    elif migihaji=="0":
        Ls6+=(i*10+1),
        Ls6+=(i*10+0),
    else:
        Ls6+=(i*10+int(migihaji)+1),
        Ls6+=(i*10+int(migihaji)+0),
        Ls6+=(i*10+int(migihaji)-1),





for i in Ls6:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls7+=(i*10+8),
        Ls7+=(i*10+9),
    elif migihaji=="0":
        Ls7+=(i*10+1),
        Ls7+=(i*10+0),
    else:
        Ls7+=(i*10+int(migihaji)+1),
        Ls7+=(i*10+int(migihaji)+0),
        Ls7+=(i*10+int(migihaji)-1),





for i in Ls7:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls8+=(i*10+8),
        Ls8+=(i*10+9),
    elif migihaji=="0":
        Ls8+=(i*10+1),
        Ls8+=(i*10+0),
    else:
        Ls8+=(i*10+int(migihaji)+1),
        Ls8+=(i*10+int(migihaji)+0),
        Ls8+=(i*10+int(migihaji)-1),





for i in Ls8:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls9+=(i*10+8),
        Ls9+=(i*10+9),
    elif migihaji=="0":
        Ls9+=(i*10+1),
        Ls9+=(i*10+0),
    else:
        Ls9+=(i*10+int(migihaji)+1),
        Ls9+=(i*10+int(migihaji)+0),
        Ls9+=(i*10+int(migihaji)-1),





for i in Ls9:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls10+=(i*10+8),
        Ls10+=(i*10+9),
    elif migihaji=="0":
        Ls10+=(i*10+1),
        Ls10+=(i*10+0),
    else:
        Ls10+=(i*10+int(migihaji)+1),
        Ls10+=(i*10+int(migihaji)+0),
        Ls10+=(i*10+int(migihaji)-1),




Lunluns=Ls+Ls2+Ls3+Ls4+Ls5+Ls6+Ls7+Ls8+Ls9+Ls10
Lunluns.sort()

print(Lunluns[K-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

lst = []
def dfs(N, n, s):
    if n == N:
        lst.append(s)
        return
    s_ = s*10
    s0 = s%10
    if s0 == 0:
        for i in range(0, 2):
            dfs(N, n+1, s_+i)
    elif s0 == 9:
        for i in range(8, 10):
            dfs(N, n+1, s_+i)
    else:
        for i in range(s0-1, s0+2):
            dfs(N, n+1, s*10+i)

K = int(input())
for i in range(1, 11):
    for j in range(1, 10):
        dfs(i, 1, j)
print(lst[K-1])

Submission status: Accepted

Solution code:
import sys
k = int(input())
if k < 10:
    print(k)
    sys.exit()

total = 9
lunluns = []
for i in range(10, 100):
    if abs(i // 10 - i % 10) <= 1:
        lunluns.append('{:02d}'.format(i))
if k < 10 + len(lunluns):
    print(lunluns[k - 10])
    sys.exit()
total = 9 + len(lunluns)

while True:
    new = []
    for lunlun in lunluns:
        if lunlun[-1] == '0':
            new.append(lunlun + '0')
            new.append(lunlun + '1')
        elif lunlun[-1] == '9':
            new.append(lunlun + '8')
            new.append(lunlun + '9')
        else:
            new.append(lunlun + str(int(lunlun[-1])-1))
            new.append(lunlun + lunlun[-1])
            new.append(lunlun + str(int(lunlun[-1])+1))

    lunluns = new
    if total + len(lunluns) >= k:
        print(lunluns[k - total - 1])
        break
    total += len(lunluns)

Submission status: Accepted

Solution code:
k = int(input())
if k <= 9:
    print(k)
    exit()
lunlun = [[1,2,3,4,5,6,7,8,9]]
count = 9
digit = 1
while True:
    lunlun.append([])
    for i in lunlun[digit-1]:
        if i % 10 == 0:
            x = i*10
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
            x = i*10+1
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
        elif i % 10 == 9:
            x = i*10+8
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
            x = i*10+9
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
        else:
            y = i % 10
            x = i*10+y-1
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
            x = i*10+y
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
            x = i*10+y+1
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
    digit += 1

Submission status: Accepted

Solution code:
from sys import exit
from collections import deque
K = int(input())
if K < 13:
    print(K)
    exit()

que = deque([i for i in range(1, 10)])
counter = 0

while True:
    counter += 1
    if counter == K:
        print(que.popleft())
        exit()
    val = que.popleft()
    before = val % 10
    if before - 1 >= 0:
        que.append(val*10+(before-1))
    que.append(val*10+before)
    if before + 1 <= 9:
        que.append(val*10+(before+1))

Submission status: Accepted

Solution code:
def plus(x):
    X = str(x)
    p = int(X[len(X)-1])
    if p == 0:
        return(int(X+str(p)), int(X+str(p+1)))
    elif p == 9:
        return(int(X+str(p-1)), int(X+str(p)))
    else:
        return(int(X+str(p-1)), int(X+str(p)), int(X+str(p+1)))
    
A,B,C,D,E,F,G,H,I,J=[],[],[],[],[],[],[],[],[],[]
for i in range(1,10):
    A.append(i)
for i in A:
    B.extend(plus(i))
for i in B:
    C.extend(plus(i))
for i in C:
    D.extend(plus(i))    
for i in D:
    E.extend(plus(i))    
for i in E:
    F.extend(plus(i))
for i in F:
    G.extend(plus(i))
for i in G:
    H.extend(plus(i))
for i in H:
    I.extend(plus(i))
for i in I:
    J.extend(plus(i))

ans = A+B+C+D+E+F+G+H+I+J
print(ans[int(input())-1])

Submission status: Accepted

Solution code:
k = int(input())
dp = [[0]*10 for i in range(12)]  # dp[i][j]: i桁で先頭がj

for i in range(10):
    dp[1][i] = 1

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

ans = 0
for i in range(11):
    for j in range(1,10):
        if k > dp[i][j]:
            k -= dp[i][j]
        else:
            ni = i-1
            nj = j
            ans = j
            break
    if ans > 0:
        break


while ni > 0:
    for j in range(nj-1,nj+2):
        if j<0 or j>9:
            continue
        if k > dp[ni][j]:
            k -= dp[ni][j]
        else:
            ans = ans*10+j
            nj = j
            break
    ni -= 1
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import queue
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")

def cnt(n, k):

    return k

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

    Q = queue.Queue()
    for i in range(1, 10):
        Q.put(str(i))
    
    cnt = 1
    while cnt < K:
        q = Q.get()
        cnt += 1
        n = int(q[-1])
        if n != 0:
            Q.put(q + str(n-1))
        Q.put(q + str(n))
        if n != 9:
            Q.put(q + str(n+1))
    
    print(Q.get())
            


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def ith(N,i):
    # print(N, i, (N % (10 ** (i+1))) // 10 ** i)
    return (N % (10 ** (i+1))) // 10 ** i
def next(N):
    if N < 10:
        return N+1
    if ith(N,0) == 9:
        up = next(N//10)
        # print(up)
        if ith(up,0) == 0:
            return up * 10 + ith(up,0)
        else:
            return up * 10 + ith(up,0) - 1
    if ith(N,0) == ith(N,1) + 1:
        up = next(N//10)
        if ith(up,0) == 0:
            return up * 10 + ith(up,0)
        else:
            return up * 10 + ith(up,0) - 1
    return N + 1


def main():
    K = int(input())
    ans = 1
    for i in range(K-1):
        ans = next(ans)
    print(ans)
main()

Submission status: Accepted

Solution code:
input = raw_input

k = int(input())

suf_dict = {}
for d in range(10):
    if d == 0:
        suf_dict[str(d)] = ["0", "1"]
    elif d == 1:
        suf_dict[str(d)] = ["0", "1", "2"]
    elif d == 9:
        suf_dict[str(d)] = ["8", "9"]
    else:
        suf_dict[str(d)] = [str(d-1), str(d), str(d+1)]


def find(x):
    sufs = suf_dict[x[-1]]
    ret = [x+suf for suf in sufs]
    return ret

def main():
    xs = list("123456789")
    last_count = 9
    if k <= 9:
        out = k
        return out
    else:
        while True:
            next_xs = []
            for x in xs:
                first_count = last_count + 1
                elms = find(x)
                cur_num = len(elms)
                last_count = first_count + cur_num - 1
                #print(first_count, last_count, elms)
                if first_count <= k <= last_count:
                    out = elms[k-first_count]
                    return out
                next_xs += elms
            xs = next_xs

out = main()
print(out)

Submission status: Accepted

Solution code:
hoge=[1,2,3,4,5,6,7,8,9]
n=100001
new=[1,2,3,4,5,6,7,8,9]
while len(hoge)<n:
  huga=[]
  for i in range(len(new)):
    aaa=new[i]*10+new[i]%10
    huga.append(aaa)
    if(new[i]%10!=9):
      aaa=new[i]*10+new[i]%10+1
      if(1>=abs(int(str(aaa)[-1])-int(str(aaa)[-2]))):
        huga.append(aaa)
    if(new[i]%10!=0):
      aaa=new[i]*10+new[i]%10-1
      if(1>=abs(int(str(aaa)[-1])-int(str(aaa)[-2]))):
        huga.append(aaa)
  new=huga
  hoge=hoge+huga
hoge.sort()
print(hoge[int(input())-1])

Submission status: Accepted

Solution code:
K = int(input())
cnt = 9
li = [list(range(1,10))]
if(K<=cnt):
    print(li[0][K-1])
else:
    while(cnt<K):
        li.append([])
        for num in li[-2]:
            s_num = str(num)
            if(s_num[-1]=='0'):
                li[-1].append(num*10)
                li[-1].append(num*10+1)
                cnt += 2
            elif(s_num[-1]=='9'):
                li[-1].append(num*10+8)
                li[-1].append(num*10+9)
                cnt += 2
            else:
                last = int(s_num[-1])
                li[-1].append(num*10+last-1)
                li[-1].append(num*10+last)
                li[-1].append(num*10+last+1)
                cnt += 3
            if(cnt>=K):
                print(li[-1][-(cnt-K+1)])
                break

Submission status: Accepted

Solution code:
k = int(input())

lists = [1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 0
while len(lists) <= k:
    num = lists[i]
    lastnum = num % 10
    if lastnum == 0:
        lists.append(num * 10 + 0)
        lists.append(num * 10 + 1)
    elif lastnum == 9:
        lists.append(num * 10 + 8)
        lists.append(num * 10 + 9)
    else:
        lists.append(num * 10 + lastnum-1)
        lists.append(num * 10 + lastnum)
        lists.append(num * 10 + lastnum+1)
    i+=1
#print(lists)    
print(lists[k-1])

Submission status: Accepted

Solution code:
k = int(input())
l = []

def lunlun(i):
    b = i[-1:]
    if int(i) <= 3234566667:
        if int(b)-1 >= 0 and int(b)-1 <= 9:
            l.append(int(i)*10+int(b)-1)
            lunlun(str(int(i)*10+int(b)-1))
        l.append(int(i)*10+int(b))
        lunlun(str(int(i)*10+int(b)))
        if int(b)+1 >= 0 and int(b)+1 <= 9:
            l.append(int(i)*10+int(b)+1)
            lunlun(str(int(i)*10+int(b)+1))
    

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

l.sort()
#15print(l)
print(l[k-1])

Submission status: Accepted

Solution code:
K = int(input())
seq = list(map(str, range(1, 10)))
answer = seq[:]
while True:
    tmp = []
    for i in seq:
        if i[-1] == '0':
            tmp.append(i + '0')
            tmp.append(i + '1')
        elif i[-1] == '9':
            tmp.append(i + '8')
            tmp.append(i + '9')
        else:
            t = ord(i[-1])
            tmp.append(i + chr(t - 1))
            tmp.append(i + i[-1])
            tmp.append(i + chr(t + 1))
    seq = tmp[:]
    answer.extend(seq[:])
    if len(seq) > K:
        break

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

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    ans = set()

    def rec(S):
        if 3234566667 < int(S):
            return
        c = S[-1]
        d = int(c)
        for plus in range(d-1, d+2):
            if plus < 0:
                continue
            ans.add(int(S+str(plus)))
            rec(S+str(plus))

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

    ansc = ans.copy()
    for a in ansc:
        S = str(a)
        pre = ""
        for i, s in enumerate(S):
            if i == 0:
                pre = s
                continue
            if abs(int(pre) - int(s)) > 1:
                ans.discard(a)
                break
            pre = s
    answer = sorted(ans)
    print(answer[K-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K = int(input())
arr = list(range(1, 10))
i = 0
while len(arr) < K:
    num = arr[i]
    last = list(filter(lambda x: 0 <= x <= 9, [num%10-1, num%10, num%10+1]))
    arr.extend(num*10 + t for t in last)
    i += 1
# print(arr)
print(arr[K-1])

Submission status: Accepted

Solution code:
k=int(input())
ans=[1,2,3,4,5,6,7,8,9]
p=[1,2,3,4,5,6,7,8,9]
c=9
while c<k:
    t=[]
    for i in p:
        j=i%10
        if j==0:
            t.append(i*10)
            t.append(i*10+1)
            c+=2
        elif j==9:
            t.append(i*10+8)
            t.append(i*10+9)
            c+=2
        else:
            t.append(i*10+j-1)
            t.append(i*10+j)
            t.append(i*10+j+1)
            c+=3
    ans.extend(t)
    p=t[::]
print(ans[k-1])

Submission status: Accepted

Solution code:
lunlun=[]

def find_lunlun(n,curr):
    global lunlun
    if curr>n:
        return

    lunlun.append(curr)
    el= curr%10
    find_lunlun(n,curr * 10 + el)
    if el==9:
        find_lunlun(n,curr*10+el-1)
    elif el==0:
        find_lunlun(n,curr*10+el+1)
    else:
        find_lunlun(n,curr*10+el-1)
        find_lunlun(n,curr*10+el+1)

for i in range(1,10):
    find_lunlun(10**10,i)
lunlun.sort()

k=int(input())
print(lunlun[k-1])

Submission status: Accepted

Solution code:
k = int(input())

result = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
prev = result
while True:
    new_prev = []
    for i in range(len(prev)):
        a = int(prev[i][-1]) - 1
        b = int(prev[i][-1])
        c = int(prev[i][-1]) + 1

        if a >= 0:
            a2 = prev[i]+str(a)
            new_prev.append(a2)
            result.append(a2)
        b2 = prev[i]+str(b)
        new_prev.append(prev[i]+str(b))
        result.append(b2)
        if c <= 9:
            c2 = prev[i]+str(c)
            new_prev.append(c2)
            result.append(c2)
    if len(result) >= k:
        break
    prev = new_prev
print(result[k-1])

Submission status: Accepted

Solution code:
K = int(input())

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

K-=9

def append_ll(array, t, ll):
    global k
    
    array[t].append(ll)
    k += 1
    if k==K:
        print(ll)
        exit()

k = 0
N = 2
lunlun = [None, [None, [1],[2],[3],[4],[5],[6],[7],[8],[9]]]
# lunlun[s][t] := list of s digits lunlun numbers with first number t
while True:
    lunlun_N = [[] for _ in range(10)]

    p = 10**(N-1)
    append_ll(lunlun_N, 1, p)
    
    for d in range(1, N):
        for ll in lunlun[d][1]:
            append_ll(lunlun_N, 1, p+ll)

    for ll in lunlun[N-1][2]:
        append_ll(lunlun_N, 1, p+ll)
    
    for x in range(2, 10):
        for ll in lunlun[N-1][x-1]:
            append_ll(lunlun_N, x, x*p+ll)
            
        for ll in lunlun[N-1][x  ]:
            append_ll(lunlun_N, x, x*p+ll)

        if x==9: continue
        for ll in lunlun[N-1][x+1]:
            append_ll(lunlun_N, x, x*p+ll)

    N+=1
    lunlun.append(lunlun_N)

Submission status: Accepted

Solution code:
k=int(input())
num=[]

def d(n):
  num.append(n)
  if n > 3234570000:
    return
  a=n%10
  if a==0:
    l=[0,1]
  elif a==9:
    l=[8,9]
  else:
    l=[a-1,a,a+1]
  for i in l:
    s=int(str(n)+str(i))
    d(s)

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

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

Submission status: Accepted

Solution code:
import sys

k = int(input())

dp = [ [ [] for _ in range(10)]  for _ in range(10)]
num = 0

for i in range(0,10):
    for j in range(0,10):
        if i==0:
            candi = [""]
        else:
            candi = []
            if j>0: candi += dp[i-1][j-1]
            candi += dp[i-1][j]
            if j<9: candi += dp[i-1][j+1]
        for x in candi:
            x = str(j)+str(x)
            dp[i][j].append(x)
            if j>0:
                num += 1
                if num == k:
                    print(x)
                    sys.exit()

Submission status: Accepted

Solution code:
K = int(input())
if K <= 10:
    print(K)
    exit()

arr = [0] * K
for i in range(1, 10):
    arr[i - 1] = i

cur = 9
s = 0
while True:
    tmp = arr[s]
    num = tmp % 10
    
    if num > 0:
        arr[cur] = tmp * 10 + (num - 1)
        cur += 1
        if cur  == K:
            break
        
        
    arr[cur] = tmp * 10 + num
    cur += 1
    if cur == K:
        break

    if num < 9:
        arr[cur] = tmp * 10 + (num + 1)
        cur += 1
        if cur == K:
            break
    s += 1

print(arr[-1])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
k=int(sys.stdin.readline())
arr=[1,2,3,4,5,6,7,8,9]
n=len(arr)
if k<=n:
    print(arr[k-1])
    sys.exit()
k-=n
next=[]
i=0
while k>=0 and i<n:
    x=arr[i]%10
    a,b,c=x-1,x,x+1
    if a!=-1:
        next.append(arr[i]*10+a)
        k-=1
        if k==0:
            print(next[-1])
    next.append(arr[i]*10+b)
    k-=1
    if k==0:
        print(next[-1])
    if c!=10:
        next.append(arr[i]*10+c)
        k-=1
        if k==0:
            print(next[-1])
    i+=1
    if i==n:
        arr=[j for j in next]
        i=0
        n=len(arr)
        next=[]

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
 
input = stdin.readline
 
k = int(input())
q = deque(list(range(1, 10)))
res = deque(list(range(1, 10)))
cnt = 9

while True:
    t = q.popleft()
    r = t % 10
    
    if r == 0:
        q.append(t * 10)
        q.append(t * 10 + 1)
        res.append(t * 10)
        res.append(t * 10 + 1)
        cnt += 2
    elif r == 9:
        q.append(t * 10 + 8)
        q.append(t * 10 + 9)
        res.append(t * 10 + 8)
        res.append(t * 10 + 9)
        cnt += 2
    else:
        q.append(t * 10 + r - 1)
        q.append(t * 10 + r)
        q.append(t * 10 + r + 1)
        res.append(t * 10 + r - 1)
        res.append(t * 10 + r)
        res.append(t * 10 + r + 1)
        cnt += 3

    if cnt >= k:
        break

print(res[k - 1])

Submission status: Accepted

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

def add_v(v):
  global cands
  global K
  v = str(v)
  v0 = int(v[-1])
  if v0 == 0:
    cands += [int(v+'0'), int(v+'1')]
    K -=2
  elif v0 == 9:
    cands += [int(v+'8'), int(v+'9')]
    K -= 2
  else:
    cands += [int(v+str(v0-1)), int(v+str(v0)), int(v+str(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 sys import stdin,setrecursionlimit
k = int(stdin.readline().rstrip())
li = [i for i in range(1,10)]
#ルンルン最初の数
def runrun(before,kazu):
    if before == 0:
        li.append(int(kazu+str(before+1)))
        li.append(int(kazu+str(before)))
    elif before == 9:
        li.append(int(kazu+str(before-1)))
        li.append(int(kazu+str(before)))
    else:
        li.append(int(kazu+str(before+1)))
        li.append(int(kazu+str(before-1)))
        li.append(int(kazu+str(before)))
    if len(kazu)+1 >= 10:
        return
    else:
        if before == 0:
            return runrun(before+1,kazu+str(before+1)),runrun(before,kazu+str(before))
        elif before == 9:
            return runrun(before-1,kazu+str(before-1)),runrun(before,kazu+str(before))
        else:
            return runrun(before+1,kazu+str(before+1)),runrun(before-1,kazu+str(before-1)),runrun(before,kazu+str(before))
for i in range(1,10):
    runrun(i,str(i))
li.sort()
print(li[k-1])

Submission status: Accepted

Solution code:
import sys
from string import digits

k = int(sys.stdin.readline().rstrip())

def main():
    r = k
    if r <= 9:
        print(digits[r])
        return
    res = list(digits[1:])
    r -= 9
    d = set(digits)
    while True:
        nex = []
        for n in res:
            o = ord(n[-1])
            for i in range(-1, 2):
                tail = chr(o+i)
                if tail in d:
                    nex.append(n+tail)
                    r -= 1
                    if r == 0:
                        print(nex[-1])
                        return
        res = nex.copy()    

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [0,1,2,3,4,5,6,7,8,9]
count = 9
idx = 1
while count < n:
  pick = a[idx]
  if pick % 10 == 0:
    a.extend([pick*10+0, pick*10+1])
    count += 2
  elif pick % 10 == 9:
    a.extend([pick*10+8, pick*10+9])
    count += 2
  else:
    lsn = pick % 10
    a.extend([pick*10+lsn-1, pick*10+lsn, pick*10+lsn+1])
    count += 3
  idx += 1
print(a[n])

Submission status: Accepted

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

while len(a)<=100000:
    past=len(a)
    for i in range(now,len(a)):
        if a[i]%10==0:
            a.append(a[i]*10+0)
            a.append(a[i]*10+1)
        elif a[i]%10==9:
            a.append(a[i]*10+8)
            a.append(a[i]*10+9)
        else:
            a.append(a[i]*10+a[i]%10-1)
            a.append(a[i]*10+a[i]%10)
            a.append(a[i]*10+a[i]%10+1)
    now=past

print(a[k-1])

Submission status: Accepted

Solution code:
import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    K = int(input())
    
    q = queue.Queue()
    for i in range(1, 10):
        q.put(i)

    r = 9
    for k in range(K):
        a = q.get()
        l = max(0, a % 10 - 1)
        ll = min(10, a % 10 + 2)
        for b in range(l, ll):
            q.put(a * 10 + b)
            r += 1
    print(a)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

retsu = int(input())

def dfs( s , n ):
    i = 0
    if len(s) == n:
        ans.append(s)
        return
    else:
        a = int(s[len(s)-1])
        for j in range(3):
            if a+j-1 >= 0 and a+j-1 <= 9:
                dfs( s + str(a+j-1) , n )
                
ans = []
for i in range(1,11):
    for j in range(10):
        a = str(j)
        dfs( a , i )
        
ans2 = []
for i in ans:
    if i[0] != "0":
        ans2.append(int(i))
        
print(ans2[retsu-1])

Submission status: Accepted

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

def main():
    korg = int(input())
    ranran = {(1, 0): ["0"],
        (1, 1): ["1"],
        (1, 2): ["2"],
        (1, 3): ["3"],
        (1, 4): ["4"],
        (1, 5): ["5"],
        (1, 6): ["6"],
        (1, 7): ["7"],
        (1, 8): ["8"],
        (1, 9): ["9"],
        }  # Dict: (d, k) |-> list of strings
    for d in range(2, 11):
        for k in range(10):
            ranran[(d, k)] = []
            d2 = d - 1
            for k2 in [k - 1, k, k + 1]:
                if not 0 <= k2 <= 9:
                    continue
                for s in ranran[(d2, k2)]:
                    ranran[(d, k)].append(str(k) + s)
    ranran_f = []
    for key, v in ranran.items():
        ranran_f += v
    runrun = sorted(list({int(x) for x in ranran_f}))
    print(runrun[korg])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def func(n):
    s = str(n)
    L = len(s)
    for i in reversed(range(L-1)):
        x = int(s[i])
        y = int(s[i+1])
        if abs(x-y) > 1:
            buf = 10**(L-(i+1)-1)
            if x > y:
                return int(s[:i] + str(x) + str(x-1)) * buf
            else:
                return (int(s[:i+1]) + 1)*(buf*10)
    return -1

def main():
    k = int(input())
    target = 1
    while k > 0:
        buf = func(target)
        if buf == -1:
            k -= 1
            if k == 0:
                break
            target += 1
        else:
            target = buf
#        print(target)
    print(target)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K = int(input())

from collections import defaultdict

num = 0

dp = [[] for i in range(10)]

for i in range(1, 10):
    dp[0].append(i)

for k in range(9):
    for j in range(len(dp[k])):
        s = str(dp[k][j])
        n = int(s[-1])
        if 0 < n:
            dp[k + 1].append(int(s + str(n - 1)))
        dp[k + 1].append(int(s + str(n)))
        if n < 9:
            dp[k + 1].append(int(s + str(n + 1)))

for i in range(10):
    dp[i].sort()
    for j in range(len(dp[i])):
        num += 1
        if num == K:
            print(dp[i][j])

Submission status: Accepted

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

if K < 10:
  print(K)
  exit()

count = 0
lunlun = []

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

# BFS
while count < K:
  now = queue.popleft()
  diff = [-1,0,1]
  for i in range(3):
    tmp = now % 10 + diff[i]
    if 0<= tmp <= 9:
      queue.append(now*10 + tmp)
      lunlun.append(now*10 + tmp)
      count += 1

print(lunlun[K-10])

Submission status: Accepted

Solution code:
K = int(input())

runrun = []
def check(N):
    global runrun
    n = str(N)
    runrun.append(int(n))
    if len(n) == 10:
        return 0
    if n[-1] == "9":
        check(int(n+"8"))
        check(int(n+"9"))
        return
    elif n[-1] == "0":
        check(int(n+"0"))
        check(int(n+"1"))
        return
    else:
        c = int(n[-1]) - 2
        for i in range(3):
            c += 1
            cc = str(c)
            check(int(n+cc))
        return

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

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

Submission status: Accepted

Solution code:
k = int(input())

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

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

while len(todo) != 0:
    now = todo.pop()
    if now > 3234566668:
        # if now > 3234566668:
        continue
    if str(now)[-1] == '0':
        lunlun.append(int(str(now) + '0'))
        lunlun.append(int(str(now) + '1'))
        todo.append(int(str(now) + '0'))
        todo.append(int(str(now) + '1'))
    elif str(now)[-1] == '9':
        lunlun.append(int(str(now) + '8'))
        lunlun.append(int(str(now) + '9'))
        todo.append(int(str(now) + '8'))
        todo.append(int(str(now) + '9'))
    else:
        temp = int(str(now)[-1])
        lunlun.append(int(str(now) + str(temp - 1)))
        lunlun.append(int(str(now) + str(temp)))
        lunlun.append(int(str(now) + str(temp + 1)))
        todo.append(int(str(now) + str(temp - 1)))
        todo.append(int(str(now) + str(temp)))
        todo.append(int(str(now) + str(temp + 1)))

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

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    used = [1,2,3,4,5,6,7,8,9]
    ans = used
    k = 9
    now = 0
    add = [-1,0,1]
    while True:
        if k >= K :
            break
        else:
            keep = []
            for i in used:
                if (i % 10 == 0 ) :
                    keep.append(i * 10 + 0)
                    keep.append(i * 10 + 1)
                    continue
                if (i % 10 == 9):
                    keep.append(i * 10 + 8)
                    keep.append(i * 10 + 9)
                    continue
                p = (i % 10)
                for j in range(3):
                    keep.append(i * 10 + p + add[j])
            k += len(keep)
            ans += keep
            used = keep
    print(ans[K-1])

if __name__ == '__main__':
    main()