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
limit = 3234566667
K = int(input())
ans = []

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)
q.append(5)
q.append(6)
q.append(7)
q.append(8)
q.append(9)

# 10倍して足す
ans = []
while len(q):
    num = q.popleft()
    ans.append(num)
    last_num = str(num)[-1]
    if last_num == "9":
        next_num = num * 10 + 8
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
        next_num = num * 10 + 9
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
    elif last_num == "0":
        next_num = num * 10
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
        next_num = num * 10 + 1
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
    else:
        next_num = num * 10 + int(last_num)
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
        next_num = num * 10 + int(last_num) + 1
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
        next_num = num * 10 + int(last_num) - 1
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
ans = list(set(ans))
ans.sort()
print(ans[K-1])

Submission status: Accepted

Solution code:
k = int(input())
val = [0]
for _ in range(k):
    if len(val) == 1:
        if val[0] != 9:
            val[0] += 1
        else:
            val.insert(0, 1)
            val[-1] = 0
    else:
        accept = False
        for i in range(1, len(val)):
            if val[-1*(i+1)] >= val[-1*i] and val[-1*i] != 9:
                val[-1*i] += 1
                for r in range(1,i):
                    val[-1*(i-r)] = max(0, val[-1*(i-r+1)]-1)
                accept = True
                break
        if not accept:
            if val[0] != 9:
                val[0] += 1
                for i in range(1, len(val)):
                    val[i] = max(val[i-1] - 1, 0)
            else:
                val.insert(0,1)
                for i in range(1, len(val)):
                    val[i] = 0

op = ""
for v in val:
    op += str(v)
print(op)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

K = int(input())

l = []
cnt = 0
q = deque()

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

while len(q) > 0:
    (n, prev) = q.popleft()
    l.append(int(n))
    cnt += 1
    if cnt > 100000:
        break
    if prev == 0:
        q.append((n + "0", 0))
        q.append((n + "1", 1))
    elif 1 <= prev <= 8:
        q.append((n + str(prev - 1), prev-1))
        q.append((n + str(prev), prev))
        q.append((n + str(prev + 1), prev+1))
    else:
        q.append((n + "8", 8))
        q.append((n + "9", 9))

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

Submission status: Accepted

Solution code:
from sys import exit
from collections import deque

K = int(input())
l = 0


def f(l):
    global D, K
    if l == 0:
        K -= 1
        if K == 0:
            print(''.join(map(str, D)))
            exit()
        D.pop()
        return
    d = D[-1]
    for i in (d - 1, d, d + 1):
        if i < 0 or i > 9:
            continue
        D.append(i)
        f(l - 1)
    D.pop()


while True:
    for i in range(1, 10):
        D = deque([i])
        f(l)
    l += 1

Submission status: Accepted

Solution code:
from itertools import product
K = int(input())
ans = []

for l in range(10):
    for s in range(1, 10):
        for pattern in product([0, 1, 2], repeat=l):  # そのまま, １つ上, １つ下
            X = [s]
            for p in pattern:
                if X[-1] == 0 and p == 2:
                    break
                if X[-1] == 9 and p == 1:
                    break

                if p == 0:
                    X.append(X[-1])

                if p == 1:
                    X.append(X[-1] + 1)

                if p == 2:
                    X.append(X[-1] - 1)
            else:
                ans.append(int(''.join(map(str, X))))

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

Submission status: Accepted

Solution code:
K = int(input())
kouho = []


def rec(d, n):
    if d == 12:
        return
    kouho.append(n)

    r = n % 10
    if r == 0:
        rec(d + 1, n * 10 + r)
        rec(d + 1, n * 10 + r + 1)
    elif r == 9:
        rec(d + 1, n * 10 + r)
        rec(d + 1, n * 10 + r - 1)
    else:
        rec(d + 1, n * 10 + r)
        rec(d + 1, n * 10 + r - 1)
        rec(d + 1, n * 10 + r + 1)



# def rec(s):
#     if len(s) == 12:
#         return
#     kouho.append(int(s[::-1]))
#     n = int(s[::-1])
#     if 1 <= n <= 8:
#         rec(s + str(n - 1))
#         rec(s + str(n))
#         rec(s + str(n + 1))
#     if n == 0:
#         rec(s + str(n))
#         rec(s + str(n + 1))
#     if n == 9:
#         rec(s + str(n - 1))
#         rec(s + str(n))

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

kouho.sort()
# print(kouho[:50])
print(kouho[K - 1])

Submission status: Accepted

Solution code:
K = int(input()) - 1
nums = [str(i) for i in range(1,10)]
while True:
    # print(nums)
    if K < len(nums):
        print(nums[K])
        break
    else:
        K -= len(nums)

    que = []
    for n in nums:
        if n[-1] > "0":
            que.append(n + str(int(n[-1]) - 1))
        if n[-1] < "9":
            que.append(n + str(int(n[-1]) + 1))
        que.append(n + n[-1])
    que.sort()
    nums = que

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#k = [int(i) for i in read().split()]
X = int(input())


def check(mid): # mid 以下のルンルン数は x 個以上？
    s = str(mid)
    L = len(s)    
    dp = [[0]*10 for _ in range(2)] # is_less, 上位桁
    for num,i in enumerate(s):
        ni = int(i)
        ndp = [[0]*10 for _ in range(2)] # is_less, 上位桁
        for is_less in range(2):
            for d in range(10 if is_less else ni+1):
                if d: ndp[is_less or d < ni][d] += dp[is_less][d-1]            
                ndp[is_less or d < ni][d] += dp[is_less][d]            
                if d<9: ndp[is_less or d < ni][d] += dp[is_less][d+1]            
        for j in range(1,10):
            if num == 0:
                if j==ni: ndp[0][j] += 1
                elif j<=ni: ndp[1][j] += 1
            else: ndp[1][j] += 1 
        dp = ndp
        #print(dp,num)
    return sum(dp[1])+sum(dp[0]) >= X

ng = 0
ok = 3234566668
while ok-ng > 1:
    mid = (ok+ng)//2
    if check(mid): ok = mid
    else: ng = mid

print(ok)

Submission status: Accepted

Solution code:
K=int(input())+1

def dfs(n,f,l,s):
  global K
  if l==0:
    K-=1
    if K==0:
      print(n)
      exit()
  elif s==1:
    for i in range(0,10):
      if i==0:
        dfs(10*n+i,i,l-1,1)
      else:
        dfs(10*n+i,i,l-1,0)
  else:
    if f==0:
      for i in range(0,2):
        dfs(10*n+i,i,l-1,0)
    elif f==9:
      for i in range(8,10):
        dfs(10*n+i,i,l-1,0)
    else:
      for i in range(f-1,f+2):
        dfs(10*n+i,i,l-1,0)
      
dfs(0,0,10,1)

Submission status: Accepted

Solution code:
def runrun(K,S):
    if K <= len(S):
        S.sort()
        ##print(S)
        print(S[K-1])
        return 
    else:
        for i in range(len(S)):
            tmp = S[i]%10
            if tmp == 9:
                S.append(S[i]*10+8)
                S.append(S[i]*10+9)
            elif tmp == 0:
                S.append(S[i]*10+1)
                S.append(S[i]*10)
            else:
                S.append(S[i]*10+tmp-1)
                S.append(S[i]*10+tmp)
                S.append(S[i]*10+tmp+1)
        S = list(set(S))
        runrun(K,S)

if __name__ == "__main__":
    K = int(input())
    S = []
    for i in range(1,10):
        S.append(i)
    runrun(K,S)

Submission status: Accepted

Solution code:
def Lun(ume,gen,start):
    global keta
    if(ume==keta):
        global ans
        temp=0
        for i in range(ume):
            temp+=gen[i]*(10**(keta-i-1))
        ans.append(temp)
        #print(gen)
        return
    ima=gen[ume-1]
    send=gen[:]
    if(start):
        if(ima>0):
            send[ume]=ima-1
            Lun(ume+1,send,start)
        send[ume]=ima
        Lun(ume+1,send,start)
        if(ima<9):
            send[ume]=ima+1
            Lun(ume+1,send,start)
    else:
        Lun(ume+1,send,False)
        for i in range(1,10):
            send[ume]=i
            Lun(ume+1,send,True)




ans=[]
keta=10
hajime=[0]*keta
Lun(1,hajime,False)
for i in range(1,4):
    hajime[0]=i
    Lun(1,hajime,True)

print(ans[int(input())])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def dfs(n,s,ans):
    if n == 10:
        return
    
    for i in range(10):

        tmp = s + str(i)
        if check(tmp):
            ans.append(int(tmp))
            dfs(n+1,tmp,ans)


def check(s):
    if abs(int(s[-1])-int(s[-2])) > 1:
        return False
    return True 

def main():
    K = int(input())
    ans = [1,2,3,4,5,6,7,8,9]
    for i in range(1,10):
        dfs(1,str(i),ans)
    ans.sort()
    print(ans[K-1])

    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
k = int(input())
ans = []

def rec(s, dig):
    if dig >= 10:
        ans.append(int("".join(map(str, s))))
        return
    
    if sum(s) == 0:
        for i in range(10):
            rec(s + [i], dig+1)
        return

    p = s[-1]
    if p != 0: rec(s + [p-1], dig+1)
    rec(s + [p], dig+1)
    if p != 9: rec(s + [p+1], dig+1)

rec([0], 0)
print(ans[k])

Submission status: Accepted

Solution code:
k = int(input())

dp = [[0]*10 for _ in range(10)]
d = [-1,0,1]
for i in range(10):
    for j in range(10):
        if i == 0:
            dp[i][j] = 1
        else:
            for dj in d:
                pj = j + dj
                if 0<=pj<10:
                    dp[i][j] += dp[i-1][pj]
cnt = 0
for n in range(10):
    s = sum(dp[n][1:])
    if cnt + s < k:
        cnt += s
    else:
        break
ans = ''
for j in range(1,10):
    if cnt + dp[n][j] < k:
        cnt += dp[n][j]
    else:
        ans += str(j)
        break

for i in range(n)[::-1]:
    for dj in d:
        nj = j + dj
        if 0<=nj<10:
            if cnt + dp[i][nj] < k:
                cnt += dp[i][nj]
            else:
                j = nj
                ans += str(nj)
                break
print(ans)

Submission status: Accepted

Solution code:
k = int(input())
num = 1
anss=[i for i in range(1,10)]
ans=[i for i in range(0,10)]
j=1
while(len(anss)<100001):
  j*=10
  ans_=[]
  for i in ans:
    i_=i//(j//10)
    if i_==9:
      ans_.append(i_*j+i)
      ans_.append((i_-1)*j+i)
    elif i_==0:
      ans_.append(i_*j+i)      
      ans_.append((i_+1)*j+i)
    else:
      ans_.append(i_*j+i)
      ans_.append((i_+1)*j+i)
      ans_.append((i_-1)*j+i)
  anss.extend(ans_)
  anss=list(set(anss))
  ans=[x for x in ans_]
anss.sort()
print(anss[k])

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
if k < 10:
  print(k)
else:
  queue = deque([[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7],[8,8],[9,9]])
  n = 9
  while n!=k:
    num,last_n = queue.popleft()
    if last_n-1 > -1:
      new_n = num*10+(last_n-1)
      queue.append([new_n,last_n-1])
      n += 1
    if n >= k:
      ans,_ = queue[-1]
      print(ans)
      break
    new_n = num*10+(last_n)
    queue.append([new_n,last_n])
    n += 1
    if n >= k:
      ans,_ = queue[-1]
      print(ans)
      break
    if last_n+1 < 10:
      new_n = num*10+(last_n+1)
      queue.append([new_n,last_n+1])
      n += 1
    if n >= k:
      ans, _ = queue[-1]
      print(ans)
      break

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import os
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
#############################################
All=[]

@lru_cache(maxsize=None)
def f(s):
    if(s!=""):All.append(int(s))
    if(len(s)>=10):return
    if len(s)==0:
        for a in range(1,10):
            f(s+str(a))
    else:
        for a in range(0,10):
            ch=ord("0")+a
            if abs(ord(s[-1])-ch)<=1:
                f(s+str(a))
K=int(input())
f("")
All.sort()
print(All[K-1])

Submission status: Accepted

Solution code:
K = int(input())

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

def a(b):
    if b > 3234566667:
        return
    sb = str(b)
    h = int(sb[-1])
    for i in range(0, 10):
        if abs(i-h) <= 1:
            k = int(str(b) + str(i))
            L.append(k)
            a(k)

for i in range(1, 10):
    a(i)
L = sorted(L)

print(L[K-1])

Submission status: Accepted

Solution code:
k = int(input())

ls = []

def dfs(n):
    if len(n) >= 12:
        return
    ls.append(int(n))
    lastNum = int(n[-1])
    for i in range(max(0, lastNum-1), min(lastNum + 2, 10)):
        dfs(n + str(i))

dfs("1")
dfs("2")
dfs("3")
dfs("4")
dfs("5")
dfs("6")
dfs("7")
dfs("8")
dfs("9")

ls = list(ls)
ls = sorted(ls)
print(ls[k-1])

Submission status: Accepted

Solution code:
#
import sys
import math
import numpy as np
import itertools


# ひとつ入力
k = int(input())

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

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

for i in range(20):
    k -= len(a)
    b = []
    for j in a:
        r = j % 10 
        if r == 0:
            b.append(j*10)
            b.append(j*10+1)
        elif r == 9:
            b.append(j*10+8)
            b.append(j*10+9)
        else:
            b.append(j*10+r-1)
            b.append(j*10+r)
            b.append(j*10+r+1)
#    print(b,len(b),k)
    if k <= len(b):
        print(b[k-1])
        exit()
    a = b

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)
k = int(input())

def dfs(l, lim):
    if lim == 10:
        return l
    new_l = []
    for num in l:
        last = num % 10
        base = num * 10
        if 1 <= last <= 8:
            for i in [last-1, last, last+1]:
                if base + i <= 3234566667:
                    new_l.append(base + i)
        elif last == 0:
            for i in [0, 1]:
                if base + i <= 3234566667:
                    new_l.append(base + i)
        else:
            for i in [8, 9]:
                if base + i <= 3234566667:
                    new_l.append(base + i)
    return l + new_l + dfs(new_l, lim+1)

ans = list(set(dfs([1, 2, 3, 4, 5, 6, 7, 8, 9], 0)))
ans.sort()

print(ans[k-1])

Submission status: Accepted

Solution code:
def main():

    K = int(input())
    cur = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    if K <= len(cur):
        return cur[K-1]
    K -= 9
    # add = cur
    while True:
        temp = []
        for v in cur:
            if v % 10 == 0:
                temp.append(v*10 + v % 10)
                temp.append(v*10 + 1)
            elif v % 10 == 9:
                temp.append(v*10 + 8)
                temp.append(v*10 + v % 10)
            else:
                temp.append(v * 10 + v % 10 - 1)
                temp.append(v * 10 + v % 10)
                temp.append(v * 10 + v % 10 + 1)
        # add += temp
        if len(temp) >= K:
            # break
            return temp[K-1]
        cur = temp
        K -= len(temp)
    return -1

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-

def input_multiple_number():
    return map(int, input().split())

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


K = int(input())

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

for i in range(100000):
	for j in range(3):
		if ans[i]%10 == 0 and j ==0:
			continue
		elif ans[i]%10 == 9 and j ==2:
			continue
		ans.append(ans[i]*10+j-1+ans[i]%10)

print(ans[K-1])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
k=int(input())
l=[[1,2,3,4,5,6,7,8,9]]
c=9
i=1
l0=[0]
while c<k:
    temp=[]
    for j in l0:
        temp.append(1*10*i+j)
    for j in l[-1]:
        t=j//i
        if t==1:
            temp.append(1 * 10 *i + j)
            temp.append(2*10*i+j)
            l0.append(j)
        elif t==9:
            temp.append(8*10*i+j)
            temp.append(9 * 10 *i + j)
        else:
            temp.append((t+1) * 10 *i+ j)
            temp.append(t * 10 *i + j)
            temp.append((t-1) * 10 *i + j)
    i=i*10
    c+=len(temp)
    l.append(temp)
all=[]
for i in l:
    for j in i:
        all.append(j)
all.sort()
print(all[k-1])

Submission status: Accepted

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

a = [i for i in range(1, 10)]
heapq.heapify(a)
ans = 0
while ans < k:
    r = heapq.heappop(a)
    ans += 1
    if ans == k:
        print(r)
        break
    for i in [-1, 0, 1]:
        if r % 10 + i < 0 or 9 < r % 10 + i:
            pass
        else:
            heapq.heappush(a, int("{}{}".format(r, r % 10 + i)))

Submission status: Accepted

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

def extend_lunlun(prev):
  prev_digit = int(str(prev)[-1])
  if prev_digit == 0:
    add_list = [0, 1]
  elif prev_digit == 9:
    add_list = [8, 9]
  else:
    add_list = [prev_digit-1, prev_digit, prev_digit+1]
  return [int('{}{}'.format(prev, ad)) for ad in add_list]
  

lunlun_numbers = list(range(1,10))
i_pos = 0
while True:
  lunlun_numbers += extend_lunlun(lunlun_numbers[i_pos])
  if len(lunlun_numbers) >= K:
    print(lunlun_numbers[K-1])
    break
  i_pos += 1

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
lst = []
cnt = 0
Q = deque()
for i in range(1,10):
    Q.append(str(i))
while cnt < k:
    s = Q.popleft()
    x = int(s[-1])
    lst.append(int(s))
    cnt += 1
    if x != 0:
        Q.append(s+str(x-1))
    Q.append(s+str(x))
    if x != 9:
        Q.append(s+str(x+1))

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

Submission status: Accepted

Solution code:
P = int(input())
A = []
for i in range(1, 10):
    A.append(str(i))

keta = 1
for i in range(9):
    ap = []
    for j in range(len(A)):
        a = A[j]
        if len(a)<keta:
            continue
        l = int(a[-1])
        for k in range(max(0, l-1), min(10, l+2)):
            ap.append(a+str(k))
    keta += 1
    for j in ap:
        A.append(j)
for i in range(len(A)):
    A[i] = int(A[i])
A.sort()
print(A[P-1])

Submission status: Accepted

Solution code:
import collections


def go_next(digits):
    if all(x==9 for x in digits):
        return [0]*len(digits) + [1]

    digits[0] += 1

    maxInc = -1
    # print(digits)
    for i in range(1, len(digits)):
        if digits[i-1] >= 10 or abs(digits[i]-digits[i-1]) >= 2:
            digits[i] += 1
            maxInc = i
        else:
            break
    # print(digits)
    if maxInc > 0:
        for i in range(maxInc, 0, -1):
            digits[i-1] = max(0, digits[i]-1)
    return digits


# go_next([9,8])


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

    digits = [0]
    for _ in range(K):
        digits = go_next(digits)

    print("".join(map(str, reversed(digits))))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    k = int(input())
    xl = [[] for i in range(11)]
    xl[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    if k < 10:
        print(xl[0][k-1])
        return 
    k -= 9
    for i in range(1, 11):
        pl = []
        for x in xl[i-1]:
            m = x%10
            if m == 0:
                for mi in range(m, m+2):
                    pl.append(10*x+mi)
                k -= 2
            elif m == 9:
                for mi in range(m-1, m+1):
                    pl.append(10*x+mi)
                k -= 2
            else:
                for mi in range(m-1, m+2):
                    pl.append(10*x+mi)
                k -= 3
            if k <= 0:
                print(pl[k-1])
                return
        xl[i] = pl

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
anss = ["1","2","3","4","5","6","7","8","9"]
cot  = 0

cot = 9
while cot < n:
    for temp in anss: #tempは条件を満たしている→tempの後ろにiが付けられたらそれも条件を満たす
        temp_int = int(temp[-1])
        start = max(0,temp_int - 1)
        end = min(10, temp_int + 2)
        for i in range(start,end):
            anss.append(temp + str(i))
            cot += 1
        if cot > n:
            break




anss = list(map(int,anss))
anss.sort()
print(anss[n -1])

Submission status: Accepted

Solution code:
K=int(input())
b=[[i] for i in range(1,10)]
l=[0,9, 35, 110, 327, 956, 2782, 8089, 23527, 68468,200000]
for i in range(11):
    if K<=l[i]:
        N=i
        K-=l[i-1]
        break
for i in range(N-1):
    a=[]
    for j in b:
        if j[-1]!=0:
            a.append(j+[j[-1]-1])
        a.append(j+[j[-1]])
        if j[-1]!=9:
            a.append(j+[j[-1]+1])
    b=a
print(*b[K-1],sep="")

Submission status: Accepted

Solution code:
K = int(input())

lunlun = [[0] * 10 for _ in range(10)]

for i in range(10):
    lunlun[0][i] = 1
for i in range(1, 10):
    for j in range(10):
        if j != 0 and j != 9:
            lunlun[i][j] = lunlun[i-1][j-1] + lunlun[i-1][j] + lunlun[i-1][j+1]
        if j == 0:
            lunlun[i][0] = lunlun[i-1][0] + lunlun[i-1][1]
        if j == 9:
            lunlun[i][9] = lunlun[i-1][8] + lunlun[i-1][9]

count = 0
digit = 0
ans = 0
k = 0
for i in range(10):
    for j in range(1, 10):
        if count + lunlun[i][j] < K:
            count += lunlun[i][j]
        else:
            k = K - count
            ans = j * (10 ** i)
            digit = i
            last_digit = j
            break
    if ans != 0:
        break

while(digit > 0):
    digit -= 1
    count = 0
    if last_digit != 0:
        if count + lunlun[digit][last_digit-1] < k:
            count += lunlun[digit][last_digit-1]
        else:
            k = k - count
            ans += (last_digit-1) * (10 ** digit)
            last_digit = last_digit - 1
            continue
    if count + lunlun[digit][last_digit] < k:
        count += lunlun[digit][last_digit]
    else:
        k = k - count
        ans += last_digit * (10 ** digit)
        last_digit = last_digit
        continue
    if last_digit != 9:
        if count + lunlun[digit][last_digit+1] < k:
            count += lunlun[digit][last_digit+1]
        else:
            k = k - count
            ans += (last_digit+1) * (10 ** digit)
            last_digit = last_digit + 1
            continue


print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

a = []

def g(x):
    for i in range(-1,2):
        last = int(x[-1]) + i
        if int(''.join(x)) <= 3234566667 and last != -1 and last != 10:
            y = copy.copy(x)
            y.append(str(last))
            f(y)
    return

def f(x):
    a.append(int(''.join(x)))
    g(x)
    return

f(['1'])
f(['2'])
f(['3'])
f(['4'])
f(['5'])
f(['6'])
f(['7'])
f(['8'])
f(['9'])
a.sort()

def main():
    n = inp()
    print(a[n-1])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import os
import sys

from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def is_ok(n):
    s = str(n)
    ok = True
    for a, b in zip(s, s[1:]):
        if not abs(int(a) - int(b)) <= 1:
            return False
    return True


@lru_cache(maxsize=None)
def rekkyo(n, d):
    if d == 0:
        return ['']
    ret = []
    if n > 0:
        for s in rekkyo(n - 1, d - 1):
            ret.append(str(n - 1) + s)
    for s in rekkyo(n, d - 1):
        ret.append(str(n) + s)
    if n < 9:
        for s in rekkyo(n + 1, d - 1):
            ret.append(str(n + 1) + s)
    return ret


K = int(sys.stdin.buffer.readline())

s = set()
for i in range(10):
    for j in range(1,11):
        a = rekkyo(i, j)
        s |= set(a)
a = list(sorted(set(list(map(int, s)))))
print(a[K])
# for aa in a:
#     print(aa)

Submission status: Accepted

Solution code:
memo = dict()

def rec(i, d, l, m, N, L):
    if i == L:
        return 1
    if (i, d, l, m) in memo:
        return memo[i, d, l, m]
    ret = 0
    if l == 0:
        if m == 0:
            for dd in range(10):
                if abs(dd - d) <= 1:
                    ret += rec(i+1, dd, l, m, N, L)
        else:
            n = int(N[i])
            for dd in range(n):
                if abs(dd - d) <= 1:
                    ret += rec(i+1, dd, l, 0, N, L)
            if abs(d - n) <= 1:
                ret += rec(i+1, n, l, 1, N, L)
    elif l == 1:
        if m == 0:
            ret += rec(i+1, 0, 1, m, N, L)
            for dd in range(1, 10):
                ret += rec(i+1, dd, 0, m, N, L)
        elif m == 1:
            n = int(N[i])
            for dd in range(n):
                ret += rec(i+1, dd, dd == 0, 0, N, L)
            ret += rec(i+1, n, n == 0, 1, N, L)

    memo[i, d, l, m] = ret
    return ret


def main() -> None:
    K = int(input())
    # memo.clear()
    # N = 3234566667
    # print(rec(0, 0, 1, 1, str(N), len(str(N))))
    left, right = 0, 10 ** 10
    while left + 1 < right:
        mid = (left + right) // 2
        L = len(str(mid))
        memo.clear()
        cnt = rec(0, 0, 1, 1, str(mid), len(str(mid))) - 1
        if cnt >= K:
            right = mid
        else:
            left = mid
    print(right)


if __name__ == '__main__':
    main()