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:
from collections import deque

k = int(input())

tbl = []
queue = deque()

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

while queue:
    if len(tbl) >= k:
        break
    x = queue.popleft()
    tbl.append(x)
    if x % 10 == 0:
        queue.append(x * 10)
        queue.append(x * 10 + 1)
    elif x % 10 == 9:
        queue.append(x * 10 + 8)
        queue.append(x * 10 + 9)
    else:
        queue.append(x * 10 + x % 10 - 1)
        queue.append(x * 10 + x % 10)
        queue.append(x * 10 + x % 10 + 1)

print(tbl[k - 1])

Submission status: Accepted

Solution code:
import sys
k = int(input())

from collections import deque

cnt = 0


s = [[i] for i in range(1, 10)]
stack = deque(s)
while stack:
    cur = stack.popleft()
    cnt += 1
    if cnt == k:
        print(''.join(list(map(str, cur))))
        sys.exit()
    c = cur[-1]
    for i in (c-1, c, c+1):
        if i >= 0 and i <= 9:
            next = cur[:]
            next.append(i)
            stack.append(next)

Submission status: Accepted

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

d = deque(map(str, range(1, 10)))

counter = 1
while True:
    v = d.popleft()
    if (counter == k):
        print(v)
        break

    counter += 1

    first = v[-1]
    if first == "9":
        d.append(v + "8")
        d.append(v + "9") 
    elif first == "0":
        d.append(v + "0")
        d.append(v + "1") 
    else:
        for i in [-1, 0, 1]:
            d.append(v + str(int(first) + i))

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

def serch(dp,i,j,k,now):
    if i<0:
        return ""
    # print(i,j,k,now)
    # print(dp[i])
    for l in range(3):
        if j+l-1==-1:
            continue
        if now+dp[i][j+l-1]<k:
            now+=dp[i][j+l-1]
        else:
            return str(j+l-1)+serch(dp,i-1,j+l-1,k,now)

k=int(input())
dp=[[0]*10 for i in range(10)]
for i in range(10):
    dp[0][i]=1
# print(dp)

for i in range(1,10):
    for j in range(10):
        if j==0:
            dp[i][j]+=dp[i-1][j]
            dp[i][j+1]+=dp[i-1][j]
        elif j==9:
            dp[i][j-1]+=dp[i-1][j]
            dp[i][j]+=dp[i-1][j]
        else:
            dp[i][j-1]+=dp[i-1][j]
            dp[i][j]+=dp[i-1][j]
            dp[i][j+1]+=dp[i-1][j]
# for i in range(10):
#     dp[i][0]=0
# print(dp)

now=0
for i in range(10):
    for j in range(1,10):
        if now+dp[i][j]<k:
            now+=dp[i][j]
            continue
        else:
            # print(k,now,j)
            ans=str(j)
            ans+=serch(dp,i-1,j,k,now)
            print(ans)
            quit()

Submission status: Accepted

Solution code:
K = int(input())

flag=0
lis=[]
for i in range(0, 10):
  if i == 0:
    starti = 0
    endi = 10
  else:
    starti = max(i-1, 0)
    endi = min(i+2, 10)
  for j in range(starti, endi):
    if i == 0 and j == 0:
      startj = 0
      endj = 10
    else:
      startj = max(j-1, 0)
      endj = min(j+2, 10)
    for k in range(startj, endj):
      if i == 0 and j == 0 and k == 0:
        startk = 0
        endk = 10
      else:
        startk = max(k-1, 0)
        endk = min(k+2, 10)
      for l in range(startk, endk):
        if i == 0 and j == 0 and k==0 and l == 0:
          startl = 0
          endl = 10
        else:
          startl = max(l-1, 0)
          endl = min(l+2, 10)
        for m in range(startl, endl):
          if i == 0 and j == 0 and k==0 and l == 0 and m==0:
            startm = 0
            endm = 10
          else:
            startm = max(m-1, 0)
            endm = min(m+2, 10)
          for n in range(startm, endm):
            if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0:
              startn = 0
              endn = 10
            else:
              startn = max(n-1, 0)
              endn = min(n+2, 10)
            for o in range(startn, endn):
              if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0 and o==0:
                starto = 0
                endo = 10
              else:
                starto = max(o-1, 0)
                endo = min(o+2, 10)
              for p in range(starto, endo):
                if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0 and o==0 and p==0:
                  startp = 0
                  endp = 10
                else:
                  startp = max(p-1, 0)
                  endp = min(p+2, 10)
                for q in range(startp, endp):
                  if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0 and o==0 and p==0 and q==0:
                    startq = 0
                    endq = 10
                  else:
                    startq = max(q-1, 0)
                    endq = min(q+2, 10)
                  for r in range(startq, endq):
                    if i == 0 and j == 0 and k==0 and l == 0 and m==0 and n==0 and o==0 and p==0 and q==0 and r==0:
                      startr = 0
                      endr = 10
                    else:
                      startr = max(r-1, 0)
                      endr = min(r+2, 10)
                    lis.append(r+10*q+100*p+1000*o+10000*n+100000*m+1000000*l+10000000*k+100000000*j+1000000000*i)

print(sorted(set(lis))[K])

Submission status: Accepted

Solution code:
def main():
    k = int(input())
    d = dict()

    # 2 ** 20 = 10 ** 6
    order = 0
    find = False
    for n_digit in range(1, 20):
        # print('(n_digit, order):', n_digit, order)
        if n_digit == 1:
            for i in range(10):
                d[(n_digit, i)] = 1
            
        else:
            for i in range(10):
                d[(n_digit, i)] = d[(n_digit - 1, i)]
                if i >= 1:
                    d[(n_digit, i)] += d[(n_digit - 1, i - 1)]
                if i <= 8:
                    d[(n_digit, i)] += d[(n_digit - 1, i + 1)]

        for i in range(1, 10):
            if order + d[(n_digit, i)] < k:
                order += d[(n_digit, i)]
            else:
                find = True
            
            if find:
                break

        if find:
            break

    # n_digit, start with i
    ans = list()
    ans.append(i)

    for digit in range(n_digit - 1, 0, -1):
        for j in range(i - 1, i + 2):
            if 0 <= j <= 9:
                if order + d[(digit, j)] < k:
                    order += d[(digit, j)]
                else:
                    ans.append(j)
                    i = j
                    break

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


main()

Submission status: Accepted

Solution code:
k = int(input())

xs = list(range(1, 10))
x_cnt = 0

while x_cnt + len(xs) < k:
    x_cnt += len(xs)
    next_xs = []
    for x in xs:
        ones_place = x % 10
        mul_10 = x * 10
        if ones_place != 0:
            next_xs.append(mul_10 + ones_place - 1)
        next_xs.append(mul_10 + ones_place)
        if ones_place != 9:
            next_xs.append(mul_10 + ones_place + 1)
    xs = next_xs

print(xs[k - x_cnt - 1])

Submission status: Accepted

Solution code:
N = int(input())
digits = 1
dp = []
dp.append([i for i in range(1,10)])
K = 9

if(N<=9):
    print(dp[0][N-1])
    exit(0)
else:
    N -= 9

while(N>0):
    tmp = []
    for n in dp[digits-1]:
        base = int(str(n)[-1])
        for i in [-1,0,1]:
            if(base+i >= 0 and base+i<10):
                tmp.append(int(str(n)+str(base+i)))
    digits += 1
    K = len(tmp)
    N -= K
    dp.append(tmp)

print(dp[digits-1][N-1])

Submission status: Accepted

Solution code:
K = int(input())

def nextInts(n):
    if n == 0:
        return (0, 1)
    elif n == 9:
        return (8, 9)
    else:
        return (n-1, n, n+1)

class C:
    cnt = 0
    
    def f(self, t, d, a, s, K): # t: 前の桁の値, d: 残り桁数(この桁を含む), a: 今の値
        if self.cnt == K:
            return
        if d == 0:
            #print(a)
            self.cnt += 1
            if self.cnt == K:
                print(a)
                
            return
        
        l = range(1, 10) if s else nextInts(t)
        for x in l:
            self.f(x, d-1, a * 10 + x, False, K)


c = C()
q = 1
while c.cnt != K:
    c.f(0, q, 0, True, K)
    q += 1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(1000000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def is_lunlun(n):
    s = str(n)
    for i in range(len(s)-1):
        if abs(int(s[i])-int(s[i+1])) > 1:
            return False
    return True

def slv(k):
    n = 1
    for _ in range(k-1):
        j = 0
        while True:
            l = 10**j
            t = 0
            t += n + l
            t -= (n+l) % l
            m = (t % (10**(j+1))) // l
            # print(t, j, m)
            for i in range(j-1, -1, -1):
                t += (10 ** i) * max(0, m-(j-i))
            # print(t, j)
            if is_lunlun(t):
                n = t
                break
            else:
                j+=1
            # if j > 5:
            #     break
        # print(n)
    return n



def main():
    K = read_int()
    print(slv(K))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

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

def f(p,x,m):
    a = [-1,0,1]
    for k in a:
        y = x+k
        if y >= 0 and y < 10:
            q = p+y*(10**m)
            if m == 0:
                aa.append(q)
            else:
                f(q,y,m-1)

for i in range(1,10):
    for j in range(1,10):
        f(j*(10**i),j,i-1)

n = ni()
print(aa[n-1])

Submission status: Accepted

Solution code:
import sys
K = int(input())
anss = [[i for i in range(1,10)]]
count = 9
if K <= 9:
  print(K)
  sys.exit()
for i in range(1,15):
  ans = []
  # これは昇順に並んでいるはず
  origin = anss[i-1]
  for o in origin:
    s = str(o)
    for j in range(10):
      if abs(int(s[-1]) - j) <= 1:
        a = int(s+str(j))
        count += 1
        if count == K:
          print(a)
          sys.exit()
        ans.append(a)
  anss.append(ans)

Submission status: Accepted

Solution code:
k = int(input())
nums = [i for i in range(1,10)]
tmp = [i for i in range(1,10)]
if k <= 10:
    print(tmp[k-1])
    exit()
for _ in range(10**2):
    tmpp = []
    for num in tmp:
        for i in range(-1,2):
            if 10 > num%10+i >= 0 and (num*10 + (num%10+i))!= nums[-1] and abs(num%10 - (num%10+i)) <= 1:
                nums.append(num*10+(num%10+i))
                tmpp.append(num*10+(num%10+i))
                if len(nums) == k+1:
                    print(nums[k-1])
                    exit()
    tmp = tmpp

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
limit = 10

start = [i for i in range(1, 10)]
q = deque(start)
ans = []

while q:
    cur = q.popleft()
    if len(str(cur)) > 11:
        continue
    ans.append(cur)
    r = str(cur)[-1]
    if r == '0':
        add = ['0', '1']
    elif r == '9':
        add = ['8', '9']
    else:
        add = [str(int(r) - 1), str(int(r)), str(int(r) + 1)]

    for i in add:
        q.append(int(str(cur) + i))

ans = sorted(ans)
print(ans[k - 1])

Submission status: Accepted

Solution code:
k = int(input())
if k <= 9:
    print(k)
else:
    a = [[1,2,3,4,5,6,7,8,9]]
    cnt = 0
    anscnt = 9
    flag = 0
    while flag == 0:
        b = []
        for i in a[cnt]:
            stri = str(i)
            if stri[-1] == "0":
                now = int(stri + "0")
                b.append(now)
                anscnt += 1
                if anscnt == k:
                    print(now)
                    flag = 1
                now = int(stri + "1")
                b.append(now)
                anscnt += 1
                if anscnt == k:
                    print(now)
                    flag = 1
            elif stri[-1] == "9":
                now = int(stri + "8")
                b.append(now)
                anscnt += 1
                if anscnt == k:
                    print(now)
                    flag = 1
                now = int(stri + "9")
                b.append(now)
                anscnt += 1
                if anscnt == k:
                    print(now)
                    flag = 1
            else:
                s = int(stri[-1])-1
                now = int(stri + str(s))
                b.append(now)
                anscnt += 1
                if anscnt == k:
                    print(now)
                    flag = 1
                s += 1
                now = int(stri + str(s))
                b.append(now)
                anscnt += 1
                if anscnt == k:
                    print(now)
                    flag = 1
                s += 1
                now = int(stri + str(s))
                b.append(now)
                anscnt += 1
                if anscnt == k:
                    print(now)
                    flag = 1
            a.append(b)
            cnt += 1

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools,bisect
from fractions import gcd
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10**18
MOD = 10**9 + 7
DD = ((1,0),(0,1),(-1,0),(0,-1))

k = NI()
a = [1,2,3,4,5,6,7,8,9]
cnt = 0
j = 0
while True:
    x = a[j]
    j += 1
    s = x % 10
    for i in range(s-1,s+2):
        if i >= 0 and i < 10:
            a.append(x * 10 + i)
            cnt += 1
    if cnt > 100000: break
print (a[k-1])

Submission status: Accepted

Solution code:
K = int(input())

def is_lunlun(i):
    result = -1
    n = [ord(c) -48 for c in str(i)]
    for j in range(len(n) - 1):
        if abs(n[j] - n[j + 1]) <= 1:
            continue
        if n[j] < n[j + 1]:
            for k in range(j + 1, len(n)):
                n[k] = 0
            result = int(''.join(str(k) for k in n))
            result += 10 ** (len(n) - (j + 1))
        else:
            result = int(''.join(str(k) for k in n))
            result += 10 ** (len(n) - (j + 2))
        break
    return result

i = 1
while True:
    #print(i)
    t = is_lunlun(i)
    if t == -1:
        K -= 1
        if K == 0:
            print(i)
            exit()
        i += 1
    else:
        i = t

Submission status: Accepted

Solution code:
from collections import deque

K=int(input())
# BFS
M=1
L=9
tmp=deque([1,2,3,4,5,6,7,8,9])
k=1
while L<K:
    k=str(tmp.popleft())
    if int(k[-1])-1>=0:
        tmp.append(int(k+str(int(k[-1])-1)))
        L+=1
    tmp.append(int(k+k[-1]))
    L+=1
    if int(k[-1])+1<10:
        tmp.append(int(k+str(int(k[-1])+1)))
        L+=1
    M+=1

print(tmp[K-M])

Submission status: Accepted

Solution code:
k=int(input())
cur=1
ans=-1
cnt=0
while cnt<k:
    num=str(cur)
    n=len(num)
    flag=True
    pos=-1
  #  print(num,end=' num\n')
    for i in range(n-1):
        if abs(int(num[i])-int(num[i+1]))>1:
            pos=i+1
            flag=False
            break
 #   print(flag)
    if flag==True:
        ans=cur
        cur+=1
        cnt+=1
    else:
        if int(num[pos])!=9:
            ch=str(int(num[pos])+1)
#            print(ch)
            cur=int(num[:pos]+ch+num[pos+1:])
        else:
            ch=str(int(num[pos-1])+1)
            cur=int(num[:pos-1]+ch+'0'*len(num[pos:]))
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import math
K = int(input())
Ln = [[]]
Ln[0] = [1 for i in range(10)]
for i in range(1,10):
    tmp =[Ln[i-1][0] + Ln[i-1][1]] + [Ln[i-1][j-1] + Ln[i-1][j] + Ln[i-1][j+1] for j in range(1,9)] +[Ln[i-1][8] + Ln[i-1][9] ]
    Ln.append(tmp)


X = K
Y = 0
fin =(-1,-1)
flag = 1
for i in range(10):
    for j in range(1,10):
        Y = X
        X -= Ln[i][j]

        if X<=0 : 
            fin = (i,j)
            flag = 0
            break
        
    if flag == 0:
        break

ans = 10**i * j 

p=i

for i in range(p-1,-1,-1):
    X = Y
    flag = 1

    if j==0 :
        lis = [0,1]
    elif j==9:
        lis = [8,9]
    else:
        lis = [j-1,j,j+1]
    for j in lis:
        Y = X
        X -= Ln[i][j]

        if X<=0:
            ans += 10**i * j

            flag = 0
        if flag == 0:
            break
print(ans)

Submission status: Accepted

Solution code:
k = int(input())

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

val = ['' for i in range(10)]

kouho = []
#val = 0
#num = 0

def dfs(pos,keta,num):
    if keta == pos:
        #num += 1
        val[pos] = num
        #print(val)  
        tmp = 0
        for i in range(keta+1):
            #if val[keta-1-i] != '':
            tmp += val[i] * 10 ** (keta-i)
            #print(val[i],keta-i)
        #print(val)
        kouho.append(tmp)
        """
        if num == k:
            print(tmp)
            exit()
            #return tmp
        """
        #val = 0
        return
    
    for i in range(3):
        #print(i,kouho,num)
        val[pos] = num
        #print(val)
        if num-1+i > 9:
            continue
        if num-1+i < 0:
            continue
        dfs(pos+1,keta,num-1+i)
    
for i in range(10):
    for j in range(1,10):
        #print(i,j,j,j,j)
        dfs(0,i,j)
#print(kouho)
#exit()
print(kouho[k-1])

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools
import heapq
#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)


def main():
    k=int(input())
    keta1=[x for x in range(1,10)]
    oriketa=copy.deepcopy(keta1)
    def next(keta,newketa):
        for i in range(len(keta)):
            plus=keta[i]%10+1
            eq=keta[i]%10
            minus=keta[i]%10-1
            if plus<=9:
                newketa.append(keta[i]*10+plus)
            newketa.append(keta[i]*10+eq)
            if minus>=0:
                newketa.append(keta[i]*10+minus)
        return
    ketan=[[] for i in range(10)]
    next(keta1,ketan[0])
    ketan[0]=sorted(ketan[0])
    oriketa.extend(ketan[0])
    for i in range(9):
        next(ketan[i],ketan[i+1])
        ketan[i+1] = sorted(ketan[i+1])
        oriketa.extend(ketan[i+1])

    #print(oriketa)
    print(oriketa[k-1])



if __name__ == "__main__":

    main()

Submission status: Accepted

Solution code:
def calc(K):
    l = [i for i in range(1, 10)]
    n = 9
    while True:
        if n >= K:
            return l[K - 1]
        K -= n
        newl = []
        n = 0
        for x in l:
            d = x % 10
            newl += [x * 10 + y for y in [d - 1, d, d + 1] if y > -1 and y < 10]
            n += (2 if (d == 0 or d == 9) else 3)
            if n >= K:
                return newl[K - 1]
        l = newl


K = int(input())
print(calc(K))

Submission status: Accepted

Solution code:
from collections import deque

from heapq import heappush, heappop


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

    q = []

    for i in range(1, 10):
        heappush(q, i)

    while True:
        v = heappop(q)
        K -= 1
        if K == 0:
            print(v)
            exit()
        u = v % 10
        nv = v * 10 + u

        heappush(q, nv)
        if u == 0:
            heappush(q, nv + 1)
        elif u == 9:
            heappush(q, nv - 1)
        else:
            heappush(q, nv - 1)
            heappush(q, nv + 1)


main()

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
k=int(input())
cur=0
for i in range(k):
  s=str(cur)
  n=len(s)
  if n<=1 or cur==10**n-1:
    cur+=1
  elif int(s[n-2])>=int(s[n-1]) and int(s[n-1])!=9:
    cur+=1
  elif int(s[n-2])>=int(s[n-1]) and int(s[n-1])==9:
    for j in range(n-1):
      if int(s[n-j-1])==9 or int(s[n-j-1])==int(s[n-j-2])+1:
        continue
      else:
        nn=j
        ret=s[:n-1-nn]
        ret+=str(int(s[n-1-nn])+1)
        break
    else:
      ret=str(int(s[0])+1)
      nn=n-1
    
    for j in range(nn):
      ret+=str(max(int(ret[-1])-1,0))
    cur=int(ret)
  else: 
    for j in range(1,n-1):
      if int(s[n-1-j-1])>=int(s[n-1-j]):
        nn=n-1-j
        ret=s[:nn]
        ret+=str(int(s[nn])+1)
        break
    else:
      nn=0
      ret=str(int(s[0])+1)
    for j in range(n-nn-1):
      ret+=str(max(int(ret[-1])-1,0))
    cur=int(ret)
print(cur)

Submission status: Accepted

Solution code:
lunlunnum = []
def lunlun(n):
    if n >= 10000000000:
        return
    lunlunnum.append(n)
    d = n%10
    if d == 0:
        next_d = [0, 1]
    elif d == 9:
        next_d = [8, 9]
    else:
        next_d = [d-1, d, d+1]
    for i in next_d:
        lunlun(n*10 + i)
for i in range(1, 10):
    lunlun(i)
lunlunnum.sort()
k = int(input())
print(lunlunnum[k-1])

Submission status: Accepted

Solution code:
K = int(input())

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

while True:
	if K < len(num_table[-1]):
#		for nums in num_table:
#			for n in nums:
#				print(n)
		print(num_table[-1][K - 1])
		break
	K -= len(num_table[-1])
	

	d = 1
	d2 = 10 ** len(num_table)
	new_num_table = set((d2,))
	for i in range(0, len(num_table) - 1):
		for num in num_table[i]:
			if num // d == 1:
				new_num_table.add(d2 + num)
		d *= 10
	
	for num in num_table[-1]:
		top = num // d
		if top > 1:
			new_num_table.add((top - 1) * d2 + num)
		if top > 0:
			new_num_table.add(top * d2 + num)
		if top < 9:
			new_num_table.add((top + 1) * d2 + num)
	
	new_num_table = list(new_num_table)
	new_num_table.sort()
	
	num_table.append(new_num_table)

Submission status: Accepted

Solution code:
#def lunlun(n):
#    D = []
#    while n:
#        D.append(n%10)
#        n //= 10
#    return all(abs(D[i-1]-D[i])<=1 for i in range(1,len(D)))

def lunlun_gen(which):
    R = []

    D = [1]
    while len(R) < which:
        num = 0
        for d in D:
            num = 10*num + d
        R.append(num)

        for i in reversed(range(1, len(D))):
            if D[i] + 1 <= 9 and abs(D[i] + 1 - D[i-1]) <= 1:
                D[i] += 1
                break
        else:
            # last digit
            i = 0
            if D[0] == 9:
                D.append(0)
                D[0] = 1
            else:
                D[0] += 1

                
        for j in range(i+1, len(D)):
            D[j] = max(0, D[j-1] - 1)
    return R[which-1]

k = int(input())
print(lunlun_gen(k))

Submission status: Accepted

Solution code:
K=int(input())
if K<10:
    n=2
    i=1
else:
    n=10
    i=9
while i<K:
    S=str(n)
    cond=True
    for j in range(len(S)-1):
        if abs(int(S[j])-int(S[j+1]))>1:
            cond=False
            break
    if cond:
        i+=1
#        print(n)
        n+=1
    else:
        n+=10**(len(S)-j-2)
#        print(n,10**(len(S)-j-2))
print(n-1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100010)
k = int(input())


def islunlun(l):
    for x in range(1,len(l)):
        if abs(ord(l[x])-ord(l[x-1])) > 1:
            return False
    return True

s = set()
mx = 3234566667
def generate(l):
    val = None
    if l == []:
        val = 0
    else:
        val = int("".join(list(map(str,l))))
    #print(l, val)
    if mx < val:
        return
    else:
        if l != []:
            s.add(val)
    if len(l) == 0:
        for x in range(1,10):
            l.append(x)
            generate(l.copy())
            l.pop(len(l)-1)
    else:
        #print(max(0, l[len(l) - 1] - 1), min(9,l[len(l)-1]+1)+1)
        for x in range(max(0,l[len(l)-1]-1), min(9,l[len(l)-1]+1)+1):
            l.append(x)
            generate(l)
            l.pop(len(l)-1)

"""def bt(l):
    for x in range(10):
        l.append()"""

generate([])
l = []
for x in s:
    l.append(x)
l.sort()
print(l[k-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
if K < 10:
    print(K)
else:
    K -= 9
    q = deque(list(range(1, 10)))
    while K:
        num = q.popleft()
        last_digit = str(num)[-1]
        if last_digit == '0':
            q.append(int(str(num) + '0')); K -= 1
            if K == 0: break
            q.append(int(str(num) + '1')); K -= 1
        elif last_digit == '9':
            q.append(int(str(num) + '8')); K -= 1
            if K == 0: break
            q.append(int(str(num) + '9')); K -= 1
        else:
            q.append(int(str(num) + str(int(last_digit) - 1))); K -= 1
            if K == 0: break
            q.append(int(str(num) + str(int(last_digit)))); K -= 1
            if K == 0: break
            q.append(int(str(num) + str(int(last_digit) + 1))); K -= 1
    print(q[-1])

Submission status: Accepted

Solution code:
K = int(input())

def runrun_build(K):
    runrun_list = list(range(1, 10))
    base_list = runrun_list.copy()
    cnt = 9
    for i in range(0, 9):
        new_base_list = []
        for val in base_list:
            val_list = []
            if val % 10 == 0:
                for j in range(0, 2):
                    val_list.append(val * 10 + val % 10 + j)
                    cnt += 1
            elif val % 10 == 9:
                for j in range(-1, 1):
                    val_list.append(val * 10 + val % 10 + j)
                    cnt += 1
            else:
                for j in range(-1, 2):
                    val_list.append(val * 10 + val % 10 + j)
                    cnt += 1
            new_base_list.extend(val_list)
            if cnt > K:
                runrun_list.extend(new_base_list)
                return runrun_list
        runrun_list.extend(new_base_list)
        base_list = new_base_list
    return runrun_list

print(sorted(runrun_build(K))[K-1])

Submission status: Accepted

Solution code:
from collections import deque


def lunlun(k: int):
    q = deque([str(i) for i in range(1, 10)])
    res = '1'

    while k > 0:
        res = q.popleft()
        left = int(res[-1]) - 1
        mid = int(res[-1])
        right = int(res[-1]) + 1

        if left >= 0:
            q.append("{}{}".format(res, str(left)))
        q.append("{}{}".format(res, str(mid)))
        if right <= 9:
            q.append("{}{}".format(res, str(right)))

        k -= 1

    return int(res)


if __name__ == '__main__':
    k = int(input())
    print(lunlun(k))

Submission status: Accepted

Solution code:
import sys
# import resource

sys.setrecursionlimit(10 ** 9)
# resource.setrlimit(resource.RLIMIT_STACK, ((2 ** 7) * 1000 * 1000, -1))

k = int(input())

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

def ans(j, nums):
    nums[j] += 1
    pre = nums[j]
    for i in range(j + 1, len(nums)):
        if pre > 0:
            nums[i] = pre - 1
            pre = nums[i]
        else:
            nums[i] = pre
    return int(''.join(map(str, nums)))

def lunlun(n):
    if n <= 9:
        return ary[n - 1]
    l = lunlun(n - 1)
    nums = list(map(int, list(str(l))))
    first = len(nums) - 1
    last = 0
    for i in range(len(nums)):
        j = len(nums) - i - 1
        c = nums[j] + 1
        # 桁数が変わらないとき
        if j == first:
            # 1桁目
            if nums[j] < 9 and abs(nums[j - 1] - c) <= 1:
                nums[j] += 1
                return int(''.join(map(str, nums)))
        elif j == last:
            # 最終桁
            if nums[j] < 9 and abs(nums[j + 1] - c) <= 1:
                return ans(j, nums)
        elif j != first and j != last:
            # 間の桁
            if nums[j] < 9 and abs(nums[j - 1] - c) <= 1 and abs(nums[j + 1] - c) <= 1:
                return ans(j, nums)

    # 桁が繰り上がるとき
    return int('1' + ''.join(['0'] * len(nums)))

print(lunlun(k))