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:
def main():
  n=int(input())
  l=0
  runrun=[str(x) for x in range(1,10)]
  while len(runrun)<n:
    l+=1
    def addrunrun(s,n,l):
      if l==0:
        runrun.append(s)
      elif n==0:
        addrunrun(s+"0",0,l-1)
        addrunrun(s+"1",1,l-1)
      elif n==9:
        addrunrun(s+"8",8,l-1)
        addrunrun(s+"9",9,l-1)
      else:
        addrunrun(s+str(n-1),n-1,l-1)
        addrunrun(s+str(n),n,l-1)
        addrunrun(s+str(n+1),n+1,l-1)
    for i in range(1,10):
      addrunrun(str(i),i,l)
  print(runrun[n-1])
main()

Submission status: Accepted

Solution code:
K = int(input())
l = [i for i in range(1,10)]

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

li1 = l[:]
li2 = []
if K < 10:
    print(K)
else:
    while True:
        for i in li1:
            a = func(i)
            li2.extend(a)
        l.extend(li2)
        if len(l) >=K:
            break
        else:
            li1 = li2[:]
            li2 = []
    print(l[K-1])

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
ans = 0
num = ["0","1","2","3","4","5","6","7","8","9"]
dq = deque(["1","2","3","4","5","6","7","8","9"])
# print(num[k:k+2])
if k<=12:
    print(k)
else:
    while 1:
        ans += 1
        a = dq.popleft()
        if ans == k:
            print(int(a))
            exit()
        for i in num[max(0,int(a[-1])-1):min(10,int(a[-1])+2)]:
            dq.append(a+i)

Submission status: Accepted

Solution code:
import collections
k = int(input())
li = [str(i) for i in range(1,10)]
st_li = li[:]

q = collections.deque(li)
count = 0
n = 10 ** 10

for i in range(1,n):
    # print(st_li)
    a = q.popleft()
    num = int(a[-1])
    # print(num)
    if num != 0:
        aa = a + str(num-1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    aa = a + str(num)
    st_li.append(aa)
    q.append(aa)
    count += 1
    if num != 9:
        aa = a + str(num+1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    if count > k:
        print(st_li[k-1])
        exit(0)

Submission status: Accepted

Solution code:
K = int(input())

from collections import deque
d = deque([1,2,3,4,5,6,7,8,9])
for i in range(K):
  x = d.popleft()
  if x%10!=0:
    d.append(10*x+x%10-1)
  d.append(10*x+x%10)
  if x%10!=9:
    d.append(10*x+x%10+1)

print(x)

Submission status: Accepted

Solution code:
K = int(input())
if K < 13:
    print(K)
    quit()

now = list(range(1, 10))

count = 9
while True:
    nxt = []
    for l in now:
        tail = l % 10
        for t in range(max(0, tail - 1), min(10, tail + 2)):
            nxt.append(l * 10 + t)
            count += 1
            if count == K:
                print(l * 10 + t)
                quit()
    now = nxt

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

lunlun = deque()

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

for i in range(K - 1):
    x = lunlun[0]
    lunlun.popleft()
    if x % 10 != 0:
        res = 10 * x + x % 10 - 1
        lunlun.append(res)
        
    res = 10 * x + x % 10
    lunlun.append(res)

    if x % 10 != 9:
        res = 10 * x + x % 10 + 1
        lunlun.append(res)
    

print(lunlun[0])

Submission status: Accepted

Solution code:
k = int(input())
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range(k):
    if a[i] % 10 != 0:
        a.append(10*a[i] + a[i] % 10 - 1)
    a.append(10*a[i] + a[i] % 10)
    if a[i] % 10 != 9:
        a.append(10*a[i] + a[i] % 10 + 1)

print(a[k - 1])

Submission status: Accepted

Solution code:
K = int(input())

# キューを作成
import queue
q = queue.Queue()
for i in range(1, 10):
  q.put(i)

# 取り出した要素に対して計算を行う
ans = 0
for i in range(K) :
  x = q.get()
  ans = x

  if (x%10) != 0 :
    q.put(10*x + x%10 - 1)

  q.put(10*x + x%10)

  if (x%10) != 9 :
    q.put(10*x + x%10 + 1)

print(ans)

Submission status: Accepted

Solution code:
import queue
N = int(input())
Q = [i for i in range(1, 10)]
q = queue.Queue()
for i in Q:
  q.put(i)
count = 0
while count < N:
  n = q.get()
  d = n%10
  for i in range(max([d-1, 0]), min([d+2 , 10])):
    q.put(n*10+i)
  count += 1
print(n)

Submission status: Accepted

Solution code:
def make_bigger_digit_runrunnum(srcNum):
    num_list = list()
    one_digit_num = srcNum % 10
    if one_digit_num == 9:
        num_list.append(srcNum*10 + one_digit_num - 1)
    elif one_digit_num == 0:
        num_list.append(srcNum*10 + one_digit_num + 1)
    else:
        num_list.append(srcNum*10 + one_digit_num - 1)
        num_list.append(srcNum*10 + one_digit_num + 1)
    num_list.append(srcNum * 10 + one_digit_num)
    return num_list


k = int(input())
count = 0
pre_num_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
if 0 < k < 10:
    print(k)
else:
    count = 9
    while True:
        new_num_list = []
        for num in pre_num_list:
            new_num_list += make_bigger_digit_runrunnum(num)
        if k <= (len(new_num_list) + count):
            print(sorted(new_num_list)[k-count-1])
            break
        pre_num_list = new_num_list
        count += len(pre_num_list)

Submission status: Accepted

Solution code:
from collections import deque
A = deque(range(1,10))
B = int(input())
for i in range(B):
    C = 0
    C = A.popleft()
    if C % 10 != 0:
        A.append(C * 10 + C%10-1)
    A.append(C * 10 + C%10)
    if C % 10 != 9:
        A.append(C * 10 + C%10+1)
print(C)

Submission status: Accepted

Solution code:
from collections import deque 
k=int(input())
dq=deque()
for i in range(1,10):
    dq.append(i)

cnt=1
while cnt<k:
    now=dq.popleft()
    if now%10>=1:
        dq.append(now*10+now%10-1)
    dq.append(now*10+now%10)
    if now%10<=8:
        dq.append(now*10+now%10+1)
    cnt+=1
print(dq.popleft())

Submission status: Accepted

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

for a in range(1,10):
    que.append(a)
nums = []
while len(nums) <= 1000000:
    if que:
        num = que.popleft()
    nums.append(num)
    for i in range(-1,2):
        plus = (num % 10) + i
        if 0 <= plus < 10:
            new = num*10 + plus
            if new <= 3234566667:
                que.append(new)
            else:
                continue

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

Submission status: Accepted

Solution code:
import queue

k=int(input())

q=queue.Queue()

for i in range(9):
    q.put(i+1)

c=1

for i in range(k):
    c=q.get()
    b=c%10
    if b!=0:
        q.put(10*c+b-1)
    q.put(10*c+b)
    if b!=9:
        q.put(10*c+b+1)

print(c)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k = int(input())

nums = []
def inc(num):
    if num > 3234566667:
        return None
    if num <= 3234566667:
      nums.append(num)

    end = str(num)[-1:]
    end_num = int(end)

    if end_num < 9:
        inc(num * 10 + end_num + 1)

    inc(num * 10 + end_num)

    if end_num > 0:
        inc(num * 10 + end_num - 1)

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

sort_nums = sorted(nums)
print(sorted(nums)[k - 1])

Submission status: Accepted

Solution code:
k = int(input())

nums = []
def inc(num):
    if num > 3234566667:
        return None
    if num <= 3234566667:
      nums.append(num)

    num_str = str(num)
    end = num_str[-1:]
    end_num = int(end)

    if end_num < 9:
        inc(int(num_str + str(end_num + 1)))
   
    inc(int(num_str + end))
    
    if end_num > 0:
        inc(int(num_str + str(end_num - 1)))

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

sort_nums = sorted(nums)
print(sorted(nums)[k - 1])

Submission status: Accepted

Solution code:
#coding:utf-8
import queue

k = int(input())

q = queue.Queue()
ans = 0

for i in [1,2,3,4,5,6,7,8,9]:
    q.put(i)

for i in range(k):
    x = q.get()
    if i == k-1:
        ans = x
        break
    
    if x % 10 != 0:
        q.put(10*x + x%10 - 1)

    q.put(10*x + x%10)
    
    if x % 10 != 9:
        q.put(10*x + x%10 + 1)

print("{}".format(ans))

Submission status: Accepted

Solution code:
k = int(input())

def fun(k):
    lun_luns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    index = 0
    while True:
        if len(lun_luns) >= k:
            break
        num = lun_luns[index]
        mod = num%10
        n = num*10
        if mod == 9:
            lun_luns.extend([n+mod-1, n+mod])
        elif mod == 0:
            lun_luns.extend([n, n+1])
        else:
            lun_luns.extend([n+mod-1, n+mod, n+mod+1])
        index += 1
    
    return lun_luns[k-1]

print(fun(k))

Submission status: Accepted

Solution code:
k = int(input())

lis = []

lis.append(1)
lis.append(2)
lis.append(3)
lis.append(4)
lis.append(5)
lis.append(6)
lis.append(7)
lis.append(8)
lis.append(9)

keta = 1

while len(lis) <= k:
    for j in [i for i in lis if len(str(i)) == keta]:
        if j % 10 == 0:
            lis.append( j * 10 )
            lis.append( j * 10 + 1 )
        elif j % 10 == 9:
            lis.append( j * 10 + 9 )
            lis.append( j * 10 + 8 )
        else:
            last = j % 10
            lis.append( j * 10 + last - 1 )
            lis.append( j * 10 + last )
            lis.append( j * 10 + last + 1 )
    keta += 1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# coding: utf-8
import math
import itertools
import collections

# def debug(arg):
#     if __debug__:
#         pass
#     else:
#         import sys
#         print(arg, file=sys.stderr)

def main():
    K = int(input())
    print(next(itertools.islice(lunlun(), K - 1, None)))

def lunlun():
    q = collections.deque(range(1,10))
    while True:
        x = q.popleft()
        yield x
        r = x % 10
        if r != 0:
            q.append(10 * x + r - 1)
        q.append(10 * x + r)
        if r != 9:
            q.append(10 * x + r + 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
K=int(input())
Q=deque(list(range(1,10)))
for _ in range(K):
  x=Q.popleft()
  if x%10 != 0:
    Q.append(10*x+x%10-1)
  Q.append(10*x+x%10)
  if x%10 != 9:
    Q.append(10*x+x%10+1)
print(x)

Submission status: Accepted

Solution code:
import queue
k=int(input())
q=queue.Queue()
for i in range(1,10):
    q.put(i)
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:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)


def input(): return sys.stdin.readline().rstrip()

K = int(input())
queue = deque(range(1, 10))
for _ in range(K):
    i = queue.popleft()
    if i % 10 >= 1:
        queue.append(i * 10 + (i % 10) - 1)
    queue.append(i * 10 + i % 10)
    if i % 10 <= 8:
        queue.append(i * 10 + (i % 10) + 1)
print(i)

Submission status: Accepted

Solution code:
k = int(input())
ans = 0
import queue

q = queue.Queue()
for i in range(1,10):
    q.put(i)

for i in range(k):
    ans = q.get()
    if ans%10 != 0:
        x = 10*ans + ans%10 - 1
        q.put(x)
    y = 10*ans + ans%10
    q.put(y)
    if ans%10 != 9:
        z = 10*ans + ans%10 + 1
        q.put(z)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
q = deque([1,2,3,4,5,6,7,8,9])
for i in range(k):
  x = q.popleft()
  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:
a = []
 
def dfs(x):
    if x > 3234566667:
        return
    a.append(x)
    for i in range(10):
        if abs(x%10-i) <= 1:
            dfs(x*10+i)

for i in range(1, 10):
  dfs(i)
a = sorted(a)
k = int(input())
print(a[k-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def check(k=10):
    li = {'0':("0","1"), "1":("0","1","2"), "2":("1","2","3"),"3":("2","3","4"),
    "4":("3","4","5"),"5":("4","5","6"),"6":("5","6","7"),"7":("6","7","8"),"8":("7","8","9"),"9":("8","9")}
    if k == 1:
        res = set(['1','2','3','4','5','6','7','8','9'])
    else:
        s = check(k-1)
        res = s.copy()
        for i in s:
            for j in li[i[-1]]:
                res.add(i+j)
    return res

def solve(K: int):
    k = K
    s = list(map(int, check()))
    s = sorted(s)
    print(s[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():
    K = int(input())  # type: int
    solve(K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    MAX = 20
    dp = [[0] * 10 for _ in range(MAX)]
    dp[1] = [1] * 10
    for i in range(2, MAX):
        for j in range(10):
            dp[i][j] = dp[i-1][j]
            if j >= 1:
                dp[i][j] += dp[i-1][j-1]
            if j < 9:
                dp[i][j] += dp[i-1][j+1]
    total = 0
    idx = 0
    for i in range(MAX):
        tmp = sum(dp[i][1:])
        if total + tmp < K:
            total += tmp
            continue
        idx = i
        break
    K -= total
    ans = [""] * idx
    rng = range(1, 10)
    while idx > 0:
        for i in rng:
            if K <= dp[idx][i]:
                ans[idx-1] = str(i)
                rng = range(max(0, i-1), min(9, i+1)+1)
                break
            K -= dp[idx][i]
        idx -= 1
    print("".join(ans[::-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K = int(input())

def block(d, digits, count):
    if d == 1:
        return (digits if count == 1 else None), (count-1)
    s = digits[-1]
    for i in range(max(s-1, 0), min(s+2, 10)):
        answer, count = block(d-1, digits + [i], count)
        if answer:
             return answer, count
    return None, count

def solve():
    if K <= 9:
        return [K]
    count = K - 9
    for d in range(2,10**9):
        for i in range(1,10):
            answer, count = block(d, [i], count)
            if answer:
                return answer

print(''.join(str(d) for d in solve()))

Submission status: Accepted

Solution code:
l=[[1,2,3,4,5,6,7,8,9]]
for i in range(9):
    l.append([])
    for j in l[-2]:
        if j%10==0:
            l[-1].append(j*10)
            l[-1].append(j*10+1)
        elif j%10==9:
            l[-1].append(j*10+8)
            l[-1].append(j*10+9)
        else:
            k=j%10
            l[-1].append(j*10+k-1)
            l[-1].append(j*10+k)
            l[-1].append(j*10+k+1)
ll=[]
for lis in l:
    ll+=lis
ll.sort()
print(ll[int(input())-1])

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
a = deque()
for i in range(1,10):
    a.append(i)
ans = []
for i in range(k):
    x = a.popleft()
    ans.append(x)
    y = x%10
    if y != 0:
        a.append(10*x + y - 1)
    a.append(10*x + y)
    if y != 9:
        a.append(x*10 + y + 1)
print(ans[k-1])

Submission status: Accepted

Solution code:
import queue

q=queue.Queue()
for i in range(1,10):
  q.put(i)

K=int(input())

for k in range(K):
  x=q.get()
  end_one=x%10
  if end_one !=0:
    q.put(10*x+end_one-1)
  q.put(10*x+end_one)
  if end_one !=9:
    q.put(10*x+end_one+1)
print(x)

Submission status: Accepted

Solution code:
N = int(input())
R = list(range(1, 10))
cnt = 0

while True:
    cnt += 1
    p = R[cnt - 1]

    if p % 10 != 0:
        R.append(10 * p + p % 10 - 1)
    R.append(10 * p + p % 10)
    if p % 10 != 9:
        R.append(10 * p + p % 10 + 1)
    if cnt == N:
        break

print(R[cnt - 1])

Submission status: Accepted

Solution code:
import queue

A = queue.Queue()

k = int(input())

if k < 9:
    print(k)

else:
    cou = 9
    for i in range(1, 10):
        A.put(i)

    while(cou < k):
        tmp = A.get()
        if (tmp % 10) == 0:
            cou += 2
            if cou == k:
                print(tmp * 10 + (tmp % 10) + 1)
                break
            elif k == cou - 1:
                print(tmp * 10 + (tmp % 10))
                break
            else:
                A.put(tmp * 10 + (tmp % 10))
                A.put(tmp * 10 + (tmp % 10) + 1)
            

        elif (tmp % 10) == 9:
            cou += 2
            if cou == k:
                print(tmp * 10 + (tmp % 10))
                break
            elif k == cou - 1:
                print(tmp * 10 + (tmp % 10) - 1)
                break
            else:
                A.put(tmp * 10 + (tmp % 10) - 1)
                A.put(tmp * 10 + (tmp % 10))

        else:
            cou += 3
            # print(cou)
            if cou == k:
                print(tmp*10 + (tmp % 10) + 1)
                break
            elif cou - 1 == k :
                print(tmp * 10 + (tmp % 10))
                break
            elif cou - 2 == k:
                print(tmp * 10 + (tmp % 10) - 1)
                break

            else:
                A.put(tmp * 10 + (tmp % 10) - 1)
                A.put(tmp * 10 + (tmp % 10))
                A.put(tmp * 10 + (tmp % 10) + 1)

Submission status: Accepted

Solution code:
import sys
def fin_then_output(i):
  if count==n:
    print(ll[i][-1])
    sys.exit()
    
n=int(input())
if n<10:
  print(n)
  sys.exit()
count=9
ll=[[] for _ in [0]*10]#最大10ケタ
ll[0]=[str(i) for i in range(1,10)] #1~9
for i in range(1,10): #貰う
  for j in range(len(ll[i-1])):#前の行の1つ1つの要素にアクセス。
    #1つ小さいケトを持つルンルン数を小さい順に取り出し、
    #末尾の数字-1,±0,+1した数字を順番に末尾に追加する。
    #-1した数字
    m = int(ll[i-1][j][-1])
    if m!=0:
      ll[i].append(ll[i-1][j]+str(m-1))
      count+=1
      fin_then_output(i)
    ll[i].append(ll[i-1][j]+str(m))
    count+=1
    fin_then_output(i)
    if m!=9:
      ll[i].append(ll[i-1][j]+str(m+1))
      count+=1
      fin_then_output(i)

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
num = ["null"] #数字リスト
for i in range(10):
    num.append(i)
catalog = [i for i in range(10)] #全探索の結果を格納するリスト
q = deque([i for i in range(1, 10)]) #キュー
def bfs(x: str)-> str:
    tmp = []
    ones = int(str(x)[-1]) #最下位桁
    for i in range(3):
        try:
            tmp.append(int(num[ones+i]) + x*10)
        except:
            pass
    return tmp

while len(catalog) <= k:
    node = q.popleft()
    tmp = bfs(node)
    for i in tmp:
        q.append(i)
        catalog.append(i)

print(catalog[k])

Submission status: Accepted

Solution code:
K=int(input())
N=0 #現在のルンルン数の数
lun=list(range(1,10))
while 1:
    N+=1
    x=lun[N-1]
    if x%10 != 0:
        lun.append(10*x+x%10-1)
    lun.append(10*x+x%10)
    if x%10 != 9:
        lun.append(10*x+x%10+1)
    if N==K:
        break
print(lun[N-1])

Submission status: Accepted

Solution code:
import heapq

k = int(input())
l = list(range(1,10))
heapq.heapify(l)
for _ in range(k):
    leftpop = heapq.heappop(l)
    fp = leftpop % 10
    if fp == 0:
        heapq.heappush(l,leftpop * 10)
        heapq.heappush(l,leftpop * 10 + 1)
    elif fp == 9:
        heapq.heappush(l,leftpop * 10 + 9 - 1)
        heapq.heappush(l,leftpop * 10 + 9)
    else:
        heapq.heappush(l,leftpop * 10 + fp - 1)
        heapq.heappush(l,leftpop * 10 + fp)
        heapq.heappush(l,leftpop * 10 + fp + 1)

print(leftpop)

Submission status: Accepted

Solution code:
k = int(input())
 
n = [1, 2, 3, 4, 5, 6, 7, 8, 9]
if k < len(n):
    print(str(n[k-1]))
else:
    count = 9
    while 1:
        x = n.pop(0)
        if x % 10 != 0:
            n.append(10*x + x % 10 - 1)
            count += 1
        n.append(10*x + x % 10)
        count += 1
        if x % 10 != 9:
            n.append(10*x + x % 10 + 1)
            count += 1
        if count >= k:
            print(n[-(count-k)-1])
            break

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
Q = deque([i for i in range(1, min(9, K) + 1)])
ctr = 0

while Q:
    cur = Q.popleft()
    simo = cur % 10
    ctr += 1
    if ctr == K:
        print(cur)
        break
    for dx in [-1, 0, 1]:
        if 0 <= simo + dx <= 9:
            Q.extend([10 * cur + simo + dx])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    # x = 10
    # dp = [[0] * 10 for _ in range(x)]
    # for i in range(0, 10):
    #     dp[0][i] = 1
    # for d in range(1, x):
    #     for i in range(0, 10):
    #         tmp = 0
    #         if i-1 >= 0:
    #             tmp += dp[d-1][i-1]
    #         tmp += dp[d-1][i]
    #         if i+1 <= 9:
    #             tmp += dp[d-1][i+1]
    #         dp[d][i] += tmp
    # print(sum([sum(line[1:]) for line in dp[:x]]))
    """
    この dp で x 桁までの整数で表現される LunLun number の数を sum([line[1:] for line in dp[:x]]) で計算できる
    1 桁まで考えると 9 個
    2 桁まで考えると 35 個
    3 桁まで考えると 110 個
    4 桁まで考えると 327 個
    5 桁まで考えると 956 個
    6 桁まで考えると 2782 個
    7 桁まで考えると 8089 個
    8 桁まで考えると 23527 個
    9 桁まで考えると 68468 個
    10 桁まで考えると 199368 個
    であることがわかる。 k 番目の LunLun number を求める (k = O(10^5)) ので、10 桁の数くらいにはなりうることがわかった。
    ( ˘-з-)ふーん。
    """

    k = ii()
    cnt = 0
    q = deque(list('123456789'))
    while True:
        top = q.popleft()
        cnt += 1
        if cnt == k:
            break
        last_digit = int(top[-1])
        if last_digit - 1 >= 0:
            q.append(top + str(last_digit - 1))
        q.append(top + str(last_digit))
        if last_digit + 1 <= 9:
            q.append(top + str(last_digit + 1))
    print(top)
    """
    Queue を使う！ (解説チラ見 AC)
    """
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

# 次の桁の生成ルール ex. 1 -> 10, 11, 12
def next_num(n):
    if n == 0:
        return [0, 1]
    elif n == 9:
        return [8, 9]
    else:
        return [n-1, n, n+1]

K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # とりあえず 1 桁の Lunlun Number を初期値にとる
heapify(queue)

for _ in range(K-1):
    now = heappop(queue)  # 最小値を取り出す
    # 取り出した値を使って次の桁の値を生成し queue に投げる
    for next_i in next_num(now%10):
        heappush(queue, now*10 + next_i)

print(queue[0])

Submission status: Accepted

Solution code:
K = int(input())
# 1桁
K1 = [x for x in range(1, 10)]
#2桁

def add_2(Kn):
    K_ = []
    for i in Kn:
        
        K_.append(10*i + (i % 10 - 1))
        K_.append(10*i + i % 10)
        if i % 10 < 9:
            K_.append(10*i + (i % 10+ 1))

    return K_

def add_(Kn):
    K_ = []
    for i in Kn:
        if i%10 > 0:
            K_.append(10*i + (i % 10 - 1))
        K_.append(10*i + i % 10)
        if i % 10 < 9:
            K_.append(10*i + (i % 10+ 1))

    return K_

out = [K1, add_2(K1)]
for k in range(1, 9):
    out.append(add_(out[k]))

out = sum(out, [])
print(out[K-1])

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
q = deque([i for i in range(1, 10)])
if k <= 9:
    print(k)
    quit()

k -= 9

while k > 0:
    a = q.popleft()
    b = a % 10
    if b == 0:
        q.append(10*a)
        q.append(10*a + 1)
        k -= 2
    elif b != 0 and b != 9:
        q.append(10*a + b - 1)
        q.append(10*a + b)
        q.append(10*a + b + 1)
        k -= 3
    elif b == 9:
        q.append(10*a + b-1)
        q.append(10*a + b)
        k -= 2

if k == 0:
    print(q[-1])
elif k == -1:
    print(q[-2])
elif k == -2:
    print(q[-3])

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
d = deque(list(range(1, 10)))
for i in range(K - 1):
  a = d[0]
  b = 10 * a + a % 10
  if a % 10 != 0:
    d.append(b - 1)
  d.append(b)
  if a % 10 != 9:
    d.append(b + 1)
  d.popleft()
  
print(d[0])

Submission status: Accepted

Solution code:
K = int(input())
num = list(range(1, 10))
for i in range(K):
  a = num[i]
  b = 10 * a + a % 10
  if a % 10 != 0:
    num.append(b - 1)
  num.append(b)
  if a % 10 != 9:
    num.append(b + 1)
  if len(num) == K:
    break
print(num[K - 1])

Submission status: Accepted

Solution code:
K = int(input())
num = list(range(1, 10))
for i in range(K):
  a = num[i]
  b = 10 * a + a % 10
  if a % 10 != 0:
    num.append(b - 1)
  num.append(b)
  if a % 10 != 9:
    num.append(b + 1)
print(num[K - 1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

queue = deque([])
for i in range(1,9+1):
    queue.append(i)

lunlun = []
for i in range(K):
    x = queue.popleft()
    lunlun.append(x)
    if x%10 != 0:
        queue.append(10*x+x%10-1)
    queue.append(10*x+x%10)
    if x%10!=9:
        queue.append(10*x+x%10+1)
print(lunlun[K-1])

Submission status: Accepted

Solution code:
L=[]
def search(x):
  if x>3234566667:
    return
  L.append(x)
  search(10*x+x%10)
  if x%10!=0:
    search(10*x+x%10-1)
  if x%10!=9:
    search(10*x+x%10+1)
for i in range(1,10):
  search(i)
L.sort()
k=int(input())
print(L[k-1])

Submission status: Accepted

Solution code:
import heapq

K = int(input())
Q=list(range(1,10))
heapq.heapify(Q)
for _ in range(K):
    q = heapq.heappop(Q)
    if q%10!=0:
        heapq.heappush(Q,q*10+(q%10)-1)
    if q%10!=9:
        heapq.heappush(Q,q*10+(q%10)+1)
    heapq.heappush(Q,q*10+(q%10))
print(q)

Submission status: Accepted

Solution code:
k = int(input())

num = [1,2,3,4,5,6,7,8,9]
def lunlun(m):
    for i in range(10):
        if(abs((m%10) - i ) <=1):
            if(m*10+i > 3234566667):
                return
            num.append(m*10+i)
            lunlun(m*10+i)

for j in range(1,10):
    lunlun(j)

num = sorted(num)

print(num[k-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    k=int(input().rstrip())
    lunlun=deque([str(i) for i in range(1,10)])
    for _ in range(k-1):
        now=lunlun.popleft()
        last=now[-1]
        if last!="0":
            lunlun.append(now+str(int(last)-1))
        lunlun.append(now+last)
        if last!="9":
            lunlun.append(now+str(int(last)+1))
        
    print(lunlun[0])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
K = int(input())
li = [1,2,3,4,5,6,7,8,9]
from collections import deque
que = deque()
for i in range(1,10):
    que.append(str(i))
while len(li) < K:
    i = que.popleft()
    i0 = i[-1]
    i1 = int(i0)
    if i0 != '9' and i0 != '0':
        nm = [i1-1,i1,i1+1]
        for j in range(3):
            i2 = i + str(nm[j])
            li.append(int(i2))
            que.append(i2)
    if i0 == '9':
        nm = [8,9]
        for j in range(2):
            i2 = i + str(nm[j])
            li.append(int(i2))
            que.append(i2)
    if i0 == '0':
        nm = [0,1]
        for j in range(2):
            i2 = i+str(nm[j])
            li.append(int(i2))
            que.append(i2)
print(li[K-1])

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

k = inp()
q = deque([i+1 for i in range(9)])
while k > 0:
    now = q.popleft()
    tail = int(str(now)[-1])
    for i in range(-1,2):
        if 0 <= tail + i <= 9:
            q.append(int(str(now) + str(tail+i)))
    k -= 1
print(now)

Submission status: Accepted

Solution code:
K=int(input())
lunlun=[i for i in range(1,10)]#配列を利用

p=0
def generate_lunlun(p):#関数を作る
  last=p%10#最後の１桁がポイント
  if last!=0:#yieldは１回づつ
    yield p*10+last-1
  yield p*10+last
  if last!=9:
    yield p*10+last+1
    
while K>len(lunlun):
  for i in generate_lunlun(lunlun[p]):
    #配列lunlunのp番目を関数に入れる
    lunlun.append(i)
  p+=1#ここでインクリメント
print(lunlun[K-1])#K番目は1-index

Submission status: Accepted

Solution code:
k = int(input())
li = [i + 1 for i in range(9)]

c = 0
while len(li) < k:
    if li[c] % 10 != 0:
        li.append(li[c] * 10 + li[c] % 10 - 1)
    li.append(li[c] * 10 + li[c] % 10)
    if li[c] % 10 != 9:
        li.append(li[c] * 10 + li[c] % 10 + 1)
    c += 1
print(li[k - 1])