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())
t = {}
cnt = 0

for ie in range(10):
    ne = ie
    for id in range(10):
        nd = ne*10+id
        if abs(ie-id)>1 and ne!=0:
            continue
        for ic in range(10):
            nc = nd*10+ic
            if abs(id-ic)>1 and nd!=0:
                continue
            for ib in range(10):
                nb = nc*10+ib
                if abs(ic-ib)>1 and nc!=0:
                    continue
                for ia in range(10):
                    na = nb*10+ia
                    if abs(ib-ia)>1 and nb!=0:
                        continue
                    for i1 in range(10):
                        n1 = na*10+i1
                        if abs(ia-i1)>1 and na!=0:
                            continue
                        for i2 in range(10):
                            n2 = n1*10+i2
                            if abs(i1-i2)>1 and n1!=0:
                                continue
                            for i3 in range(10):
                                n3 = n2*10+i3
                                if abs(i2-i3)>1 and n2!=0:
                                    continue
                                for i4 in range(10):
                                    n4 = n3*10+i4
                                    if abs(i3-i4)>1 and n3!=0:
                                        continue
                                    for i5 in range(10):
                                        n5 = n4*10+i5
                                        if abs(i4-i5)>1 and n4!=0:
                                            # print("conti", n5)
                                            continue
                                        if n5 ==0:
                                            # print("z")
                                            continue
                                        cnt += 1
                                        # print(n5, cnt)
                                        if cnt==K:
                                            print(n5)
                                            exit()
                                        # t[i5*10000 + i4*1000 + i3*100 + i2*10 + i1]
                            # print(n)
            # print(cnt)

            # t.append(10**5)
            # print(t[K])
# print(cnt)

Submission status: Accepted

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

if K < 10:
    print(K)
    exit()
cnt = 9
number_list = [str(i) for i in range(1, 10)]

while True:
    new_number_list = []
    for number in number_list:
        if number[-1] == '0':
            new_number_list.append(number + '0')
            new_number_list.append(number + '1')
        elif number[-1] == '1':
            new_number_list.append(number + '0')
            new_number_list.append(number + '1')
            new_number_list.append(number + '2')
        elif number[-1] == '2':
            new_number_list.append(number + '1')
            new_number_list.append(number + '2')
            new_number_list.append(number + '3')
        elif number[-1] == '3':
            new_number_list.append(number + '2')
            new_number_list.append(number + '3')
            new_number_list.append(number + '4')
        elif number[-1] == '4':
            new_number_list.append(number + '3')
            new_number_list.append(number + '4')
            new_number_list.append(number + '5')
        elif number[-1] == '5':
            new_number_list.append(number + '4')
            new_number_list.append(number + '5')
            new_number_list.append(number + '6')
        elif number[-1] == '6':
            new_number_list.append(number + '5')
            new_number_list.append(number + '6')
            new_number_list.append(number + '7')
        elif number[-1] == '7':
            new_number_list.append(number + '6')
            new_number_list.append(number + '7')
            new_number_list.append(number + '8')
        elif number[-1] == '8':
            new_number_list.append(number + '7')
            new_number_list.append(number + '8')
            new_number_list.append(number + '9')
        elif number[-1] == '9':
            new_number_list.append(number + '8')
            new_number_list.append(number + '9')
    cnt += len(new_number_list)
    if cnt >= K:
        print(new_number_list[-(cnt-K+1)])
        exit()
    number_list = new_number_list

Submission status: Accepted

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

def dfs(now, d, L):
    if d==L:
        return 1
    
    res = 0
    
    for nex in range(max(0, now-1), min(9, now+1)+1):
        res += dfs(nex, d+1, L)
    
    return res

K = int(input())

for i in range(1, 100):
    r = 0
    
    for j in range(1, 10):
        r += dfs(j, 1, i)
    
    if K-r>0:
        K -= r
    else:
        k = i
        break

def dfs2(l, d, k):
    global K
    
    if d==k:
        K -= 1

        if K==0:
            l = list(map(str, l))
            print(''.join(l))
            exit()
        
        return
    
    now = l[-1]
    
    for nex in range(max(0, now-1), min(9, now+1)+1):
        l.append(nex)
        dfs2(l, d+1, k)
        l.pop()

for i in range(1, 10):
    dfs2(deque([i]), 1, k)

Submission status: Accepted

Solution code:
def gen_lunlun(digit, li):
    if len(li) == digit:
        lunluns.append(''.join(map(str, li)))
        return
    min_num = max(0, li[-1] - 1)
    max_num = min(9, li[-1] + 1)
    for i in range(min_num, max_num + 1):
        gen_lunlun(digit, li + [i])


k = int(input())

lunluns = []
for d in range(1, 11):
    for i in range(1, 10):
        gen_lunlun(d, [i])
print(lunluns[k - 1])

Submission status: Accepted

Solution code:
import sys
k = int(input())
klist=list(map(str, [1,2,3,4,5,6,7,8,9]))
dic = {'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']}
if k <= 9:
    print(klist[k-1])
    sys.exit()
else:
    count = 0
    ok = 9
    while 1:
        tmp = klist[count]
        for add in dic[tmp[-1]]:
            klist.append(''.join([tmp, add]))
            ok+=1
            if ok == k:
                print(''.join([tmp, add]))
                sys.exit()
        count+=1

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
import sys
k = int(input())

if k <= 9:
  print(k)
  sys.exit()

matsubi_dic = dd(lambda: [])
for i in range(0, 10):
  nums = [i-1, i, i+1]
  matsubi_dic[i] = [num for num in nums if num >= 0 and num <= 9]
#print(matsubi_dic) 
  
#ketaごとに保存 runrun[keta] -> list
runrun = dd(list)
counter = 0
for keta in range(1, 100000000000):
  if keta == 1:
    runrun[keta] = list(range(1, 10))
    counter += 9
    #print(runrun, counter)
  else:
    for num in runrun[keta - 1]:
      matsubi = int(str(num)[keta-2])
      for new_matsubi in matsubi_dic[matsubi]:
        runrun[keta].append(int(str(num) + str(new_matsubi)))
        counter += 1
        if counter == k:
          print(int(str(num) + str(new_matsubi)))
          sys.exit()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
a = int(input())
from collections import deque
stack_deque = deque([])


if a <= 9:
    print(a)
    from sys import exit
    exit()
else:
    base = [1,2,3,4,5,6,7,8,9]
    cnt = 9
    while cnt<a:
        nb = deque([])
        for i in base:
            first_v = i%10
            v = i*10
            if first_v==0:
                nb.append(v)
                cnt+=1
                if cnt==a:
                    break
                else:
                    nb.append(v+1)
                    cnt+=1
            elif first_v==9:
                nb.append(v+8)
                cnt+=1
                if cnt==a:
                    break
                else:
                    nb.append(v+9)
                    cnt+=1
            else:
                for j in [first_v-1,first_v,first_v+1]:
                    nb.append(v+j)
                    cnt+=1
                    if cnt==a:
                        break
                if cnt==a:
                    break
        base = nb
print(nb[-1])

Submission status: Accepted

Solution code:
from collections import deque
l = [i for i in range(1,10)]
deque = deque(l)
cnt = 9

def lunlun(i):
    s =str(i)
    s_last=int(s[-1])
    if s_last == 0:
        s1 = s + str(s_last)
        s2 = s + str(s_last + 1)
        return int(s1),int(s2)
    elif s_last == 9:
        s0 = s + str(s_last - 1)
        s1 = s + str(s_last)
        return int(s0),int(s1)
    else:
        s0 = s + str(s_last - 1)
        s1 = s + str(s_last)
        s2 = s + str(s_last + 1)
        return int(s0),int(s1),int(s2)

while cnt <= 10**5:
    num = deque.popleft()
    t = list(lunlun(num))
    cnt += len(t)
    l.extend(t)
    deque.extend(t)

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**5)

run=deque()

def rec(n,cnt):
    if cnt>10:return
    run.append(int(n))
    if n[-1]!="0":
        rec(n+str(int(n[-1])-1),cnt+1)
    if n[-1]!="9":
        rec(n+str(int(n[-1])+1),cnt+1)
    rec(n+n[-1],cnt+1)
k=int(input())
for i in range(1,10):
    rec(str(i),1)
a=sorted(run)
print(a[k-1])

Submission status: Accepted

Solution code:
from collections import deque

def get_lunlun(i):
    ret = [i]
    if i  > 0:
        ret.append(i-1)
    if i < 9:
        ret.append(i+1)
    return sorted(ret)

def main():
    n = int(input())
    cand = deque()
    adj = {i: get_lunlun(i) for i in range(0,10)}
    for i in range(1, 10):
        cand.append(i)
    for _ in range(n):
        pos = cand.popleft()
        for cnd in adj[pos%10]:
            cand.append(pos*10+cnd)
    print(pos)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k = int(input())
dp = [[0] * 10 for _ in range(11)]
for i in range(10):
    dp[0][i] = 1
for i in range(1,11):
    dp[i][0] = dp[i-1][0] + dp[i-1][1]
    dp[i][9] = dp[i-1][8] + dp[i-1][9]
    for j in range(1,9):
        dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j+1]

#print(dp)

ans = ""
cumsum = 0
brflag = False
for i in range(11):
    for j in range(1,10):
        cumsum += dp[i][j]
        if cumsum >= k:
            ans += str(j)
            k -= cumsum - dp[i][j]
            brflag = True
            break
    if brflag == True:
        brflag = False
        break
        
while i > 0:
    #print(i,j,k)
    i -= 1
    cumsum = 0
    psfl = False
    if j > 0:
        cumsum += dp[i][j-1]
        if cumsum >= k:
            ans += str(j-1)
            k -= cumsum - dp[i][j-1]
            j = j - 1
            #print("pass1")
            psfl = True
    if not psfl:
        cumsum += dp[i][j]
        if cumsum >= k:
            ans += str(j)
            k -= cumsum - dp[i][j]
            psfl = True
            #print("pass2")
    if (not psfl) and j < 9:
        cumsum += dp[i][j+1]
        if cumsum >= k:
            ans += str(j+1)
            k -= cumsum - dp[i][j+1]
            j = j + 1
            psfl = True    
            #print("pass3")
print(ans)

Submission status: Accepted

Solution code:
K = int(input())
s = '0'
cnt = 0
while cnt<K:
  cnt += 1
  ns = ''
  j = -1
  for i in range(len(s)-1,0,-1):
    if int(s[i])+1<=int(s[i-1])+1 and int(s[i])+1<10:
      j = i
      break
  else:
    if s[0]<'9':
      j = 0
  if j!=-1:
    m = int(s[j])
    for i in range(len(s)):
      if i==j:
        x = str(int(s[i])+1)
      elif i<j:
        x = s[i]
      elif i==j+1:
        x = str(m)
      else:
        x = str(max(m-1,0))
        m = max(m-1,0)
      ns += x
  else:
    ns = '1'+'0'*len(s)
  s = ns
#  print(s,)
print(s)

Submission status: Accepted

Solution code:
k=int(input())


if k<10:
    print(k)

else:
    q=[str(i+1) for i in range(9)]
    ans=9
    for i in range(20):
        nq = []
        for j in range(len(q)):
            if q[j][-1]=='0'or q[j][-1]== '9':
                if q[j][-1]=='0':
                    nq.append(q[j]+'0')
                    nq.append(q[j]+'1')
                else:
                    nq.append(q[j]+'8')
                    nq.append(q[j]+'9')

                ans+=2
                if ans>=k:
                    print(nq[-(ans-k+1)])
                    exit()
            else:
                nq.append(q[j] +str(int(q[j][-1])-1))
                nq.append(q[j] +str(int(q[j][-1])))
                nq.append(q[j]+ str(int(q[j][-1])+ 1))
                ans+=3
                if ans>=k:
                    print(nq[-(ans-k+1)])
                    exit()
        q=nq

Submission status: Accepted

Solution code:
K = int(input())

S = list(range(1, 10))
A = S[:]

cnt = 0
while len(A) < K:
    T = []
    for s in S:
        q, r = divmod(s, 10)
        if r != 0:
            T.append(s * 10 + r - 1)
        T.append(s * 10 + r)
        if r != 9:
            T.append(s * 10 + r + 1)
    S = T
    A += T

print(A[K - 1])

Submission status: Accepted

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

def neighbor(a):
    if a == 0:
        return [0,1]
    if a == 9:
        return [8,9]
    return [a-1,a,a+1]

def make_lunlun(digit, start):
    if digit == 1:
        return [start]
    res = []
    for start_neighbor in neighbor(start):
        b = make_lunlun(digit-1, start_neighbor)
        c = list(map(lambda x:x+(start*(10**(digit-1))), b))
        res.extend(c)
    return res
lunlun = []
for i in range(1,11):
    for j in range(1,10):
        lunlun.extend(make_lunlun(i, j))

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

Submission status: Accepted

Solution code:

import sys

#sys.setrecursionlimit(500000)

K = int(input())

ans = []

def make(prev,scale,now):
    if scale == 0:
        ans.append("".join(now))
        return
    if prev > 0:
        n = list(now)
        n.append(str(prev-1))
        make(prev-1,scale-1,n)
    n = list(now)
    n.append(str(prev))
    make(prev,scale-1,n)
    if prev < 9:
        n = list(now)
        n.append(str(prev+1))
        make(prev+1,scale-1,n)
    
for i in range(10):
    for j in range(1,10):
        make(j,i,[str(j)])

print(ans[K-1])

Submission status: Accepted

Solution code:
k=int(input())
if k<=9:
    print(k)
    exit()
a=[1,2,3,4,5,6,7,8,9]
cnt=9
while True:
    q=[]
    for i in a:
       for j in range(10):
            if abs(int(str(i)[-1])-j)<=1:
                cnt+=1
                if cnt==k:
                    print(int(str(i)+str(j)))
                    exit()
                q.append(int(str(i)+str(j)))         
    a=list(sorted(set(q)))

Submission status: Accepted

Solution code:
k = int(input())

ans = []
def add(t,d,v):
  if d == 0:
    ans.append(v)
  else:
    if t != 0:
      add(t-1, d-1, v+str(t-1))    
    add(t, d-1, v+str(t))
    if t != 9:
      add(t+1, d-1, v+str(t+1))
  
for d in range(10):
  for t in range(1,10):
    add(t,d,str(t))
  if len(set(ans)) > k:
    break

ans = [int(a) for a in ans]
ans = sorted(list(set(ans)))
print(ans[k-1])

Submission status: Accepted

Solution code:
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % mod) % mod
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    K = iRaw()
    if K <= 10:
        return K
    runrun = [1,0]
    leftK = K-10
    while leftK >0:
        leftK-=1
        lenRun = len(runrun)
        digit = lenRun -1
        while digit>0:
            if runrun[digit] <runrun[digit-1]:
                runrun[digit]+=1
                break
            if runrun[digit] == runrun[digit-1] and runrun[digit]!=9:
                runrun[digit]+=1
                break
            digit -=1
        
        if digit==0:
            if runrun[0] < 9:
                runrun[0]+=1
            else:
                runrun = [1]+([0]*lenRun)
                continue
        for idx in range(digit+1,lenRun):
            runrun[idx] = max(runrun[idx-1]-1,0)

    return "".join([str(r) for r in runrun])
    
if __name__ == "__main__":
    print(main())

Submission status: Accepted

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

def solve(K: int):
    first = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    heapq.heapify(first)
    res = 1
    while K > 0:
        res = heapq.heappop(first)
        if res % 10 != 0:
            heapq.heappush(first, res * 10 + res % 10 - 1)
        heapq.heappush(first, res * 10 + res % 10)
        if res % 10 != 9:
            heapq.heappush(first, res * 10 + res % 10 + 1)
        K -= 1
    return res


def main():
    K = int(input().rstrip())
    res = solve(K)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

K = int(input())

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

ll = [1,2,3,4,5,6,7,8,9]
aft_l = []
cnt = 9
while cnt < K:
    for l in ll:
        tmp = 10 * l
        last = l%10
        if last >= 1:
            aft_l.append(tmp+last-1)
            cnt += 1
            if cnt == K:
                print(aft_l[-1])
                exit()
        
        aft_l.append(tmp+last)
        cnt += 1
        if cnt == K:
            print(aft_l[-1])
            exit()
        if last <= 8:
            aft_l.append(tmp+last+1)
            cnt +=1
            if cnt == K:
                print(aft_l[-1])
                exit()
    ll = aft_l
    aft_l = []

Submission status: Accepted

Solution code:
k = int(input())
count = 9
from collections import deque
que = deque([1,2,3,4,5,6,7,8,9])
if k<10:
    print(k)
    exit()
while que:
    v = que.popleft()
    matu = v%10
    for i in range(10):
        if abs(matu-i)<=1:
            que.append(v*10+i)
            count +=1
            if count == k:
                print(que.pop())
                exit()

Submission status: Accepted

Solution code:
K = int(input())
lun = list(range(1, 10))
for n in range(K):
    lm = lun[n] % 10
    if lm > 0:
        lun.append(lun[n] * 10 + (lm - 1))
    lun.append(lun[n] * 10 + lm)
    if lm < 9:
        lun.append(lun[n] * 10 + (lm + 1))
print(lun[K-1])

Submission status: Accepted

Solution code:
K = int(input())
h = [0]*10
h[0] = {1,2,3,4,5,6,7,8,9}

def digit_lunlun(x):
    if x == 0:
        return h[0]
    G = digit_lunlun(x-1)
    a = set()
    for g in G:
        b = g%10
        for i in set([max(0,b-1),b,min(b+1,9)]):
            a.add(g*10+i)
    h[x] = a
    return a

digit_lunlun(9)
for i in range(10):
    le = len(h[i])
    if le < K:
        K -= le
    else:
        for g in sorted(h[i]):
            if K == 1:
                print(g)
                exit()
            else:
                K -= 1

Submission status: Accepted

Solution code:
def d1(x):
    y = x % 10
    if y == 0:
        return [0, 1]
    elif y == 9:
        return [8, 9]
    else:
        return [y-1, y, y+1]


K = int(input())

runrun = []
N = 0
digit = 0
while N < K:
    d_i = []
    if digit == 0:
        for i in range(1, 10):
            d_i.append(i)
        N += len(d_i)
        runrun.append(d_i)
        digit += 1
    else:
        tmp = runrun[digit-1]
        for x in tmp:
            for y in d1(x):
                d_i.append(10*x+y)
        N += len(d_i)
        runrun.append(d_i)
        digit += 1

print(runrun[-1][K-N-1])

Submission status: Accepted

Solution code:
# 最後に桁によって次の値の候補が定まる
# 2kから末尾が出ることに注意
# k(桁) 1k=9 2k=26 3k=75 

K = int(input())
count = 9
runrunnumber  = [[]for _ in range(10)]


runrunnumber[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
#print(runrunnumber)

if K > 10:
  for i in range(9):
    for j in runrunnumber[i]:

      if j%10 == 0:
        for p in range(2):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break
      
      if j%10 == 1:
        for p in range(3):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 2:
        for p in range(1,4):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 3:
        for p in range(2,5):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 4:
        for p in range(3,6):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break
      if j%10 == 5:
        for p in range(4,7):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 6:
        for p in range(5,8):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 7:
        for p in range(6,9):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 8:
        for p in range(7,10):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 9:
        for p in range(8,10):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

        if count >= K:
          break
    if count >= K:
      break

else:
  print(runrunnumber[0][K-1])

Submission status: Accepted

Solution code:

from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]


def main():
	k=nextIntList()[0]
	if k<=9:
		print(k)
		sys.exit(0)
	num=[0,1]
	for i in range(10, k):
# 		print(num)
		if all([n==9 for n in num]):
			num=[0 for d in range(len(num))]
			num.append(1)
			continue
		
		for di in range(len(num)):
			if di==0:
				if num[di]<=num[di+1] and num[di]<9:
					num[di]+=1
					break
			elif di<len(num)-1:
				if num[di]<=num[di+1] and num[di]<9 and num[di]<=num[di-1]:
					num[di]+=1
					break
			else: #di==len(num)-1
				num[di]+=1
	
		for dii in range(di-1, -1,-1):
			if num[dii+1]==0:
				num[dii]=0
			else:
				num[dii]=num[dii+1]-1 
	
	print("".join(str(n) for n in reversed(num)))

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

k = n_in()

h = {
    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],
}


from collections import deque

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

i = 0
current = '0'

while True:
    current = q.popleft()
    i += 1
    for j in h[int(current[-1])]:
        q.append(current + str(j))

    if i == k:
        break

print(current)

Submission status: Accepted

Solution code:
def gen(l):
    _runs = []
    for r in l:
        r = str(r)
        if r[-1] == '0':
            _runs.append(r+'1')
            _runs.append(r+'0')
        elif r[-1] == '9':
            _runs.append(r+'9')
            _runs.append(r+'8')
        else:
            _runs.append(r+str(int(r[-1])+1))
            _runs.append(r+str(int(r[-1])-1))
            _runs.append(r+r[-1])
    return _runs

def runrun(n):
    runs = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    _runs = gen(runs)
    while len(runs) < n:
        runs.extend(_runs)
        _runs = gen(_runs)
    return sorted(map(lambda i: int(i),runs))

k = int(input())

print(runrun(k)[k-1])

Submission status: Accepted

Solution code:
#BFSやなたぶん BFSって再帰呼び出しいるのかい？いやいらんだろう？

K = int(input())
runrun_num = 0

def bfs(s_list):
    global K,runrun_num
    new_s_list = []
    for s in s_list:
        new_int_min = int(s[-1])-1
        if s[-1]=='0':
            new_int_min = 0
        new_int_max = int(s[-1])+1
        if s[-1]=='9':
            new_int_max = 9
        for i in range(new_int_min,new_int_max+1):
            new_s = s+str(i)
            runrun_num+=1
            if K == runrun_num+9:
                print(new_s)
                return None
            else:
                new_s_list.append(new_s)
    bfs(new_s_list)

inp = [str(i) for i in range(1,10)]
if 1<=K and K<=9:
    print(K)
else:
    bfs(inp)

Submission status: Accepted

Solution code:
K=int(input())

l=["1","2","3","4","5","6","7","8","9"]
la=["1","2","3","4","5","6","7","8","9"]
c=9

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

while c<K:
    lb=[]
    for i in la:
        if i[-1]=="0":
            l.append(i+"0")
            l.append(i+"1")
            lb.append(i+"0")
            lb.append(i+"1")
            c+=2
        elif i[-1]=="9":
            l.append(i+"8")
            l.append(i+"9")
            lb.append(i+"8")
            lb.append(i+"9")
            c+=2
        else:
            j=int(i[-1])
            l.append(i+str(j-1))
            l.append(i+str(j))
            l.append(i+str(j+1))
            lb.append(i+str(j-1))
            lb.append(i+str(j))
            lb.append(i+str(j+1))
            c+=3
    la=lb

print(l[K-1])

Submission status: Accepted

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



def ln():
    q = deque()
    m = 1
    nd = 1

    while True:
        for i in range(9):
            q.append(([i+1], 1))

            while q:
                n, d = q.popleft()
                if d == nd:
                    if m == K:
                        return n
                    m += 1
                    continue

                if n[-1] == 0:
                    q.append((n+[0], d+1))
                    q.append((n+[1], d+1))
                elif n[-1] == 9:
                    q.append((n+[8], d+1))
                    q.append((n+[9], d+1))
                else:
                    q.append((n+[n[-1]-1], d+1))
                    q.append((n+[n[-1]], d+1))
                    q.append((n+[n[-1]+1], d+1))

        nd+=1

print(''.join(map(str, ln())))

Submission status: Accepted

Solution code:
def rec(N):
    tmp = str(N)
    if tmp[-1] == "0":
        tmp__ = int(tmp[-1])
        tmp___ = int(tmp[-1]) + 1
        yield tmp + str(tmp__)
        yield tmp + str(tmp___)
    elif tmp[-1] == "9":
        tmp_ = int(tmp[-1]) - 1
        tmp__ = int(tmp[-1])
        yield tmp + str(tmp_)
        yield tmp + str(tmp__)
    else:
        tmp_ = int(tmp[-1]) - 1
        tmp__ = int(tmp[-1])
        tmp___ = int(tmp[-1]) + 1
        yield tmp + str(tmp_)
        yield tmp + str(tmp__)
        yield tmp + str(tmp___)
        
K = int(input())
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 0
while(True):
    if len(A) > K:
        break
    for i in rec(A[count]):
        A.append(i)
    count += 1
print(A[K - 1])

Submission status: Accepted

Solution code:
k = int(input())
if k < 10:
    print(k)
else:
    d = [[str(i)] for i in range(10)]
    n = 9
    while True:
        dd = [None for _ in range(10)]
        dd[0] = ['0' + j for j in d[0]] + ['0' + j for j in d[1]]
        for i in range(1, 9):
            si = str(i)
            dd[i] = [si + j for j in d[i - 1]] + [si + j for j in d[i]] + [si + j for j in d[i + 1]]
            n += len(dd[i])
            if n >= k:
                break
        else:
            i += 1
            dd[9] = ['9' + j for j in d[8]] + ['9' + j for j in d[9]]
            n += len(dd[i])
        if n >= k:
            print(dd[i][k - n - 1])
            break
        d = dd

Submission status: Accepted

Solution code:
K = int(input())
a = []
dp = [[[] for i in range(10)] for j in range(100)]
for i in range(10):
  dp[0][i] = [i]
  if i != 0:
    a.append(i)
for i in range(1, 10):
  for j in range(10):
    if j != 0:
      for k in dp[i-1][j-1]:
        dp[i][j].append(k + 10 ** i * j)
        a.append(k + 10 ** i * j)
    for k in dp[i-1][j]:
      dp[i][j].append(k + 10 ** i * j)
      if j != 0:
        a.append(k + 10 ** i * j)
    if j != 9:
      for k in dp[i-1][j+1]:
        dp[i][j].append(k + 10 ** i * j)
        if j != 0:
          a.append(k + 10 ** i * j)
print(a[K-1])

Submission status: Accepted

Solution code:
K = int(input())
dic = {i+1:[] for i in range(11)}

dic[1] = [str(i+1) for i in range(9)]

if K < 10:
    print(dic[1][K-1])
else:
    cnt = 9
    ans = -1
    for i, nums in dic.items():
        for n in nums:
            ds = n[-1]
            dd = int(ds)
            if dd > 0:
                dic[i+1].append(n + str(int(ds)-1))
                cnt += 1
            if cnt == K: break
            dic[i+1].append(n + str(int(ds)))
            cnt += 1
            if cnt == K: break
            if dd < 9:
                dic[i+1].append(n + str(int(ds)+1))
                cnt += 1
            if cnt == K: break
        if cnt == K:
            ans = dic[i+1][-1]
            break
    # from pprint import pprint
    # pprint(dic)
    print(ans)