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 queue

k = int(input())

q = queue.Queue()
for i in range(1, 10):
  q.put(i)
  
for x in range(k):
  if x == k-1:
    print(q.get())
    exit()
  num = q.get()
  if num%10 != 0:
    q.put(10*num + num%10 - 1)
  q.put(10*num + num%10)
  if num%10 != 9:
    q.put(10*num + num%10 + 1)

Submission status: Accepted

Solution code:
from sys import stdin
import math

lun_list = []

data = stdin.readline().rstrip().split()
K = int(data[0])

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

n_f_idx, n_l_idx = 0, 8

while(1):
    f_idx, l_idx = n_f_idx, n_l_idx
    for idx in range(f_idx, l_idx+1):
        for j in range(10):
            if abs(int(str(lun_list[idx])[-1]) - j) > 1:
                continue
            else:
                num = int(str(lun_list[idx]) + str(j))
                lun_list.append(num)
                n_l_idx += 1
    
    n_f_idx = l_idx + 1

    if len(lun_list) > K:
        print(lun_list[K-1])
        break

Submission status: Accepted

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

Submission status: Accepted

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

sys.setrecursionlimit(10**9)

from functools import lru_cache
@lru_cache(maxsize=None)

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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	K = inputInt()
	counts = 0
	DP = []
	tmp = ["1","2","3","4","5","6","7","8","9"]
	DP.append(tmp)
	ans = [1,2,3,4,5,6,7,8,9]

	for i in range(10):
		tmp = []
		for j_str in DP[i]:
			sita = ""
			ue = ""
			namaka = j_str[-1]

			if j_str[-1] == "0":
				ue = str(int(j_str[-1]) + 1)
			elif j_str[-1] == "9":
				sita = str(int(j_str[-1]) - 1)
			else:
				ue = str(int(j_str[-1]) + 1)
				sita = str(int(j_str[-1]) - 1)

			tmp.append(j_str + namaka)
			ans.append(int(j_str + namaka))

			if sita == "":
				tmp.append(j_str + ue)
				ans.append(int(j_str + ue))
			elif ue == "":
				tmp.append(j_str + sita)
				ans.append(int(j_str + sita))
			else:
				tmp.append(j_str + ue)
				ans.append(int(j_str + ue))
				tmp.append(j_str + sita)
				ans.append(int(j_str + sita))

		DP.append(tmp)

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



#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k = int(input())
lunlun = [0] * 100
lunlun[1] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 1

for _ in range(9):
    n = len(lunlun[i])
    lunlun[i+1] = []
    for x in lunlun[i]:
        r = x%10
        if r > 0:
            lunlun[i+1].append(10*x + r-1)
        lunlun[i+1].append(10*x + r)
        if r < 9:
            lunlun[i+1].append(10*x + r+1)
    i += 1

for i in range(1, 11):
    for j in range(len(lunlun[i])):
        k -= 1
        if k == 0:
            print(lunlun[i][j])
            exit()

Submission status: Accepted

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

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

for j in range(0,k):
  t=q.popleft()
  if t%10 != 0:
    q.append(t*10+t%10-1)
  q.append(t*10+t%10)
  if t%10 != 9:
    q.append(t*10+t%10+1)
print(t)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc161/tasks/abc161_d
from collections import deque

numbers = deque([i for i in range(1, 10)])
K = int(input())
k = 0
ans = 0

while K != k:
    n = numbers.popleft()
    if n % 10 == 0:
        numbers.append(n * 10)
        numbers.append(n * 10 + 1)
    elif n % 10 == 9:
        numbers.append(n * 10 + 8)
        numbers.append(n * 10 + 9)
    else:
        d = n % 10
        numbers.append(n * 10 + d - 1)
        numbers.append(n * 10 + d)
        numbers.append(n * 10 + d + 1)

    k += 1
    ans = n

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

D = deque(['1','2','3','4','5','6','7','8','9'])
if N < 10:
  print(list(D)[N-1])
else:
  cnt = 9
  while cnt < N:
    a = D.popleft()
    for k in range(-1, 2):
      _plus = int(a[-1]) + k
      if not(_plus >= 0 and _plus <= 9):
        continue
      u = a + str(_plus)
      D.append(u)
      cnt +=1
      #print(cnt, u)
      if cnt == N:
        print(u)
        break
    else:
      continue
    break

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7

#N = int(input())
#A = [int(x) for x in input().split()]
#V = [[0] * 100 for _ in range(100)]

K = int(input())

def f(A):
    R = []
    for a in A:
        d = a%10
        if d == 0:
            R.append(a*10)
            R.append(a*10+1)
        elif d == 9:
            R.append(a*10 + 8)
            R.append(a*10 + 9)
        else:
            R.append(a*10 + d - 1)
            R.append(a*10 + d)
            R.append(a*10 + d + 1)
    return R

A = list(range(1,10))
tab = list(A)

while len(tab) < K:
    ret = f(A)
    A = ret
    tab += ret
    # print(tab)

tab = sorted(tab)
# print(tab)

print(tab[K-1])

Submission status: Accepted

Solution code:
K = int(input())


def is_lunlun(i):
    result = -1
    n = [ord(c) - 48 for c in str(i)]
    for j in range(len(n) - 1):
        if abs(n[j] - n[j + 1]) <= 1:
            continue
        if n[j] < n[j + 1]:
            for k in range(j + 1, len(n)):
                n[k] = max(n[k - 1] - 1, 0)
            result = int(''.join(str(k) for k in n))
            result += 10 ** (len(n) - (j + 1))
        else:
            result = int(''.join(str(k) for k in n))
            result += 10 ** (len(n) - (j + 2))
        break
    return result


i = 1
while True:
    # print(i)
    t = is_lunlun(i)
    if t == -1:
        K -= 1
        if K == 0:
            print(i)
            exit()
        i += 1
    else:
        i = t

Submission status: Accepted

Solution code:
import queue

K = int(input())

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

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

print(lunlun)

Submission status: Accepted

Solution code:
#161d
import math
import copy

K = int(input())

keta = 1
lunlun_numbers_list = [1,2,3,4,5,6,7,8,9]
lunlun_numbers_numer = 9

if K <=9:
    print(lunlun_numbers_list[K-1])
else:
    while 1:
        new_lunlun_numbers_list = list()
        for lower_keta in lunlun_numbers_list:
            ketasu = int(math.log10(lower_keta)//1 + 1)

            if lower_keta>=10:
                last_keta = lower_keta - ((lower_keta//10) * 10)
            else:
                last_keta = lower_keta

            #print(lower_keta,ketasu,last_keta)

            if last_keta !=0: 
                new_lunlun_numbers_list.append(lower_keta*10 + last_keta - 1)
            
            new_lunlun_numbers_list.append(lower_keta*10 + last_keta)

            if last_keta !=9:
                new_lunlun_numbers_list.append(lower_keta*10 + last_keta + 1)

        if len(new_lunlun_numbers_list)+lunlun_numbers_numer >= K:
            new_lunlun_numbers_list.sort(reverse=False)
            print(new_lunlun_numbers_list[K-lunlun_numbers_numer-1])
            #print(new_lunlun_numbers_list)
            break
        else:
            lunlun_numbers_numer+=len(new_lunlun_numbers_list)

        lunlun_numbers_list = copy.copy(new_lunlun_numbers_list)

Submission status: Accepted

Solution code:
import queue
q = queue.Queue()

a = int(input())

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

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

Submission status: Accepted

Solution code:
import queue

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

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

for i in range(k):
	output = q.get()
	if output % 10 == 0:
		q.put(output*10)
		q.put(output*10 + 1)
	elif output % 10 == 9:
		q.put(output*10 + 8)
		q.put(output*10 + 9)
	else:
		a = output % 10
		q.put(output*10 + a - 1)
		q.put(output*10 + a )
		q.put(output*10 + a + 1)

print(output)

Submission status: Accepted

Solution code:
a = int(input())

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

for x in range(a):
  tmp = N[x]
  if tmp%10 != 0:
    N.append(tmp*10+tmp%10-1)
  N.append(tmp*10+tmp%10)
  if tmp%10 != 9:
    N.append(tmp*10+tmp%10+1)
print(N[a-1])

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-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(Q.popleft())

Submission status: Accepted

Solution code:
import heapq

K = int(input())

Q = [1,2,3,4,5,6,7,8,9]
heapq.heapify(Q)

for i in range(K-1):
    x = heapq.heappop(Q)
    if x % 10 != 0:
        heapq.heappush(Q,10*x+x%10-1)
    heapq.heappush(Q,10*x+x%10)
    if x % 10 != 9:
        heapq.heappush(Q,10*x+x%10+1)

print(heapq.heappop(Q))

Submission status: Accepted

Solution code:
# coding: utf-8
DATA = """
100000
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

def Calc():
	K = [int(i) for i in get_line().strip().split(" ")][0]
	ret = [str(_) for _ in range(1,10)]
	size = len(ret)
	start = 0
	count = len(ret)
	while(size < K):
		for i in range(start, size):
			v = int(ret[i][-1])
			ll = ret[i]
			if not v == 0:
				count += 1
				ret.append(ll + str(v - 1))
			ret.append(ll + str(v))
			count += 1
			if not v == 9:
				count += 1
				ret.append(ll + str(v+1))

			if count >= K:
				break
		if count >= K:
			break
		start = size
		size = len(ret)
	print (ret[K-1])
Calc()

Submission status: Accepted

Solution code:
K=int(input())

from collections import deque
num=deque()
for i in range(1,10):
  num.append(i)

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

print(l)

Submission status: Accepted

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

import queue
k = int(input())

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())

from collections import deque
d = deque([])
for i in range(1,10):
    d.append(i)
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:
from collections import deque
k = int(input())

que = deque([])
for i in range(1,10):
    que.appendleft(i)


for i in range(k):
    x = que.pop()
    if x % 10 != 0:
        que.appendleft(10*x+(x%10)-1)
    
    que.appendleft(10*x+(x%10))
    
    if x % 10 != 9:
        que.appendleft(10*x+(x%10)+1)

print(x)

Submission status: Accepted

Solution code:
from collections import deque
q=deque([1,2,3,4,5,6,7,8,9])
n=int(input())
def check(k):
  while k<=n:
    a=q.popleft()
    if a%10-1>=0:
      q.append(a*10+a%10-1)
      k=k+1 
      if k==n:
        return a*10+a%10-1
    k=k+1
    q.append(a*10+a%10)
    if k==n:
      return a*10+a%10
    if a%10+1<=9:
      q.append(a*10+a%10+1)
      k=k+1
      if k==n:
        return a*10+a%10+1
if n<=9:
  print(n)
else:
  print(check(9))

Submission status: Accepted

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

            
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k=int(input())
index=0
chk_num=0
keta=0
str_num=""
while index<k:
  chk_num+=1
  str_num=str(chk_num)
  keta=len(str_num)
  index+=1
  if keta!=1:
    for nn_index in range(keta-1,-2,-1):
      if nn_index==-1:
        break
      if str_num[nn_index]!="9":
        break
    num_chr=0
    bk=str(chk_num+1)
    if nn_index==-1:
      bk=""
      for j in range(keta):
        if j==0:
          num_chr=10
        else:
          num_chr=0
        bk+=str(num_chr)
    elif int(str_num[keta-2])+1==int(str_num[keta-1]) or (str_num[keta-2]=="9" and str_num[keta-1]=="9"):
      for asc_index in range(nn_index-1,-2,-1):
        if asc_index==-1:
          break
        if int(str_num[asc_index])+1!=int(str_num[asc_index+1]):
          break
      bk=""
      for j in range(keta):
        if j<asc_index+1:
          num_chr=int(str_num[j])
        elif j==asc_index+1:
          num_chr=int(str_num[j])+1
        else:
          num_chr=num_chr-1 if num_chr-1>0 else 0
        bk+=str(num_chr)
    chk_num=int(bk)-1
print(str_num)

Submission status: Accepted

Solution code:

from collections import deque

K = int(input())

Q = deque()

for i in range(9):
    Q.append(i+1)
cnt = 0

while cnt < K:
    q = Q.popleft()

    if q % 10 != 0:
        Q.append(10*q+(q%10)-1)

    Q.append(10*q+(q%10))

    if q % 10 != 9:
        Q.append(10*q+(q %10)+1)

    cnt += 1

print(q)

Submission status: Accepted

Solution code:
k=int(input())
b=[0]
c=1
c=1
for i in range(k):
    if  b[len(b)-c]+1-b[len(b)-c-1]<=1 and b[len(b)-c]!=9:
        b[len(b)-c]+=1
    elif b==[9]*len(b):
        b=[1]+[0]*len(b)
    else:
        while b[len(b)-c]+1-b[len(b)-c-1]>1 or b[len(b)-c]+1==10:
            c+=1
        b[len(b)-c]+=1
        
        for i in range(c-1):
            if b[len(b)-(c-i)]-1<0:
                b[len(b)-(c-i)+1]=0
            else:
                b[len(b)-(c-i)+1]=b[len(b)-(c-i)]-1
        c=1
    
print(int(''.join(map(str,b))))

Submission status: Accepted

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

if K<10: print(K); exit()

q=deque(list(range(1,10)))
anslist=list(range(1,10))
cnt=9

while cnt<=K:
    a=q.popleft()
    
    # aの1桁目
    a_1=int(str(a)[-1])

    # aの1桁目が0でない場合
    if a_1!=0:
        i=a*10+(a_1-1)
        q.append(i)
        anslist.append(i)
        cnt+=1

    # どのような場合も処理する
    i=a*10+a_1
    q.append(i)
    anslist.append(i)
    cnt+=1

    # aの1桁目が9でない場合
    if a_1!=9:
        i=a*10+(a_1+1)
        q.append(i)
        anslist.append(i)
        cnt+=1

print(anslist[K-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# d 現在の桁
# val 現在の値
# all 格納
def rec(d, val, all):
    # 格納
    all.append(val)
    # 10桁なら終了
    if d == 10:
        return
    # 再帰
    for i in range(-1, 2):
        add = val%10 + i
        if 0 <= add <= 9:
            rec(d+1, val*10+add, all)

# main
K = int(input())
all = []

# 1~9までを格納＆処理
for i in range(1, 10):
    rec(1, i, all)

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

Submission status: Accepted

Solution code:
from collections import deque

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

    q = deque()

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

    count = 0

    a = 0

    while(count < k):

        a = q.popleft()

        if (a%10 != 0):
            q.append(10*a + (a%10) - 1)

        q.append(10*a + (a%10))

        if (a%10 != 9):
            q.append(10*a + (a%10) + 1)

        count += 1

    print(a)

main()

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):
  a = q.popleft()
  if a % 10 == 0:
    q.append(10*a)
    q.append(10*a + 1)
  elif a % 10 == 9:
    q.append(10*a + 8)
    q.append(10*a + 9)
  else:
    q.append(10*a + a%10 - 1)
    q.append(10*a + a%10)
    q.append(10*a + a%10 + 1)
else:
  print(a)

Submission status: Accepted

Solution code:
# coding: utf-8

# 標準入力 <int>
K = int(input())

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

cnt = 9

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

while cnt <= K:
  l = []
  for i in range(len(tmp)):
    if tmp[i] % 10 == 0:
      #print(tmp[i], "a")
      l.append(tmp[i] * 10 + tmp[i] % 10)
      l.append(tmp[i] * 10 + tmp[i] % 10 + 1)
      cnt += 2
    elif tmp[i] % 10 == 9:
      #print(tmp[i], "b")
      l.append(tmp[i] * 10 + tmp[i] % 10 - 1)
      l.append(tmp[i] * 10 + tmp[i] % 10)
      cnt += 2
    else:
      #print(tmp[i], "c")
      l.append(tmp[i] * 10 + tmp[i] % 10 - 1)
      l.append(tmp[i] * 10 + tmp[i] % 10)
      l.append(tmp[i] * 10 + tmp[i] % 10 + 1)
      cnt += 3
  tmp = l
  ind += l

#print(ind)
print(ind[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])
for _ in range(k):
    ans = x = q.popleft()
    x0 = x % 10
    if x0 >= 1:
        q.append(x * 10 + x0 - 1)
    q.append(x * 10 + x0)
    if x0 <= 8:
        q.append(x * 10 + x0 + 1)

print(ans)

Submission status: Accepted

Solution code:
def is_lunlun(s):
    for i in range(len(s) - 1):
        if abs(int(s[i]) - int(s[i+1])) > 1:
            return (i)
    return -1

def minimize(s, j):
    init = int(s[j])
    for i in range(j + 1, len(s)):
        if init == 0:
            s[i] = str(0)
        else:
            init -= 1
            s[i] = str(init)
    return s

k = int(input())
if k <= 10:
    print(k)
else:
    counter = 10
    i = 10
    while counter < k:
        i += 1
        s = list(str(i))
        lunlun_dig = is_lunlun(s)
        while lunlun_dig != -1:
            if int(s[lunlun_dig]) < int(s[lunlun_dig + 1]):
                s[lunlun_dig] = str(int(s[lunlun_dig]) + 1)
            s = minimize(s, lunlun_dig)
            lunlun_dig = is_lunlun(s)
        i = int("".join(s))
        counter += 1
    print(i)

Submission status: Accepted

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

while True:
    #るんるん数の候補を、桁数ごとに積み上げます。まず１桁
    if k<=len(a):
        print(a[k-1])
        break
    """
    1桁に成果がなければ、kから１桁のlen(るんるん数リスト)を引いて、
    ２桁のリストを作ります。作り方は、元のるんるんリストのそれぞれの数を１０倍して、
    その１０の位と同じか隣接する値を加えたものをappend.
    以下同様
    """
    k-=len(a)
    old=[]
    old, a=a, old
    for x in old:
        for i in range(-1,2):
            d=x%10+i
            if d<0 or d>9:
                continue
            new_x=x*10+d
            a.append(new_x)

Submission status: Accepted

Solution code:
k = int(input())
a = [x for x in range(1, 10)]

while(1):
    if(k <= len(a)):
        print(a[k-1])
        break
    k -= len(a)
    old = []
    old, a = a, old
    for x in old:
        for i in range(-1, 2):
            d = x % 10+ i
            if(d < 0 or d > 9):
                continue
            nx = x*10 + d
            a.append(nx)

Submission status: Accepted

Solution code:
K = int(input())
#N, K = list(map(int, input().split()))

res = 0

def runrun(keta, flag, before, res) :
  if(flag) :
    if(keta == 0) :
      res += 1
      if(res == K) :
        print("".join(map(str, before)))
        exit()
      return res
    for i in range(before[-1]-1, before[-1]+2) :
      if((i < 0) or (i > 9)) :
        continue
      else :
        res = runrun(keta-1, flag, before+[i], res)
    return res
  else :
    if(keta <= 0) :
      return res

    res = runrun(keta-1, flag, before, res)
    for i in range(1, 10) :
      res = runrun(keta-1, True, before+[i], res)
    return res
      
      
runrun(10, False, [], res)

Submission status: Accepted

Solution code:
k = int(input())
from collections import deque
que = deque()
for i in range(1,10):
    que.append(i)
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)
    if i == k-1:
        print(x)

Submission status: Accepted

Solution code:
K=int(input())
S=[1]
while 1:
    #print(S,K)
    flag=0
    idxflag=0
    for i in range(len(S)-1):
        if not S[i] in [S[i+1]+1,S[i+1],S[i+1]-1]:
            flag=1
            break
    if flag:
        S[i]+=1

        for m in range(i+1,len(S)):
            S[m]=max(S[m-1]-1,0)
    else:
        K-=1
        if K==0:
            break
        S[-1]+=1


    for i in range(1,len(S))[::-1]:
        if S[i]==10:
            idx=i
            idxflag=1
            S[i]=0
            S[i-1]+=1
            #S[i]=max(S[i-1]-1,0)
    if idxflag:
        for i in range(idx,len(S)):
            S[i]=max(S[i-1]-1,0)


    if S[0]==10:
        S=[0 for i in range(len(S)+1)]
        S[0]=1
print(int("".join([str(i) for i in S])))

Submission status: Accepted

Solution code:
import collections
m = int(input())
n = 1000000000
ans = []
listnum = [
            [0, 1],
            [0, 1, 2],
            [1, 2, 3],
            [2, 3, 4],
            [3, 4, 5],
            [4, 5, 6],
            [5, 6, 7],
            [6, 7, 8],
            [7, 8, 9],
            [8, 9]
           ]
def dfs(s):
    if len(str(n)) + 1 > len(s):
        ans.append(int(s))
        lastnum = str(s)[-1]
        for i in listnum[int(lastnum)]:
            dfs(s + str(i))
for i in range(1, 10):
    dfs(str(i))
ans = sorted(ans)
print(ans[m - 1])

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    K=int(readline())

    que=deque(["0"])
    res=[]
    count=0
    while count<K:
        n=que.popleft()
        if n=="0":
            for i in range(1,10):
                i=str(i)
                que.append(i)
                res.append(i)
                count+=1
        else:
            if n[-1]=="0":
                nex=["0","1"]
            elif n[-1]=="9":
                nex=["8","9"]
            else:
                m=int(n[-1])
                nex=[str(m-1),n[-1],str(m+1)]
            for l in nex:
                k=n+l
                que.append(k)
                res.append(k)
                count+=1

    print(res[K-1])
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
ll = set()

def search(s):
    ll.add(int(s))
    if len(s) == 10:
        return
    
    if int(s[-1]) == 0:
        search(s+"1")
    elif int(s[-1]) == 9:
        search(s+"8")
    else:
        search(s+str(int(s[-1])+1))
        search(s+str(int(s[-1])-1))
    search(s+s[-1])
    
for i in range(1, 10):
    search(str(i))

ll = list(sorted(ll))

print(ll[int(input())-1])

Submission status: Accepted

Solution code:
K = int(input())

if K < 10:
  queue = range(1,K+1)
  count = K
else:
  count = 9
  queue = [1,2,3,4,5,6,7,8,9]

while count != K:
  for x in queue:
    if x%10 != 0:
      queue.append(10*x + (x%10) - 1)
      count += 1
      if count == K:
        break

    queue.append(10*x + (x%10))
    count += 1
    if count == K:
      break

    if x%10 != 9:
      queue.append(10*x + (x%10) + 1)
      count += 1
      if count == K:
        break

print(queue[-1])

Submission status: Accepted

Solution code:
from collections import deque


def solve():
    N = int(input())
    q = deque([1,2,3,4,5,6,7,8,9])
    cnt = 0
    l = []

    while cnt<N:
        p = q.popleft()
        l.append(p)
        cnt += 1
        for i in range(max((p%10)-1,0), min((p%10)+1, 9)+1):
            q.append(10*p+i)

    print(l[N-1])


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque


def solve():
    N = int(input())
    q = deque([1,2,3,4,5,6,7,8,9])
    cnt = 0
    l = []
    used = set()

    while cnt<N:
        p = q.popleft()
        if p in used:continue
        used.add(p)
        l.append(p)
        cnt += 1
        for i in range(max((p%10)-1,0), min((p%10)+1, 9)+1):
            q.append(10*p+i)

    print(l[N-1])


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque

q = deque([1,2,3,4,5,6,7,8,9])
cnt = 0
l = []
used = set()

while cnt<100000:
    p = q.popleft()
    if p in used:continue
    used.add(p)
    l.append(p)
    cnt += 1
    for i in range(max((p%10)-1,0), min((p%10)+1, 9)+1):
        q.append(10*p+i)

N = int(input())
print(l[N-1])

Submission status: Accepted

Solution code:
b=[[] for i in range(10)]
b[0]=[1,2,3,4,5,6,7,8,9]
for j in range(9):  
    for k in b[j]:
        b[j+1].append(int(str(k)+str(k)[-1]))
        if str(k)[-1]!="9":b[j+1].append(int(str(k)+str(int(str(k)[-1])+1)))
        if str(k)[-1]!="0":b[j+1].append(int(str(k)+str(int(str(k)[-1])-1)))            
    b[j+1]=list(set(b[j+1]))
c=[]
for j in range(10): c=c+b[j]
c=sorted(c)
print(c[int(input())-1])

Submission status: Accepted

Solution code:
from collections import deque

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

n = int(input())

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