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())
A = [1,2,3,4,5,6,7,8,9]
for i in range(len(A)):
    if A[i] != 9:
        for j in range(-1,2):
            a = int(str(A[i]) + str(A[i]+j))
            A.append(a)
    else:
        A.append(98)
        A.append(99)
A.append(100)
A.append(101)
L1 = len(A.copy())
for i in range(10, L1):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L2 = len(A.copy())
for i in range(8):
    for i in range(L1,L2):
        B = A[i]
        if B % 10 == 0:
            A.append(int(str(B) + '0'))
            A.append(int(str(B) + '1'))
        elif B % 10 == 9:
            A.append(int(str(B) + '8'))
            A.append(int(str(B) + '9'))
        else:
            for j in range(-1, 2):
                a = int(str(B) + str((B % 10) + j))
                A.append(a)
    L1 = L2
    L2 = len(A.copy())
print(A[K-1])

Submission status: Accepted

Solution code:
k = int(input())
l = ['1','2','3','4','5','6','7','8','9']
lf = ['1','2','3','4','5','6','7','8','9']
sum = 9
while sum < k:
    lff = []
    for i in lf:
        if i[-1] == '0':
            lff.append(i+'0')
            lff.append(i+'1')
        elif i[-1] == '9':
            lff.append(i+'8')
            lff.append(i+'9')
        else:
            lff.append(i+str(int(i[-1])-1))
            lff.append(i+str(int(i[-1])))
            lff.append(i+str(int(i[-1])+1))
    lf = lff
    l += lff
    sum += len(lff)
print(int(l[k-1]))

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

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

num = 0

while True:
    x = q.popleft()
    num += 1
    if num == k:
        break
    y = x % 10
    if y != 0:
        q.append(10 * x + y - 1)
    q.append(10 * x + y)
    if y != 9:
        q.append(10 * x + y + 1)

print(x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import heapq

def suc(s):
    return s + str(int(s[-1]) + 1)

def prev(s):
    return s + str(int(s[-1]) - 1)

def f(k):
    pq = list(range(1, 10))
    heapq.heapify(pq)
    i = 0
    while i < k:
        a = heapq.heappop(pq)
        yield a

        i += 1
        a_ = str(a)
        if a_[-1] < "9":
            down = int(suc(a_))
            heapq.heappush(pq, down)

        if a_[-1] > "0":
            up = int(prev(a_))
            heapq.heappush(pq, up)

        flat = int(a_ + a_[-1])
        heapq.heappush(pq, flat)

def main():
    k = int(input())
    ans = list(f(k))
    print(ans[-1])




main()

Submission status: Accepted

Solution code:
#n桁のるんるん数のrisutoを求める
import sys

sys.setrecursionlimit(10**9)

def runrun(n):
    if n == 1:
        return [['1','2','3','4','5','6','7','8','9']]
    else:
        li = runrun(n-1)
        li2 = []
        for i in range(len(li[n-2])):
            p = int(li[n-2][i][-1])
            if p == 0:
                li2.append(li[n-2][i]+'0')
                li2.append(li[n-2][i]+'1')
            elif p == 9:
                li2.append(li[n-2][i]+str(8))
                li2.append(li[n-2][i]+'9')
            else:
                li2.append(li[n-2][i]+str(p-1))
                li2.append(li[n-2][i]+str(p))
                li2.append(li[n-2][i]+str(p+1))
        li2 =[li2]
        li.extend(li2)
        return li
    


x = int(input())
t = True
k=1
b = 0
while t:
    a = runrun(k)
    b = 0
    #k桁までに何個るんるん数があるか数えるもの
    for i in range(len(a)):
        b+=(len(a[i]))
        #k桁ということが確定したあと以下の処理を行う
    if x <= b:
        t = False
        if k == 1:
            print(x)
        else:
            tmp = runrun(k-1)
            c = 0
#まずk-1桁までのるんるん数の数を数える
            for i in range(len(tmp)):
                c += (len(tmp[i]))
            s = a[k-1][x-c-1]
            print(int(s))
    else:
        k += 1

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
k -= 1
de = deque([1,2,3,4,5,6,7,8,9])
while k > 0:
    x = de.popleft()
    if x%10==0:
        de.append(10*x)
        de.append(10*x+1)
    else:
        de.append(10*x+x%10-1)
        de.append(10*x+x%10)
        if x%10!=9:
            de.append(10*x+x%10+1)
    k -= 1
print(de.popleft())

Submission status: Accepted

Solution code:
K = int(input())
l = [0]*(10**5+10)
l[1:10] = list(range(1,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
        
start = 1
end = 9
while True:
  tmp = []
  for a in l[start:end+1]:
    tmp += list(res(str(a)))
  b = len(tmp)
  start = end+1
  end = start+b-1
  if end<=10**5+5:
    l[start:end+1]=tmp
  else:
    l[start:10**5+5]=tmp[:10**5+5-start]
    break
print(int(l[K]))

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

que = deque(list(range(1,10)))

for _ in range(K-1):
    x = que.popleft()
    p = x % 10
    if p == 0:
        que.extend([10*x, 10*x+1])
    elif p == 9:
        que.extend([10*x+8, 10*x+9])
    else:
        que.extend([10*x + p - 1, 10*x + p, 10*x + p + 1])
print(que.popleft())

Submission status: Accepted

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

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

    S = [str(i) for i in range(1, 10)]
    Sa = [str(i) for i in range(1, 10)]
    while True:
        Ad = []
        for sa in Sa:
            if sa[-1] == '0':
                Ad.append(sa + '0')
                Ad.append(sa + '1')
            elif sa[-1] == '9':
                Ad.append(sa + '8')
                Ad.append(sa + '9')
            else:
                for i in [-1, 0, 1]:
                    Ad.append(sa + str(int(sa[-1]) + i))

        Sa = Ad
        S.extend(Ad)
        if k <= len(S):
            print(S[k - 1])
            exit()

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import deque
K = int(input())
queue = [str(i) for i in range(1, 10)]
# print(queue)
queue = deque(queue)
L = []
cnt = 0
while cnt < K:
    v = queue.popleft()
    # L.push(int(v))
    L.append(int(v))
    if v[-1] == "0":
        # print("v =", v)
        queue.append(v + v[-1])
        queue.append(v+"1")
        
    elif v[-1] == "9":
        # print("9", v)
        queue.append(v + "8")
        queue.append(v + v[-1])
    else:
        # print("else", v)
        t = int(v[-1])
        queue.append(v+str(t-1))
        queue.append(v + v[-1])
        queue.append(v+str(t+1))
    cnt += 1
print(v)

Submission status: Accepted

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

dp = [[0]*10 for _ in range(17)]
for i in range(10):
    dp[0][i] = 1

for keta in range(1, 17):
    for i in range(10):
        if 1 <= i and i <= 8:
            dp[keta][i] += dp[keta-1][i-1]+dp[keta-1][i]+dp[keta-1][i+1]
        if i == 0:
            dp[keta][i] += dp[keta-1][0]+dp[keta-1][1]
        if i == 9:
            dp[keta][i] += dp[keta-1][9]+dp[keta-1][8]
SUM = 0
for keta in range(17):
    SUM += sum(dp[keta][1:])
    if SUM >= K:
        break
SUM = 0
for i in range(keta):
    SUM += sum(dp[i][1:])

r = K-SUM
tmp_r = 0
for i in range(1, 10):
    tmp_r += dp[keta][i]
    if tmp_r >= r:
        tmp_r -= dp[keta][i]
        r -= tmp_r
        break
keta += 1
if keta == 1:
    print(i)
else:
    l=[i]
    rr = 0
    for k in range(keta-1, 0, -1):
        q = deque()
        if i == 0:
            q.append(0)
            q.append(1)
        elif i == 9:
            q.append(8)
            q.append(9)
        else:
            q.append(i-1)
            q.append(i)
            q.append(i+1)
        while q:
            num = q.popleft()
            rr += dp[k-1][num]
            if rr >= r:
                rr -= dp[k-1][num]
                l.append(num)
                i = num
                break
    keta = len(l)
    ans = 0
    for i in range(keta):
        ans += l[keta-i-1]*10**i
    print(ans)

Submission status: Accepted

Solution code:
K = int(input())
from queue import Queue
q = Queue()
for i in range(9):
    q.put(i+1)
num = 0
for i in range(K):
    num = q.get()
    if num%10 != 0:
        q.put(num*10+num%10-1)
    q.put(num*10+num%10)
    if num%10 != 9:
        q.put(num*10+num%10+1)
print(num)

Submission status: Accepted

Solution code:
n = int(input())
f = list()
def dfs(k, a):
  if not k:
    f.append(a)
    return
  if not a:
    for i in range(10):
      dfs(k-1, i)
    return 
  t = a % 10
  dfs(k-1, a*10 + t)
  if t: dfs(k-1, a*10 + t - 1)
  if t < 9: dfs(k-1, a*10 + t + 1)
  return

dfs(11, 0)
f.sort()
print(f[n])

Submission status: Accepted

Solution code:
def countup(nums):
  flag = [False for _ in range(len(nums))]
  
  nums[0] += 1
  
  for i in range(len(nums)-1):
    if nums[i] == 10 or nums[i] - nums[i+1] >= 2:
      flag[i] = True
      nums[i+1] += 1
  
  if nums[-1] == 10:
    nums[-1] = 0
    nums.append(1)
    
  for i in range(len(nums)-2, -1, -1):
    if flag[i]:
      if nums[i+1] == 0:
        nums[i] = 0
      else:
        nums[i] = nums[i+1] - 1
  return nums

N = int(input())

nums = [0]

for i in range(N):
  nums = countup(nums)
  
for i in range(len(nums)-1, -1, -1):
  print(nums[i], end='')
  
print('')

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    K = II()
    if K <= 10:
            print(K)
            return
    x = [0]
    x = [0,1]
    for _ in range(K-10):
        # print(x)
        c = 1
        for j in range(len(x)):
            if c == 0:
                break
            x[j] += 1
            c = x[j] // 10
            x[j] %= 10
        if c == 1:
            x.append(1)


        for i in range(1,len(x)):
            d = x[i] - x[i-1]
            if d < -1:
                c = 1
                for j in range(i,len(x)):
                    if c == 0:
                        break
                    x[j] += 1
                    c = x[j] // 10
                    x[j] %= 10
                if c == 1:
                    x.append(1)
                for j in range(i,0,-1):
                    x[j-1] = max(x[j] - 1,0)
            elif d > 1:
                x[i-1] = x[i] - 1
        for i in range(len(x)-1,0,-1):
            if x[i] - x[i-1] > 1:
                x[i-1] = x[i] -1

    
    ans = 0
    # print(x)
    for i in x[::-1]:
        ans *= 10
        ans += i
    print(ans)
    

    
    

if __name__ == '__main__':

    main()

Submission status: Accepted

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

count = 0
x = 0

runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
def dfs(current, next, max_len):
    if next < 0 or next > 9:
        return
    current.append(str(next))
    if len(current) == max_len:
        tmp = ''.join(current)
        runrun.append(int(tmp))
        return
    dfs(copy.deepcopy(current), next - 1, max_len)
    dfs(copy.deepcopy(current), next, max_len)
    dfs(copy.deepcopy(current), next + 1, max_len)

for i in range(1, 10):
    dfs([], i, 2)
for i in range(1, 10):
    dfs([], i, 3)
for i in range(1, 10):
    dfs([], i, 4)
for i in range(1, 10):
    dfs([], i, 5)
for i in range(1, 10):
    dfs([], i, 6)
for i in range(1, 10):
    dfs([], i, 7)
for i in range(1, 10):
    dfs([], i, 8)
for i in range(1, 10):
    dfs([], i, 9)
for i in range(1, 5):
    dfs([], i, 10)

print(runrun[k - 1])

Submission status: Accepted

Solution code:
K = int(input())

str_runrun = "1"

for i in range(K-1):
    str_next_runrun = str_runrun
    # 次のルンルン数を作る。ただし、未定の桁は"x"にしておく。
    for j in range(1, len(str_runrun)+1):
        if j < len(str_runrun):
            if abs(int(str_runrun[-(j+1)]) - (int(str_runrun[-j])+1)%10) <= 1:
                str_next_runrun = str_runrun[:-j] + str(int(str_runrun[-j])+1) + "x"*max((j-1),0)
                break
            else:
                pass
        elif str_runrun[0] != "9":
            str_next_runrun = str(int(str_runrun[0])+1) + "x"*(len(str_runrun)-1)
        else:
            str_next_runrun = "1" + "x"*len(str_runrun)
    # "x"にしておいた未定の桁を埋める。
    str_next_runrun_no_x_list = []
    for l in str_next_runrun:
        if l != "x":
            str_next_runrun_no_x_list.append(l)
        else:
            str_next_runrun_no_x_list.append(str(max(int(str_next_runrun_no_x_list[-1])-1, 0)))
    str_runrun = "".join(str_next_runrun_no_x_list)

print(str_runrun)

Submission status: Accepted

Solution code:
n = int(input())
t = [1,2,3,4,5,6,7,8,9]
if n < 10:
    print(n)
else:
  i = 0
  while len(t) < n:
    a = t[i]
    b = a % 10
    if b == 0:
        c = a*10
        t.append(c)
        c += 1
        t.append(c)
    elif b == 9:
        c = a*10+8
        t.append(c)
        c += 1
        t.append(c)
    else:
        c = a*10 + b -1
        t.append(c)
        c += 1
        t.append(c)
        c += 1
        t.append(c)
    i += 1
  print(t[n-1])

Submission status: Accepted

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

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

     runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     count = 0
     while(len(runrun) < k):
          target = runrun[count]
          num = target % 10
          if num != 0:
               runrun.append(target * 10 + num - 1)
          runrun.append(target * 10 + num)
          if num != 9:
               runrun.append(target * 10 + num + 1)

          count += 1
          # print(runrun)

     print(runrun[k-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


K = I()

ans = []
def fn(n):
    ns = str(n)
    tail = int(ns[-1])
    if tail > 0:
        yield int(ns + str(tail - 1))
    yield int(ns + ns[-1])
    if tail < 9:
        yield int(ns + str(tail + 1))


for i1 in range(1, 10):
    ans.append(i1)
    for i2 in fn(i1):
        ans.append(i2)
        for i3 in fn(i2):
            ans.append(i3)
            for i4 in fn(i3):
                ans.append(i4)
                for i5 in fn(i4):
                    ans.append(i5)
                    for i6 in fn(i5):
                        ans.append(i6)
                        for i7 in fn(i6):
                            ans.append(i7)
                            for i8 in fn(i7):
                                ans.append(i8)
                                for i9 in fn(i8):
                                    ans.append(i9)
                                    for i10 in fn(i9):
                                        ans.append(i10)


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

Submission status: Accepted

Solution code:
k = int(input())
from collections import deque
q = deque()
a = list(map(str, list(range(1, 10))))
ans = a + []
illist = []
for i in range(10):
    if i == 0:
        illist.append(["0","1"])
    elif i == 9:
        illist.append(["8","9"])
    else:
        illist.append([str(i-1),str(i),str(i+1)])
for i in range(1,10):
    q.append(str(i))

node = "0"
while node != "323456667":
    node = q.popleft()
    for j in illist[int(node[-1])]:
        nodej = node+j
        q.append(nodej)
        a.append(nodej)

print(a[k - 1])

Submission status: Accepted

Solution code:
K = int(input())
A = [1,2,3,4,5,6,7,8,9]
for i in range(len(A)):
    if A[i] != 9:
        for j in range(-1,2):
            a = int(str(A[i]) + str(A[i]+j))
            A.append(a)
    else:
        A.append(98)
        A.append(99)
A.append(100)
A.append(101)
L1 = len(A.copy())
for i in range(10,L1):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L2 = len(A.copy())
for i in range(L1,L2):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B%10) + j))
            A.append(a)
L3 = len(A.copy())
for i in range(L2,L3):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L4 = len(A.copy())
for i in range(L3,L4):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L5 = len(A.copy())
for i in range(L4,L5):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L6 = len(A.copy())
for i in range(L5,L6):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L7 = len(A.copy())
for i in range(L6,L7):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L8 = len(A.copy())
for i in range(L7,L8):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
print(A[K-1])

Submission status: Accepted

Solution code:
import os
import sys
from collections import deque

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

# 解説
K = int(sys.stdin.buffer.readline())
que = deque(list(map(str, range(1, 10))))
for _ in range(K - 1):
    # print(que)
    s = que.popleft()
    d = int(s[-1])
    if d > 0:
        que.append(s + str(d - 1))
    que.append(s + str(d))
    if d < 9:
        que.append(s + str(d + 1))
print(int(que[0]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
from copy import copy

def get_digits(i):
    last_digit = int(str(i)[-1])
    if last_digit in list(range(1,9)):
        return [last_digit-1, last_digit, last_digit+1]
    elif last_digit == 0:
        return [last_digit, last_digit+1]
    elif last_digit == 9:
        return [last_digit-1, last_digit]

def solve(K: int):
    deq1 = deque()
    deq2 = deque()
    lunlun_list = []

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

    while  len(lunlun_list) <= 10 ** 5:
        num = deq1.popleft()
        digits = get_digits(num)
        for new_digit in digits:
            new_num = int(str(num)+str(new_digit))
            lunlun_list.append(new_num)
            deq2.append(new_num)

        if len(deq1) == 0:
            deq1 = copy(deq2)
            deq2 = deque()

    print(lunlun_list[K-1])


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect

k = int(input())
A = list(range(10))

if k <= 9:
    print(A[k])
    exit()


def is_1_keta(i):
    return len(str(i)) == 1


kouho = list(map(str, range(1, 10)))
kouho2 = list(map(str, range(1, 10)))
while True:
    ll = []
    for i in kouho:
        su = list(filter(is_1_keta, [int(i[-1]) - 1, int(i[-1]), int(i[-1]) + 1]))
        l = [str(i) + str(x) for x in su]
        A.extend(l)
        ll.extend(l)
    kouho = ll
    kouho2.extend(ll)
    if len(kouho2) > k:
        break

print(sorted(list(map(int, kouho2)))[k - 1])

Submission status: Accepted

Solution code:
import sys

def lunlun(n0, n,m):
    ans = list()

    if (n<n0 and m-1>=0) :    
        ans.append(m-1)
    ans.append(m)
    if n<n0 and m+1<=9:
        ans.append(m+1)

    if (n==1):
        return ans
    else:
        ans2=list()
        for i in ans:
            ans1=lunlun(n0, n-1, i)
            for j in ans1:
                ans2.append(str(i)+str(j))
        return ans2

K=int(input())

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

for j in range(2,11):
    for i in range(1,10):
        add=lunlun(j, j, i)
        ans=ans+add

#print(ans)
print(ans[K-1])
#print(len(ans))

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import deque
K = int(input())
D = [str(i) for i in range(1, 10)]
D = deque(D)
cnt = 0
while cnt < K:
    v = D.popleft()
    if v[-1] == "0":
        D.append(v + "0")
        D.append(v + "1")
    elif v[-1] == "9":
        D.append(v+"8")
        D.append(v+"9")
    else:
        D.append(v + str(int(v[-1]) - 1))
        D.append(v + v[-1])
        D.append(v + str(int(v[-1]) + 1))
    cnt += 1
print(v)

Submission status: Accepted

Solution code:
K=int(input())
x=[[0] for _ in range(11)]
y=[ 0 for _ in range(11)]

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

for i in range(2,11):
  x[i].pop()
  for num in x[i-1]:
    last = num%10
    if last==0:
      x[i].append(10*num)
      x[i].append(10*num+1)
      y[i] +=2
    elif last==9:
      x[i].append(10*num+8)
      x[i].append(10*num+9)
      y[i] +=2
    else:
      x[i].append(10*num+(last-1))
      x[i].append(10*num+last)
      x[i].append(10*num+(last+1))
      y[i] +=3
      
#print(y)
#print(sum(y))

z=[0,y[1]]
for i in range(2,11):
 z.append(z[-1]+y[i])
#print(z)

keta=0
for i,num in enumerate(z):
  if num<=K:
    keta=i+1

s= K-z[keta-1]
#print(s)
print(x[keta][s-1])

Submission status: Accepted

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

lis = []
def search(s):
  lis.append(s)
  
  if int(s) > 3234566667:
    return
  
  it = int(s[-1])
  if it == 0:
    search(s + '0')
    search(s + '1')
  elif it == 9:
    search(s + '8')
    search(s + '9')
  else:
    search(s + str(it - 1))
    search(s + str(it))
    search(s + str(it + 1))
  

for i in range(1, 10):
  search(str(i))

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

Submission status: Accepted

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

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)


def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
    
    k = int(lines[0])

    return (k, )


def solve(k):

    nums = [str(e) for e in range(1, 10)]

    def find(found):
        new_found = []
        for f in found:
            last_num = int(f[-1])

            if last_num == 0:
                new_found.append(f + str(last_num ))
                new_found.append(f + str(last_num + 1))
            elif 1 <= last_num and last_num <= 8:
                new_found.append(f + str(last_num - 1))
                new_found.append(f + str(last_num ))
                new_found.append(f + str(last_num + 1))
            elif last_num == 9:
                new_found.append(f + str(last_num - 1))
                new_found.append(f + str(last_num ))
        
        
        cnt = len(found) + len(new_found)
        if cnt < k:
            total_found = found + find(new_found)
        else:
            total_found = found + new_found
            
        return total_found

    total_found = find(nums)
    total_found_as_int = [int(e) for e in total_found]
    total_found_as_int.sort()

    result = total_found_as_int[k-1]
    
    return result

def main():
    # 出力
    new_found = solve(*parse_input())
    if isinstance(new_found, list):
        for r in new_found:
            print("%s" % r, sep='')
    else:
        print("%s" % new_found, sep='')

if __name__ == '__main__':

    main()

Submission status: Accepted

Solution code:
from functools import lru_cache
# 上がうまく使えない場合、以下を使う(僕はうまくいかなかったのでこっちを使った)
# from functools32 import lru_cache 

k = int(input())

@lru_cache(maxsize=None)
def check(num, keta):
  if keta == 1:
    return 1
  l = [i for i in range(10) if abs(num-i) <= 1]
  result = 0
  for i in l:
    result += check(i, keta-1)
  return result

s = ''
n = 10
keta = 2
f = True

if k <= 9:
  print(k)
else:
  checker = 9
  while f:
    for i in range(1, 10):
      pre_checker = checker
      checker += check(i, keta)
      if checker >= k:
        n = i
        s += str(i)
        keta -= 2
        checker = pre_checker
        f = False
        break
    keta += 1
    
  while keta != 0:
    l = [i for i in range(10) if abs(n-i) <= 1 ]
    for i in l:
      pre_checker = checker
      checker += check(i, keta)
      if checker >= k:
        keta -= 1
        s += str(i)
        n = i
        checker = pre_checker
        break
  
print(s)

Submission status: Accepted

Solution code:
import numpy as np

k=int(input())
a=np.array([i+1 for i in range(9)])
ans=a
temp=a
for i in range(10):
    for j in range(3):
        b=temp*10+temp%10
        c=temp*10+np.minimum(temp%10+1,9)
        d=temp*10+np.maximum(temp%10-1,0)
    ans=np.append(np.append(np.append(ans,b),c),d)
    temp=np.append(np.append(b,c),d)

ans=np.sort(np.unique(ans))
print(ans[k-1])

Submission status: Accepted

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

ans = []

def solve(x, l):
    if int(x) > 3234566667:
        return l

    l.append(int(x))
    if x[-1] == '0':
        solve(x + '0', l)
        solve(x + '1', l)
    elif x[-1] == '9':
        solve(x + '9', l)
        solve(x + '8', l)
    else:
        last_digit = int(x[-1])
        for i in range(-1, 2):
            new_digit = last_digit + i
            solve(x + str(new_digit), l)

for i in range(1, 10):
    solve(str(i), ans)
ans.sort()
print(ans[k - 1])

Submission status: Accepted

Solution code:
k = int(input())

numset = {i for i in range(1,10)}
flag = False
count = len(numset)
if count >= k:
    flag = True
arr = [numset]
index = 0

while not flag:
    beforeset = arr[index]
    tmpset = set()
    for i in beforeset:
        tail = str(i)[-1]
        if tail == "0":
            tmpset.add(int(str(i)+str(0)))
            tmpset.add(int(str(i)+str(1)))
        elif tail == "9":
            tmpset.add(int(str(i)+str(8)))
            tmpset.add(int(str(i)+str(9)))
        else:
            tmpset.add(int(str(i)+str(int(tail))))
            tmpset.add(int(str(i)+str(int(tail)+1)))
            tmpset.add(int(str(i)+str(int(tail)-1)))
    count += len(tmpset)
    if count >= k:
        flag = True
    arr.append(tmpset)
    index += 1
    
totalarr = []
for tmpset in arr:
    totalarr += list(tmpset)
    
totalarr.sort()
print(totalarr[k-1])

Submission status: Accepted

Solution code:
import heapq

K = int(input())
count = 0
ans = []
heapq_list = []
# リストを優先度付きキューへ
# 配列で渡した場合，インデックス0によって並び替えが行われる
# インデックス0に重さが入る
heapq.heapify(heapq_list)
for i in range(1,10):
    heapq.heappush(heapq_list, i)
    count += 1

while heapq_list != []:
    current_number = heapq.heappop(heapq_list)
    ans.append(current_number)
    if count <= 10**5:
        if str(current_number)[len(str(current_number))-1] == "0":
            heapq.heappush(heapq_list, int(str(current_number) + "0"))
            heapq.heappush(heapq_list, int(str(current_number) + "1"))
            count += 2
        elif str(current_number)[len(str(current_number))-1] == "9":
            heapq.heappush(heapq_list, int(str(current_number) + "8"))
            heapq.heappush(heapq_list, int(str(current_number) + "9"))
            count += 2
        else:
            heapq.heappush(heapq_list, int(str(current_number) + str(int(str(current_number)[len(str(current_number))-1])-1)))
            heapq.heappush(heapq_list, int(str(current_number) + str(int(str(current_number)[len(str(current_number))-1]))))
            heapq.heappush(heapq_list, int(str(current_number) + str(int(str(current_number)[len(str(current_number))-1])+1)))
            count += 3
print(ans[K-1])

Submission status: Accepted

Solution code:
def lun(s):
    ch = 1
    temp = int(s[0])
    for i in s[1: ]:
        i = int(i)
        if abs(i - temp) > 1:
            ch = 0
            break
        temp = i
    return ch
k = int(input())
d = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
l = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
while 1:
    for i in l:
        for j in d:
            # print(i, j)
            s = i + str(j)
            if lun(s): l.append(s)
        if len(l) >= 100002: break
    if len(l) >= 100002: break
print(l[k - 1])