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
sys.setrecursionlimit(10**7)
L = []
def lunlun(x, cnt, c):
  if cnt == 10:
    L.append(int(x))
    return
  e = int(x[-1])
  if c:
    for i in range(max(e-1, 0), min(e+2, 10)):
      lunlun(x+str(i), cnt+1, 1)
  else:
    lunlun(x+"0", cnt+1, 0)
    for i in range(1, 10):
      lunlun(x+str(i), cnt+1, 1)
lunlun("0", 1, 0)
for i in range(1, 10):
  lunlun(str(i), 1, 1)

k = int(input())
ans = L[k]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
L = []
def lunlun(x, cnt, c):
  if cnt == 10:
    L.append(int(x))
    return
  e = int(x[-1])
  if c:
    for i in range(max(e-1, 0), min(e+2, 10)):
      lunlun(x+str(i), cnt+1, 1)
  else:
    lunlun(x+"0", cnt+1, 0)
    for i in range(1, 10):
      lunlun(x+str(i), cnt+1, 1)
lunlun("0", 1, 0)
for i in range(1, 10):
  lunlun(str(i), 1, 1)
L.sort()

k = int(input())
ans = L[k]
print(ans)

Submission status: Accepted

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

for _ in range(k-1):
  a = Q.popleft()
  d = a % 10
  if d != 0:
    Q.append(10 * a + d - 1)
  Q.append(10 * a + d)
  if d != 9:
    Q.append(10 * a + d + 1)

print(Q.popleft())

Submission status: Accepted

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

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

    if K <= 9:
        print(K)
        return

    que = [i for i in range(1, 10)]
    cnt = 9

    while True:
        tmp_que = copy.deepcopy(que)
        que = []
        for i in tmp_que:
            a = i%10
            for j in range(a-1, a+2):
                if j < 0 or j > 9:
                    continue
                cnt += 1
                new = i*10+j
                if K == cnt:
                    print(new)
                    return
                que.append(new)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
K = int(input())

import queue

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

count = 0
while True:
    x = q.get()
    count += 1
    if count == K:
        print(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)

Submission status: Accepted

Solution code:
K = int(input())
Q = [i for i in range(1, 10)]
k = 0
for q in Q:
  if k >= K:
    break
  r = q%10
  if r != 0:
    Q.append(q*10 + r - 1)
    k += 1
  Q.append(q*10 + r)
  k += 1
  if r != 9:
    Q.append(q*10 + r + 1)
    k += 1
print(Q[K-1])

Submission status: Accepted

Solution code:
# xをseedとしてどんどんlunlun数を作成する関数. 
# uppe lim = 3234566667
K = int(input())
lunlun_arr = []

#dfs(x)はxを格納して, 次のnodeのdfsを実行する関数.
def dfs(x):
    if x<= 3234566667:
        lunlun_arr.append(x)
        for i in range(10):
            if abs(x%10-i)<=1:
                dfs(10*x + i)
    return lunlun_arr

for seed in range(1,10):
    dfs(seed)

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

Submission status: Accepted

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

def next_lunlun(x):
    K = len(x)
    if len(x) == 1:
        return str(int(x) + 1)
    elif x[-1] == '9':
        next =  next_lunlun(x[:-1])
        if int(next[-1]) - 1 >= 0:
            return next + str(int(next[-1]) - 1)
        else:
            return next + '0'
    elif x[-2] >= x[-1]:
        return x[:-1] + str(int(x[-1]) + 1)
    elif x[-2] < x[-1]:
        next = next_lunlun(x[:-1])
        if int(next[-1]) - 1 >= 0:
            return next + str(int(next[-1]) - 1)
        else:
            return next + '0'


def solve(K: int):
    x = '0'
    for k in range(K):
        x = next_lunlun(x)
    print(x)
    return


# 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:
a = [1,2,3,4,5,6,7,8,9]
i = -1
N = int(input())

while True:
    if  len(a) >= N:
        print(a[N-1])
        break
    i = i + 1
    n = int(str(a[i])[-1])
    x = a[i]*10 + n-1
    y = a[i]*10 + n
    z = a[i]*10 + n+1
    if n != 9 and n != 0:
        w = (x,y,z)
        a.extend(w)
    elif n == 9:
        w = (x,y)
        a.extend(w)
    elif n == 0:
        w = (y,z)
        a.extend(w)

Submission status: Accepted

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

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

    if K <= 9:
        print(K)
        return

    que = [i for i in range(1, 10)]
    cnt = 9

    while True:
        tmp_que = copy.deepcopy(que)
        que = []
        for i in tmp_que:
            a = i%10
            if 0 <= (a-1) <= 9:
                cnt += 1
                new = i*10 + (a-1)
                if K == cnt:
                    print(new)
                    return
                que.append(new)
            if 0 <= a <= 9:
                cnt += 1
                new = i*10 + a
                if K == cnt:
                    print(new)
                    return
                que.append(new)
            if 0 <= (a+1) <= 9:
                cnt += 1
                new = i*10 + (a+1)
                if K == cnt:
                    print(new)
                    return
                que.append(new)



if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-04-06 00:29:17 +0900
# LastModified: 2020-04-06 00:37:37 +0900
#


import os
import sys
from collections import deque

def main():
    K=int(input())
    Q=deque()
    for i in range(1,10):
        Q.append(i)
#    print(Q)
    count=0
    while Q:
        count+=1
        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)
        if count==K:
            print(x)
            return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from functools import lru_cache
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()

def num_digs(n):
	return len(str(n))

@lru_cache(None)
def lunlun(n, pos, tight, prev):
	if pos >= len(n):
		return 1
	md = n[pos] if tight else 9
	sd = 1 if pos == 0 else 0
	count = 0
	for d in range(sd, md + 1):
		new_tight = 1 if tight and d == n[pos] else 0
		if (pos == 0) or (d in {prev - 1, prev, prev + 1}):
			count += lunlun(n, pos  + 1, new_tight, d)
	return count 

def lunlun2(n):
	ans = 0
	for i in range(1, num_digs(n)):
		tupn = tuple(9 for _ in range(i))
		pt = lunlun(tupn, 0, 1, 0)
		ans += pt
	tupn = tuple(int(x) for x in str(n))
	ans += lunlun(tupn, 0, 1, 0)
	return ans	

def main():
	k = int(rl())
	n, jump = 10**19, 10**19
	while jump >= 1:
		while n - jump >= 0 and lunlun2(n - jump) >= k:
			n -= jump
		jump //= 2
	stdout.write(str(n));stdout.write("\n")
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n = int(input())
D = []

def FindOtvet(i, j, otv):
    if i == 0:
        return ''
    if j == 0:
        if (otv + D[i - 1][j]) < n:
            otv += D[i - 1][j]
            return str(j + 1) + FindOtvet(i - 1, j + 1, otv)
        else:
            return str(j) + FindOtvet(i - 1, j, otv)
    elif j == 9:
        if (otv + D[i - 1][j - 1]) < n:
            otv += D[i - 1][j - 1]
            return str(j) + FindOtvet(i - 1, j, otv)
        else:
            return str(j - 1) + FindOtvet(i - 1, j - 1, otv)
    else:
        if (otv + D[i - 1][j - 1]) < n:
            otv += D[i - 1][j - 1]
            if (otv + D[i - 1][j]) < n:
                otv += D[i - 1][j]
                return str(j + 1) + FindOtvet(i - 1, j + 1, otv)
            else:
                return str(j) + FindOtvet(i - 1, j, otv)
        else:
            return str(j - 1) + FindOtvet(i - 1, j - 1, otv)

arr = []
if n < 10:
    print(n)
    exit()
for i in range(10):
    arr.append(1)
D.append(arr)
totalSum = 9
i = 1
respI = 0
respJ = 0
while respI == 0 and respJ == 0:
    arr = []
    for j in range(10):
        if j == 0:
            arr.append(D[i - 1][j] + D[i - 1][j + 1])
        elif j < 9:
            arr.append(D[i - 1][j - 1] + D[i - 1][j] + D[i - 1][j + 1])
        else:
            arr.append(D[i - 1][j - 1] + D[i - 1][j])
        if j > 0:
            if (totalSum + arr[j]) >= n:
                respI = i
                respJ = j
                break
            totalSum += arr[j]
    D.append(arr)
    i += 1
respStr = str(respJ)
print(respStr + FindOtvet(respI, respJ, totalSum))

Submission status: Accepted

Solution code:
K=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)

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

Submission status: Accepted

Solution code:
k = int(input())
a = []


def dfs(x):
    a.append(x)
    if x > 3234566667:
        return
    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)
print(a[k - 1])

Submission status: Accepted

Solution code:
import queue

k = int(input())
li = [1,2,3,4,5,6,7,8,9]
a = queue.Queue()
for l in li:
  a.put(l)

if k <= 9:
  print(li[k-1])
else:
  n = 9
  f=False
  while True:
    x = a.get()
    for i in [-1, 0, 1]:
      if x%10+i==10 or x%10+i==-1:
        continue
      d = (x+i)%10
      t=x*10+d
      a.put(t)
      n+=1
      if n==k:
        print(t)
        f=True
        break
    if f:
      break

Submission status: Accepted

Solution code:
k = int(input())

from collections import deque
d = [-1,0,1]

que = deque()
for i in range(1,10):
    que.append(i)
 
cnt = 0
while que:
    p = que.popleft()
    cnt += 1
    if cnt == k:
        print(p)
        break
    for i in d:
        if 0 <= int(str(p)[-1]) + i <= 9:
            que.append(int(str(p) + str(int(str(p)[-1]) + i)))

Submission status: Accepted

Solution code:
k = int(input())
#print(k)
l = [[0 for i in range(10)] for j in range(10)]

for j in range(10):
	l[0][j] = 1

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

#print(l)
ai = 0
aj = 0
sum = 0
ret = 0
for i in range(10):
	for j in range(1,10):
		sum += l[i][j]
		if(sum >= k):
			ai = i
			aj = j
			sum -= l[i][j]
#			print("ai: ",ai,", aj: ",aj,", sum:",sum) 
			break
	if(ai != 0)or(aj != 0):
		break

ret = aj*(10**ai)
m = aj
for i in range(ai):
	if(ai-1-i < 0):
		break
	if(m != 0):
		sum += l[ai-1-i][m-1]
#		print(sum)
		if(sum >= k):
			sum -= l[ai-1-i][m-1]
			m = m-1
			ret += m*(10**(ai-1-i))
#			print("ai-1-i: ",ai-1-i," m:",m," sum:",sum," ret: ",ret,"!!") 
			continue
	
	sum += l[ai-1-i][m]
	if(sum >= k):
		sum -=l[ai-1-i][m]
		ret += m*(10**(ai-1-i))
#		print("ai-1-i: ",ai-1-i," m:",m," sum:",sum," ret: ",ret,"!") 
		continue
	
	m = m+1
	ret += m*(10**(ai-1-i))
#	print("ai-1-i: ",ai-1-i," m:",m," sum:",sum," ret: ",ret) 

#print("ret:",ret)
print(ret)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
d = deque()
for i in range(1, 10):
    d.append(i)

cnt = 0
while d:
    tmp = d.popleft()
    cnt += 1
    if cnt == K:
        print(tmp)
        break
    r = tmp % 10
    if r != 0:
        d.append(tmp * 10 + r - 1)
    d.append(tmp * 10 + r)
    if r != 9:
        d.append(tmp * 10 + r + 1)

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
q = deque(list(range(1, 10)))
for i 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:
from collections import deque

K = int(input())

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

for _ in range(K-1):
    p = q.popleft()

    if p%10 > 0:
        q.append(p*10 + p%10 - 1)
    
    q.append(p*10 + p%10)

    if p%10 < 9:
        q.append(p*10 + p%10 + 1)

print(q.popleft())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
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())
# ルンルン数の作成
L = [1,2,3,4,5,6,7,8,9]
nL = [1,2,3,4,5,6,7,8,9]
nL2 = []

def D1(a):
    if a == 0:
        return [0,1]
    elif a == 9:
        return [8,9]
    else:
        return [a-1,a,a+1]
        
for _ in range(9):

    for l in nL:
        for l2 in D1(int(str(l)[-1])):
            nL2.append(int(str(l)+str(l2)))
    # print("nL:",nL)
    # print("nL2:",nL2)
    nL = nL2.copy()
    L += nL
    nL2.clear()
    
    # print("nL:",nL)
    # print("nL2:",nL2)
    
    # print(len(L))

print(L[K-1])

Submission status: Accepted

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

nums = [[] for _ in range(11)]
for x in range(1, 10):
    nums[0].append(x)

def push(x, n):
    global nums, cnt
    nums[x].append(n)
    cnt += 1
    if cnt == K:
        print(n)
        sys.exit()
    

if 1 <= K <= 9:
    print(K)
    sys.exit()

cnt = 9
for x in range(1, 11):
    for n in nums[x - 1]:
        if str(n)[-1] == "0":
            push(x, int(str(n) + "0"))
            push(x, int(str(n) + "1"))
        elif str(n)[-1] == "9":
            push(x, int(str(n) + "8"))
            push(x, int(str(n) + "9"))
        else:
            for i in range(-1, 2):
                push(x, int(str(n) + str(int(str(n)[-1]) + i)))

Submission status: Accepted

Solution code:
from collections import deque

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

    lunluns = deque(range(1, 10))

    lunlun = -1

    for _ in range(k):
        lunlun = lunluns.popleft()

        ones_place = lunlun % 10
        if ones_place > 0:
            lunluns.append(lunlun * 10 + ones_place -1)
        lunluns.append(lunlun * 10 + ones_place)
        if ones_place < 9:
            lunluns.append(lunlun * 10 + ones_place + 1)
    return lunlun

print(main())

Submission status: Accepted

Solution code:
from queue import Queue
k = int(input())
q = Queue(maxsize = 10000000)
for i in range(1,10):
    q.put(i)
if(k<10):
    print(k)
else:
    count = 0
    while(count<k-1):
        ele = q.get()
        temp = ele%10
        if(temp-1>=0):
            q.put(int(str(ele)+str(temp-1)))
        q.put(int(str(ele)+str(temp)))
        if(temp+1<=9):
            q.put(int(str(ele)+str(temp+1)))
        count+=1
    print(q.get())

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
q = deque(range(1,10))
n = 0
while n < K:
  n += 1
  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:
from collections import deque
K = int(input())

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

for _ in range(K):
    x = q.popleft()
    xmod = x % 10
    if xmod != 0:
        q.append(10 * x + xmod - 1)
    q.append(10 * x + xmod)
    if xmod != 9:
        q.append(10 * x + xmod + 1)
print(x)

Submission status: Accepted

Solution code:
import sys
# sys.stdin = open('input.txt')

import queue

k = int(input())
q = queue.Queue()

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

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

print(x)

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()
  m = x%10
  if m != 0:
    d.append(10*x+m-1)
  d.append(10*x+m)
  if m != 9:
    d.append(10*x+m+1)
print(x)

Submission status: Accepted

Solution code:
K = int(input())
cand = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
for _ in range(9):
    tmp = []
    for v in cand[-1]:
        if v%10 != 0:
            tmp.append(v*10 + (v%10-1))
        tmp.append(v*10 + (v%10))
        if v%10 != 9:
            tmp.append(v*10 + (v%10+1))
    cand.append(tmp)
ans = []
for i in range(len(cand)):
    for v in cand[i]:
        ans.append(v)
ans = sorted(ans)
print(ans[K-1])

Submission status: Accepted

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

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok

def check(x):
    x = str(x)
    N = len(x)
    dp0 = list2d(N+1, 10, 0)
    dp1 = list2d(N+1, 10, 0)
    a = int(x[0])
    dp0[1][a] = 1
    for j in range(1, a):
        dp1[1][j] = 1
    for i in range(2, N+1):
        for j in range(1, 10):
            dp1[i][j] = 1
    for i, a in enumerate(x):
        a = int(a)
        for j in range(10):
            for k in range(10):
                if abs(j - k) >= 2:
                    continue
                if k > a:
                    dp1[i+1][k] += dp1[i][j]
                elif k == a:
                    dp0[i+1][k] += dp0[i][j]
                    dp1[i+1][k] += dp1[i][j]
                else:
                    dp1[i+1][k] += dp0[i][j]
                    dp1[i+1][k] += dp1[i][j]
    ans = sum(dp0[N]) + sum(dp1[N])
    return ans >= K

K = INT()

res = bisearch_min(0, 10**10, check)
print(res)

Submission status: Accepted

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

mod = 0
for i in range(1,10):
    q.append(i)
for _ in range(K):
    x = q.popleft()
    mod = x % 10
    if mod != 0:
        q.append(x * 10 + mod - 1)
    q.append(x * 10 + mod)
    if mod != 9:
        q.append(x * 10 + mod + 1)
print(x)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    K = int(input())
    l = deque([i for i in range(1,10)])
    for i in range(K):
        t = l.popleft()
        u = t % 10
        if u != 0:
            l.append(t * 10 + u - 1)
        l.append(t*10 + u)
        if u != 9:
            l.append(t*10 + u + 1)
    return t
print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# D - Lunlun Number
# モジュールのインポート
from collections import deque

# 標準入力の取得
K = int(input())

# 求解処理
# 空のQueueを一つ用意し、1, 2, ・・・, 9を順にEnqueue
que = deque(list(range(1, 10)))
lunlun_number = 0
for k in range(K):
    # Queueに対して、Dequeueを行う
    x = que.popleft()
    # x mod 10 ≠ 0なら、10x + (x mod 10) - 1をEnqueue
    if x % 10 != 0:
        que.append(10*x + (x%10) - 1)
    # 10x + (x mod 10)をEnqueue
    que.append(10*x + (x%10))
    # x mod 10 ≠ 9なら、10x + (x mod 10) + 1をEnqueue
    if x % 10 != 9:
        que.append(10*x + (x%10) + 1)

    # 上の操作をK回実施したときの値がLunlun Number
    lunlun_number = x

print(lunlun_number)

Submission status: Accepted

Solution code:
k = int(input())
q = [0]*100003
for i in range(9):
    q[i] = i + 1
c = 9
for i in range(k):
    x = q[i]
    y = x % 10
    if y != 0:
        q[c] = 10 * x + y - 1
        c = c + 1
    q[c] = 10 * x + y
    c = c + 1
    if y != 9:
        q[c] = 10 * x + y + 1
        c = c + 1
    if c > k:
        break
print(q[k - 1])

Submission status: Accepted

Solution code:
def is_count_k(count,n):
    count +=1
    if count == k :
        print(n)
        exit()
    
    return count
def make_tree(G,keta,count):
    num_list = G[keta-2]
    new_list =[]
    for num in num_list:
        r = num%10
        if r != 0 :
            count = is_count_k(count,num*10 + (r-1))
            new_list.append(num*10 + r-1)
        count = is_count_k(count,num*10+r)
        new_list.append(num*10 + r)
        if r != 9:
            count = is_count_k(count,num*10+(r +1))
            new_list.append(num*10+(r +1))
    G.append(new_list)
    make_tree(G,keta+1,count)
k = int(input())
G=[]
if k < 10:
    print(k)
    exit()
G.append([1,2,3,4,5,6,7,8,9])
make_tree(G,2,9)

Submission status: Accepted

Solution code:

import collections


class Solution:
    def solve(self, k):
        lunlunNumbers = [i for i in range(1, 10)]

        for i in range(k-1):
            lunlun = lunlunNumbers[i]

            if lunlun % 10 != 0:
                lunlunNumbers.append(lunlun * 10 + lunlun % 10 - 1)

            lunlunNumbers.append(lunlun * 10 + lunlun % 10)

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

        # print(lunlunNumbers)
        return lunlunNumbers[k-1]


sol = Solution()

k = int(input().strip())
print(sol.solve(k))

Submission status: Accepted

Solution code:
k = int(input())

Lunlun = set()
for a in range(0,10):
    now = a
    Lunlun.add(now)
    for b in range(a-1, a+2):
        if b < 0 or b > 9:
            continue
        now = a +b*10
        Lunlun.add(now)
        for c in range(b-1, b+2):
            if c < 0 or c > 9:
                continue
            now = a +b*10 + c*100
            Lunlun.add(now)
            for d in range(c-1, c+2):
                if d < 0 or d > 9:
                    continue
                now = a +b*10 + c*100 + d*1000
                Lunlun.add(now)
                for e in range(d-1, d+2):
                    if e < 0 or e > 9:
                        continue
                    now = a +b*10 + c*100 + d*1000 + e*10000
                    Lunlun.add(now)
                    for f in range(e-1, e+2):
                        if f < 0 or f > 9:
                            continue
                        now = a +b*10 + c*100 + d*1000 + e*10000 + f*100000
                        Lunlun.add(now)
                        for g in range(f-1, f+2):
                            if g < 0 or g > 9:
                                continue
                            now = a +b*10 + c*100 + d*1000 + e*10000 + f*100000 + g*(10**6)
                            Lunlun.add(now)
                            for h in range(g-1, g+2):
                                if h < 0 or h > 9:
                                    continue
                                now = a +b*10 + c*100 + d*1000 + e*10000 + f*100000 + g*(10**6) + h*(10**7)
                                Lunlun.add(now)
                                for i in range(h-1, h+2):
                                    if i < 0 or i > 9:
                                        continue
                                    now = a +b*10 + c*100 + d*1000 + e*10000 + f*100000 + g*(10**6) + h*(10**7) + i*(10**8)
                                    Lunlun.add(now)
                                    for j in range(i-1, i+2):
                                        if j < 0 or j > 9:
                                            continue
                                        now = a +b*10 + c*100 + d*1000 + e*10000 + f*100000 + g*(10**6) + h*(10**7) + i*(10**8) +j*(10**9)
                                        Lunlun.add(now)


Lunlun = sorted(Lunlun)
# print(len(Lunlun))
ans = Lunlun[k]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input()) 
a = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

for i in range(K-1):
    j = a.popleft()
    if j%10 != 0:
        a.append((10*j) + ((j%10) -1))
        
    a.append((10*j)+j%10)
    
    if j%10 != 9:
        a.append((10*j) +((j%10)+1))
    
print(a.popleft())

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
c = 0
q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
i = 0
while True:
    i = q.popleft()
    c += 1
    if c == k:
        break
    else:
        e = int(str(i)[-1])
        if e == 0:
            q.append(int(str(i)+str(e)))
            q.append(int(str(i)+str(e+1)))
        elif e == 9:
            q.append(int(str(i)+str(e-1)))
            q.append(int(str(i)+str(e)))
        else:
            q.append(int(str(i)+str(e-1)))
            q.append(int(str(i)+str(e)))
            q.append(int(str(i)+str(e+1)))

print(i)

Submission status: Accepted

Solution code:
k=int(input())
num=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]
keta=0
for i in range(0,k):
  for j in range(0,len(num)-1):
    if num[j]==-1:
      num[j]=1
      keta=j
      break
    elif num[j]!=9 and (num[j+1]==-1 or (num[j]-num[j+1])<1):
      num[j]+=1
      break
  for x in range(j-1,-1,-1):
    num[x]=max(0,num[x+1]-1)

for i in range(keta,-1,-1):
  print(num[i],end='')
print()

Submission status: Accepted

Solution code:
k = int(input())

a = []
for i in range(1, 10):
    a.append(i)

while True:
    if k <= len(a):
        print(a[k - 1])
        exit(0)
    else:
        k -= len(a)
    old = a
    a = []
    for x in old:
        d = x % 10
        if d > 0:
            a.append(x * 10 + d - 1)
        a.append(x * 10 + d)
        if d < 9:
            a.append(x * 10 + d + 1)

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-1):
    x = q.get()

    if x%10 == 0:
        q.put(x*10 + 0)
        q.put(x*10 + 1)
    elif x%10 == 9:
        q.put(x*10 + 8)
        q.put(x*10 + 9)
    else:
        q.put(x*10 + x%10-1)
        q.put(x*10 + x%10)
        q.put(x*10 + x%10+1)
    
print(q.get())

Submission status: Accepted

Solution code:
k = int(input())

List = [i for i in range(1, 10)]
latest_added = List.copy()
newly_add = []

count = 9
for _ in range(10000000):
    for i in latest_added:
        mod10 = i % 10
        if mod10 != 0:
            newly_add.append(i * 10 + mod10 - 1)
            count += 1

        newly_add.append(i * 10 + mod10)
        count += 1

        if mod10 != 9:
            newly_add.append(i * 10 + mod10 + 1)
            count += 1


    List += newly_add
    latest_added = newly_add.copy()
    newly_add = []

    if count >= k:
        break

print(List[k - 1])

Submission status: Accepted

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

MOD = 10**9
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors




K = int(input())

r = [1,2,3,4,5,6,7,8,9]
if K < 10:
    print(r[K-1])
    exit()
f = True
index = 10
cnt = 0
start = 0
while f==True:
    r_len = len(r)
    for i in range(start, r_len):
        s = str(r[i])
        migi = len(s)-1
        ix1 = str(int(s[migi])-1)
        ix2 = str(int(s[migi])+1)
        if int(ix1)>=0:
            r.append(int(s+ix1))
        r.append(int(s+s[migi]))
        if int(ix2)<=9:
            r.append(int(s+ix2))
    start = r_len
    if len(r) > 100000:
        f = False

r = sorted(r)
print(r[K-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque
import math
# stdin = open("sample.txt")

K = int(stdin.readline().rstrip())
a = deque(range(1,10))
ans_list = deque()
attack = 100000
while attack > 0:
    ans = a.popleft()
    ue = ans*10
    shimo = ans%10
    ans_list.append(ans)
    if shimo == 0:
        a.append(ue)
        a.append(ue+1)
    elif shimo == 9:
        a.append(ue+shimo-1)
        a.append(ue+shimo)
    else:
        a.append(ue+shimo-1)
        a.append(ue+shimo)
        a.append(ue+shimo+1)
    attack -= 1

print(ans_list[K-1])

Submission status: Accepted

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

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

MAX = 3234566667
ans = []
def rec(x):
    if int(x) > MAX:
        return
    ans.append(int(x))
    last = int(x[-1])
    rec(x+str(last))
    if last != 0:
        rec(x+str(last-1))
    if last != 9:
        rec(x+str(last+1))
    return

K = INT()

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque
import math
# stdin = open("sample.txt")

K = int(stdin.readline().rstrip())
a = deque(range(1,10))
ans_list = []
attack = 100000
while attack > 0:
    ans = a.popleft()
    ue = ans*10
    shimo = ans%10
    ans_list.append(ans)
    if shimo == 0:
        a.append(ue)
        a.append(ue+1)
    elif shimo == 9:
        a.append(ue+shimo-1)
        a.append(ue+shimo)
    else:
        a.append(ue+shimo-1)
        a.append(ue+shimo)
        a.append(ue+shimo+1)
    attack -= 1

print(ans_list[K-1])