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:
import sys

K = int(input())
s = [1,2,3,4,5,6,7,8,9,10,11,12,21,22,23,32,33,34,43,44,45,54,55,56,65,66,67,76,77,78,87,88,89,98,99]

if K <= 35:
  print(s[K-1])
  sys.exit()

heads = ["10","11","12","21","22","23","32","33","34","43","44","45","54","55","56","65","66","67","76","77","78","87","88","89","98","99"]
s = len(heads)
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]}


i = 0
K = K-10
while True:
  lenHeads = len(heads)
  if lenHeads-1 >= K:
      print(int(heads[K]))
      sys.exit()
  now = heads[i]
  tail = now[-1]
  values = dic[int(tail)]
  for v in values:
      newHead = "".join([now,str(v)])
      heads.append(newHead)
  i+=1

Submission status: Accepted

Solution code:
nyuryoku=int(input())
lunlun=[["1","2","3","4","5","6","7","8","9"],[],[],[],[],[],[],[],[],[]]
numbers=[["0","1"],["0","1","2"],["1","2","3"],["2","3","4"],["3","4","5"],["4","5","6"],["5","6","7"],["6","7","8"],["7","8","9"],["8","9"]]

for i in range(9):
    for j in lunlun[i]:
        if j[-1]=="0":
            for k in numbers[0]:
                lunlun[i+1].append(j+k)
        elif j[-1]=="1":
            for k in numbers[1]:
                lunlun[i+1].append(j+k)
        elif j[-1]=="2":
            for k in numbers[2]:
                lunlun[i+1].append(j+k)
        elif j[-1]=="3":
            for k in numbers[3]:
                lunlun[i+1].append(j+k)
        elif j[-1]=="4":
            for k in numbers[4]:
                lunlun[i+1].append(j+k)
        elif j[-1]=="5":
            for k in numbers[5]:
                lunlun[i+1].append(j+k)
        elif j[-1]=="6":
            for k in numbers[6]:
                lunlun[i+1].append(j+k)
        elif j[-1]=="7":
            for k in numbers[7]:
                lunlun[i+1].append(j+k)
        elif j[-1]=="8":
            for k in numbers[8]:
                lunlun[i+1].append(j+k)
        elif j[-1]=="9":
            for k in numbers[9]:
                lunlun[i+1].append(j+k)

newrunrun=[]
for i in range(len(lunlun)):
    newrunrun+=lunlun[i]
newlunlun=list(map(int,newrunrun))
newlunlun.sort()
print(newlunlun[nyuryoku-1])

Submission status: Accepted

Solution code:
K = int(input())

def cal():
    count = 9
    d = [[1,2,3,4,5,6,7,8,9]]
    for i in range(10**9):
        d_ = []
        for j in range(len(d[i])):
            a = str(d[i][j])
            if a[-1]=="0":
                for k in [0, 1]:
                    d_.append(int(a)*10+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return
            elif a[-1]=="9":
                for k in [8, 9]:
                    d_.append(int(a)*10+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return 
            else:
                for k in [-1, 0, 1]:
                    d_.append(int(a)*10+int(a[-1])+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return
        d.append(d_)
if K <= 9:
    print(K)
else:
    cal()

Submission status: Accepted

Solution code:
K = int(input())

lun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for idx, ll in enumerate(lun, start=1):
    base = int(str(ll)[-1])
    candi = list(filter(lambda x: 0 <= x < 10, [base - 1, base, base + 1]))
    for c in candi:
        target = str(ll) + str(c)
        lun.append(int(target))
    if idx > K:
        break
lun.sort()
# print(lun)
print(lun[K-1])

Submission status: Accepted

Solution code:
n = int(input())
listnum = [[0, 1],[0, 1, 2],[1, 2, 3],[2, 3, 4],[3, 4, 5],[4, 5, 6],[5, 6, 7],[6, 7, 8],[7, 8, 9],[8, 9]]
listans = []
for i in range(1, 10):
    numb = str(i)
    listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        numb = str(i) + str(j)
        listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            numb = str(i) + str(j) + str(m)
            listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                numb = str(i) + str(j) + str(m) + str(x)
                listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                for x2 in listnum[x]:
                    numb = str(i) + str(j) + str(m) + str(x) + str(x2)
                    listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                for x2 in listnum[x]:
                    for x3 in listnum[x2]:
                        numb = str(i) + str(j) + str(m) + str(x) + str(x2) + str(x3)
                        listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                for x2 in listnum[x]:
                    for x3 in listnum[x2]:
                        for x4 in listnum[x3]:
                            numb = str(i) + str(j) + str(m) + str(x) + str(x2) + str(x3) + str(x4)
                            listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                for x2 in listnum[x]:
                    for x3 in listnum[x2]:
                        for x4 in listnum[x3]:
                            for x5 in listnum[x4]:
                                numb = str(i) + str(j) + str(m) + str(x) + str(x2) + str(x3) + str(x4) + str(x5)
                                listans.append(int(numb))
for i in range(1, 10):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                for x2 in listnum[x]:
                    for x3 in listnum[x2]:
                        for x4 in listnum[x3]:
                            for x5 in listnum[x4]:
                                for x6 in listnum[x5]:
                                    numb = str(i) + str(j) + str(m) + str(x) + str(x2) + str(x3) + str(x4) + str(x5) + str(x6)
                                    listans.append(int(numb))
for i in range(1, 5):
    for j in listnum[i]:
        for m in listnum[j]:
            for x in listnum[m]:
                for x2 in listnum[x]:
                    for x3 in listnum[x2]:
                        for x4 in listnum[x3]:
                            for x5 in listnum[x4]:
                                for x6 in listnum[x5]:
                                    for x7 in listnum[x6]:
                                        numb = str(i) + str(j) + str(m) + str(x) + str(x2) + str(x3) + str(x4) + str(x5) + str(x6) + str(x7)
                                        listans.append(int(numb))
print(listans[n - 1])

Submission status: Accepted

Solution code:
import numpy as np

K = int(input())

top = np.ones(10, dtype=int)
adj = np.eye(10, dtype=int)
adj[1:, :-1] += np.eye(9, dtype=int)
adj[:-1, 1:] += np.eye(9, dtype=int)

counts = [top]
tmp = top
for _ in range(10):
    tmp = np.dot(tmp, adj)
    counts.append(tmp)

for i in range(10):
    for j in range(1, 10):
        if K > counts[i][j]:
            K -= counts[i][j]
        else:
            break
    else:
        continue
    break

ans = [-1] * (i + 1)
ans[i] = j

for d in range(i, 0, -1):
    for k in range(max(0, j - 1), min(9, j + 1) + 1):
        if K > counts[d - 1][k]:
            K -= counts[d - 1][k]
        else:
            ans[d - 1] = k
            j = k
            break


print("".join(list(map(str, ans))[::-1]))

Submission status: Accepted

Solution code:
K = int(input())
l = [0]*(10**5+10)
l[1:10] = list(range(1,10))
keta = 2
i=10
def res(now):
    if int(now[-1])==0:
      for a in range(0,2):
        ret=str(now)+str(a)
        yield ret
    elif int(now[-1])==9:
      for a in range(8,10):
        ret=str(now)+str(a)
        yield ret
    else:
      for a in range(int(now[-1])-1,int(now[-1])+2):
        ret=str(now)+str(a)
        yield ret
        
while i!=10**5+1:
  if keta==1:
    keta+=1
    l[i]=i
    i+=1
  elif keta==2:
    for j in range(1,10):
      for k in res(str(j)):
        l[i]=k
        i+=1
    keta+=1
  elif keta==3:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          l[i]=a
          i+=1
    keta+=1
  elif keta==4:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            l[i]=b
            i+=1
    keta+=1
  elif keta==5:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            for c in res(str(b)):
              l[i]=c
              i+=1
    keta+=1
  elif keta==6:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            for c in res(str(b)):
              for d in res(str(c)):
                l[i]=d
                i+=1
    keta+=1
  elif keta==7:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            for c in res(str(b)):
              for d in res(str(c)):
                for e in res(str(d)):
                  l[i]=e
                  i+=1
    keta+=1
  elif keta==8:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            for c in res(str(b)):
              for d in res(str(c)):
                for e in res(str(d)):
                  for f in res(str(e)):
                    l[i]=f
                    i+=1
    keta+=1
  elif keta==9:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            for c in res(str(b)):
              for d in res(str(c)):
                for e in res(str(d)):
                  for f in res(str(e)):
                    for g in res(str(f)):
                      l[i]=g
                      i+=1
    keta+=1
  elif keta==10:
    for j in range(1,10):
      for k in res(str(j)):
        for a in res(str(k)):
          for b in res(str(a)):
            for c in res(str(b)):
              for d in res(str(c)):
                for e in res(str(d)):
                  for f in res(str(e)):
                    for g in res(str(f)):
                      for h in res(str(g)):
                        l[i]=h
                        i+=1
                        if i==10**5+5:
                          break
                      else:
                        continue
                      break
                    else:
                      continue
                    break
                  else:
                    continue
                  break
                else:
                  continue
                break
              else:
                continue
              break
            else:
              continue
            break
          else:
            continue
          break
        else:
          continue
        break
      else:
        continue
      break
    else:
      continue
    break
    
print(int(l[K]))

Submission status: Accepted

Solution code:
K=int(input())

ans = [0]

def hoge(n):
    global ans
    if ans[-n] != 9:
        ans[-n]+=1
        if check():
            pass
        else:
            huga(n)
    else:
        if len(ans) < n+1:
            ans = [0] * (n+1)
            ans[0] = 1
        else:
            huga(n)

def huga(n):
    global ans
    ans[-(n+1)]+=1
    for i in range(n,0,-1):
        if(ans[-(i+1)]==0):
            ans[-i] = 0
        else:
            ans[-i]=ans[-(i+1)]-1
    ans[-(n+1)]-=1
    hoge(n+1)


def check():
    global ans
    for i in range(len(ans)-1):
        if abs(ans[i]-ans[i+1])>1:
            return False
    return True
       


for i in range(K):
    hoge(1)
print(''.join(map(str,ans)))

Submission status: Accepted

Solution code:
n=int(input())
if n<10: print(n); exit()
l=[[[] for _ in range(10)] for _ in range(10)]
l[0]=[[i] for i in range(10)]
c=9
for i in range(9):
  for j in range(10):
    for k in (-1,0,1):
      if 0<=j+k<=9:
        for h in l[i][j+k]:
          if j: c+=1
          t=j*10**(i+1)+h
          l[i+1][j]+=[t]
          if c==n: print(t); exit()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

k = INT()
if k <= 10:
    print(k)
    exit()
arr = [0 for _ in range(15)]
arr[1] = 1
for i in range(k - 10):
    for j in range(12):
        #print(j, arr[j], sum(range(arr[j], arr[j] + j)))
        flag = True
        for k in range(j):
            if arr[k] == arr[k + 1] + 1 or arr[k] == 9:
                continue
            flag = False
        #print(j, flag)
        if flag and sum(arr[j + 1:]) == 0 and arr[j] < 9:
            #print('c', j)
            arr[j] += 1
            for k in reversed(range(j)):
                arr[k] = max(0, arr[k + 1] - 1)
            break
        elif arr[j] == arr[j + 1] + 1 and arr[j + 1] < arr[j + 2] + 1:
            #print('a', j)
            arr[j + 1] += 1
            for k in reversed(range(j + 1)):
                arr[k] = max(0, arr[k + 1] - 1)
            break
        elif sum(arr[:j + 1]) == 9 * (j + 1) and arr[j + 1] < 9 and (arr[j + 1] < arr[j + 2] + 1 or arr[j + 2] == 0):
            #print('d', j)
            arr[j + 1] += 1
            for k in reversed(range(j + 1)):
                arr[k] = max(0, arr[k + 1] - 1)
            break
        elif (arr[j] == arr[j + 1] or arr[j] == arr[j + 1] - 1) and arr[j] < 9:
            #print('b', j)
            arr[j] += 1
            break
    #print(i + 10, arr)
arr.reverse()
for i in range(15):
    arr[i] = str(arr[i])
ans = ''.join(arr)
ans = int(ans)
print(ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

k = ii()
if k//10 ==0:
    print(k)
    exit()
ans = 0
alis = [[0]*10 for _ in range(100)]
blis = [[0]*10 for _ in range(100)]
for i in range(10):
    alis[0][i] = 1
    blis[0][i] = i
    tmp = i
flag = False
for l in range(1,100):
    for i in range(10):
        if i == 0:
            alis[l][i] = alis[l-1][1] + alis[l-1][0]
            continue
        elif i == 9:
            alis[l][i] = alis[l-1][8] + alis[l-1][9]
        else:
            alis[l][i] = alis[l-1][i] + alis[l-1][i+1] + alis[l-1][i-1]
        blis[l][i] = tmp + alis[l][i] 
        if blis[l][i] >= k:
            banme = k - tmp
            retu = l+1
            hazime = i
            flag = True
            break
        else:
            tmp = blis[l][i]
    if flag:
        break

ans = [0]*retu
ans[0] = hazime
for i in range(1,retu):
    if hazime == 0:
        if banme - alis[retu-1-i][hazime] <=0:
            ans[i] = hazime 
        else:
            banme -= alis[retu-1-i][hazime]
            ans[i] = hazime +1
            hazime = hazime +1
        continue
    elif hazime == 9:
        if banme - alis[retu-1-i][hazime-1] <=0:
            ans[i] = hazime -1
            hazime = hazime -1
        else:
            banme -= alis[retu-1-i][hazime-1]
            ans[i] = hazime 
            hazime = hazime 
        continue
    else:
        if banme - alis[retu-1-i][hazime-1] <=0:
            ans[i] = hazime -1
            hazime = hazime -1
        elif banme - alis[retu-1-i][hazime-1] - alis[retu-1-i][hazime] <=0:
            banme -= alis[retu-1-i][hazime-1]
            ans[i] = hazime 
            hazime = hazime 
        else:
            banme -= (alis[retu-1-i][hazime-1] + alis[retu-1-i][hazime])
            ans[i] = hazime +1
            hazime = hazime +1
aa = 0
for i in range(len(ans)):
    aa += ans[i]*(10**(len(ans)-1-i))
print(aa)

Submission status: Accepted

Solution code:
import numpy as np

k = int(input())


def get_top(rem):
    number = 0

    numbers = np.zeros((100,10), dtype=np.int64)
    numbers[0] += 1
    for i in range(100):
        for j in range(10):
            if j == 0:
                numbers[i+1][j] = numbers[i][j] + numbers[i][j+1]
            elif j == 9:
                numbers[i+1][j] = numbers[i][j-1] + numbers[i][j]
                number += numbers[i+1][j]
            else:
                numbers[i+1][j] = numbers[i][j-1] + numbers[i][j] + numbers[i][j+1]
                number += numbers[i+1][j]
            if number >= rem:
                break
        if number >= rem:
            break
    return i, j, k-(number - numbers[i+1][j]), numbers


def get_after_second(top, remains):
    pass

ans = ""

if k <= 9:
    print(k)
else:
    k -= 9
    dig, top, remain, nums = get_top(k)
    ans += str(top)
    for i in range(dig+1):
        digit = dig - i
        if not top == 0:
            second_top = top - 1
            if not top == 9:
                for j in range(3):
                    if remain - nums[digit][second_top + j] <= 0:
                        top = second_top + j
                        break
                    else:
                        remain -= nums[digit][second_top + j]
            else:
                for j in range(2):
                    if remain - nums[digit][second_top + j] <= 0:
                        top = second_top + j
                        break
                    else:
                        remain -= nums[digit][second_top + j]
        else:
            second_top = top
            for j in range(2):
                if remain - nums[digit][second_top + j] <= 0:
                    top = second_top + j
                    break
                else:
                    remain -= nums[digit][second_top + j]
        ans += str(top)
    print(ans)

Submission status: Accepted

Solution code:
k=int(input())

q=["1","2","3","4","5","6","7","8","9"]
x=9
for i in q:
    if x>100000:
        break
    x+=1
    a=i[-1]
    for j in ([-1,0,1]):
        bb=int(a)+j
        if bb<10 and bb>=0:
            q.append(i+str(bb))
 
       
print(q[k-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def f(n):
    C = [[1 for i in range(10)]]
    while sum(d for c in C for d in c[1:]) < n:
        C.append([sum(C[-1][max(0,i-1):min(i+2,10)]) for i in range(10)])
    return C

def solve():
    n = int(input())
    C = f(n)
    X = []
    m = sum(d for c in C[:-1] for d in c[1:])
    x = 1
    for x in range(1,10):
        if m + C[-1][x] < n:
            m += C[-1][x]
        else:
            break
    X.append(x)
    C = C[:-1]
    for c in C[::-1]:
        for x in range(max(0,X[-1]-1), min(10,X[-1]+2)):
            if m + c[x] < n:
                m += c[x]
            else:
                break
        X.append(x)
    return ''.join(map(str,X))


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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K = INT()

q = [str(i) for i in range(1, 10)]
q = deque(q)
# print(q)

l = []
while len(l) != K:
    a = q.popleft()
    l.append(a)
    for i in range(0, 10):
        last = int(a[-1])
        b = deepcopy(a)
        if last == 0:
            if i == 1 or i == 0:
                b = b + str(i)
                q.append(b)
        elif last == 9:
            if i == 8 or i == 9:
                b = b + str(i)
                q.append(b)
        else:
            if last - 1 <= i <= last + 1:
                b = b + str(i)
                q.append(b)
        
        # print(q)
        # exit()
print(l[-1])

Submission status: Accepted

Solution code:
K = int(input())
ary = [0]*(K+1)
for i in range(min(K+1, 10)):
    ary[i] = str(i)
bi = 1
n = 0
b = int(ary[bi][-1])
for i in range(10, K+1):
    if n > 9:
        bi += 1
        b = int(ary[bi][-1])
        n = b-1
    if n > b+1:
        bi += 1
        b = int(ary[bi][-1])
        n = b-1
    if n < 0:
        n = 0
    ary[i] = ''.join([ary[bi], str(n)])
    n += 1
print(ary[-1])

Submission status: Accepted

Solution code:
k = int(input())

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

digits = [{k: 1 for k in range(10)}]
count = 9
digits[0]["lc"] = 9
while count < k:
    dg = {}
    dg[0] = digits[-1][0] + digits[-1][1]
    for i in range(1, 9):
        dg[i] = digits[-1][i - 1] + digits[-1][i] + digits[-1][i + 1]
    dg[9] = digits[-1][8] + digits[-1][9]
    dg["lc"] = digits[-1]["lc"] + sum(dg[i] for i in range(1, 10))
    count = dg["lc"]
    digits.append(dg)

def count_lun(base, index, last_digit=None):
    if index < 0:
        return ""
    if last_digit is None:
        rng = range(1, 10)
    elif last_digit == 0:
        rng = range(2)
    elif last_digit == 9:
        rng = range(8, 10)
    else:
        rng = range(last_digit - 1, last_digit + 2)
    for i in rng:
        base += digits[index][i]
        if base >= k:
            return str(i) + count_lun(base - digits[index][i], index - 1, i)

res = count_lun(digits[-2]["lc"], len(digits) - 1)
print(res)

Submission status: Accepted

Solution code:
K=int(input())
l=[0,1,2,3,4,5,6,7,8,9]
cnt=0
def dfs(s, depth):
    if depth>8:
        return
    S=str(s)
    ls=int(S[-1])
    for i in range(max(0,ls-1),min(10,ls+2)):
        n=int(S+str(i))
        l.append(n)
        dfs(n, depth+1)
for i in range(1, 10):
    dfs(i, 0)
l.sort()
print(l[K])

Submission status: Accepted

Solution code:
# 全探索 O(10**5)
import sys

K = int(input())
if K < 10:
    print(K)
    sys.exit()
i = 9
operation = [-1, 0, 1]
lst = [str(i + 1) for i in range(9)]
while True:
    tmp = []
    for a in lst:
        for ope in operation:
            val = int(a[-1]) + ope
            if 0 <= val <= 9:
                i += 1
                if i == K:
                    print(int(a + str(val)))
                    sys.exit()
                tmp.append(a + str(val))
    lst = tmp

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

K = int(input())						# 5


A=[0,1,2,3,4,5,6,7,8,9]
S=[]
for a in A:
	S.append(str(a))

from collections import deque
Q = deque()


B=list(S)

while True:
	for a in B:
		Q.append(str(a))
	B=[]

	while Q:
		s = Q.popleft()
		
		a = int(s[0])
		
		x = (str(a-1) + s) if a>0 else ""
		y = (str(a) + s)
		z = (str(a+1) + s) if a<9 else ""
		
		if x!="": B.append(x)
		if y!="": B.append(y)
		if z!="": B.append(z)

	B.sort()
	for b in B:
		if b[0]=="0": continue
		A.append(int(b))

	if len(A)>K:
		ans = A[K]
		print(ans)
		#p(A)
		#p(B)
		exit(0)

Submission status: Accepted

Solution code:
def main():
    k=int(input())
    l=[[] for _ in range(20)]
    l[1]=[0,1,2,3,4,5,6,7,8,9]
    cnt=9
    if cnt>=k:
        print(l[1][k])
        exit()
    for i in range(2,20):
        for keta in range(1,i):
            for j in l[keta]:
                f=j//10**(i-2)
                if j==0:
                    l[i].append(10**(i-1)+j)
                if f==0:
                    if j//10**(len(str(j))-1)==1:
                        l[i].append(10**(i-1)+j)
                elif f==1:
                    l[i].append(10**(i-1)+j)
                    l[i].append(2*10**(i-1)+j)
                elif f==9:
                    l[i].append(8*10**(i-1)+j)
                    l[i].append(9*10**(i-1)+j)
                elif f>0:
                    l[i].append((f-1)*10**(i-1)+j)
                    l[i].append(f*10**(i-1)+j)
                    l[i].append((f+1)*10**(i-1)+j)
        if cnt+len(l[i])>=k:
            l[i].sort()
            ans=l[i][k-cnt-1]
            if ans==0:
                print(10**(i-1))
            else:
                print(ans)
            exit()
        else:
            cnt+=len(l[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k = int(input())

ans = list(range(1, 10))
next_ans = ans

while len(ans)<k:
  temp_ans = []
  
  for a in next_ans:
    a_0 = int(str(a)[-1])
    new_ans = [int(str(a)+str(a_0+i)) for i in [-1,0,1] if 0<=a_0+i<=9]
    temp_ans.extend(new_ans)
  
  ans.extend(temp_ans)
  next_ans = temp_ans
  
  
print(ans[k-1])

Submission status: Accepted

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


cnt = 9
while True:
    a_tmp = []
    for s in a:
        for t in range(max(0, int(str(s[-1])) - 1), min(9, int(str(s[-1])) + 1) + 1):
            a_tmp.append(s+str(t))
            cnt += 1
            if cnt == K:
                print(s+str(t))
                exit()
    a = a_tmp

Submission status: Accepted

Solution code:
k = int(input())
ans = 0
a = ["0","1","2","3","4","5","6","7","8","9"]
old = ["0","1","2","3","4","5","6","7","8","9"]
b = []
l = 0
while l <= 9:
	b = []
	for i in range(10):
		x = str(i)
		for j in old:
			if abs(i- int(j[0])) <= 1:
				y = x + j
				b.append(y)
	a.extend(b)
	old = b.copy()
	l += 1
c = set()
for i in a:
	c.add(int(i))
d = list(c)
d.sort()
print (d[k])

Submission status: Accepted

Solution code:
K = int(input())

lunlun = []
for i in range(10):
    lunlun.append([0, i])

count, itr = 9, 1
while count < K:
    if lunlun[itr][1] == 0:
        lunlun.append([itr, 0])
        lunlun.append([itr, 1])
        count += 2
    elif lunlun[itr][1] == 9:
        lunlun.append([itr, 8])
        lunlun.append([itr, 9])
        count += 2
    else:
        lunlun.append([itr, lunlun[itr][1] - 1])
        lunlun.append([itr, lunlun[itr][1]])
        lunlun.append([itr, lunlun[itr][1] + 1])
        count += 3
    itr += 1

ans = ""
itr = K
while True:
    ans = str(lunlun[itr][1]) + ans
    if lunlun[itr][0] != 0:
        itr = lunlun[itr][0]
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
K = int(input())

F = {}
for i in range(10):
    F[(1, i)] = 1


def f(n, d):
    if (n, d) in F:
        return F[(n, d)]
    nf = 0
    for i in [d - 1, d, d + 1]:
        if 0 <= i <= 9:
            nf += f(n - 1, i)
    F[(n, d)] = nf
    return nf


k = 0
p = (1, 0)
for i in range(1, 11):
    for j in range(1, 10):
        fij = f(i, j)
        if k + fij >= K:
            p = (i, j)
            break
        k += fij
        p = (i, j)
    else:
        continue
    break


def g(n, d, index):
    if n == 1:
        return str(d)
    total = 0
    for i in [d - 1, d, d + 1]:
        if not 0 <= i <= 9:
            continue
        if total + f(n - 1, i) >= index:
            break
        total += f(n - 1, i)
    return str(d) + g(n - 1, i, index - total)


print(g(p[0], p[1], K - k))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque

def main():

    K = int(input())

    ans = []

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

    visited = set()
    for i in range(9):
        visited.add(queue[i])

    for i in range(K):

        current = queue.popleft()
        ans.append(int(current))
        digit_tail = int(current[-1])


        digit_tail_1 = str(digit_tail - 1)
        digit_tail_2 = str(digit_tail)
        digit_tail_3 = str(digit_tail + 1)

        if int(digit_tail_1) != -1 and current+digit_tail_1 not in visited:

            queue.append(current+digit_tail_1)
            visited.add(current+digit_tail_1)

        if current+digit_tail_2 not in visited:
            queue.append(current+digit_tail_2)
            visited.add(current+digit_tail_2)

        if int(digit_tail_3) != 10 and current+digit_tail_3 not in visited:
            queue.append(current+digit_tail_3)
            visited.add(current+digit_tail_3)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k = int(input())

def listappend(list, length):
    templist = [i for i in list if i >= 10 ** (length - 1)]
    for x in templist:
        if x % 10 != 0: list.append(x * 10 + x % 10 - 1)
        list.append(x * 10 + x % 10)
        if x % 10 != 9 : list.append(x * 10 + x % 10 + 1)
    return list

list = [i + 1 for i in range(9)]
numList = [i + 1 for i in range(9)]
for x in numList:
    list.append(x * 10 + x - 1)
    list.append(x * 10 + x)
    if x != 9 : list.append(x * 10 + x + 1)
for x in range(11):
    if x == 0 or x == 1: continue
    list = listappend(list, x)
list.sort()
print(list[k - 1])