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 LunLun(k, count, base):
    nx = []
    n = len(base)
    if count + n >= k:
        ans = base[k - count - 1]
        return ans

    for x in base:
        count += 1
        p = x % 10
        x *= 10
        a = x + p - 1
        b = a + 1
        c = b + 1
        n = 3
        if p == 0:
            n -= 1
            nx.extend([b, c])
        elif p == 9:
            n -= 1
            nx.extend([a, b])
        else:
            nx.extend([a, b, c])

    return LunLun(k, count, nx)


def main():
    k = int(input())
    base = range(1, 10)
    ans = LunLun(k, 0, base)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def LunLun(k, count, base):
    nx = []
    n = len(base)
    if count + n >= k:
        print(base[k - count - 1])
        return
    for x in base:
        count += 1
        p = x % 10
        x *= 10
        a = x + p - 1
        b = a + 1
        c = b + 1
        n = 3
        if p == 0:
            n -= 1
            nx.extend([b, c])
        elif p == 9:
            n -= 1
            nx.extend([a, b])
        else:
            nx.extend([a, b, c])

    LunLun(k, count, nx)


def main():
    k = int(input())
    base = range(1, 10)
    LunLun(k, 0, base)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    k = int(input())
    ans = 0
    que = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
    x = 0
    for _ in range(k):
        x = que.popleft()

        p = x % 10
        e = 10 * x
        if p != 0:
            a = e + p - 1
            que.append(a)
        b = e + p
        que.append(b)
        if p != 9:
            c = e + p + 1
            que.append(c)
    print(x)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(K):
    count = 9
    queue = deque("123456789")
    while queue:
        num = queue.popleft()
        d1 = int(num[-1])
        # e.g.) 123 --> 1232
        if d1 - 1 >= 0:
            count += 1
            next_num = "".join([num, str(d1 - 1)])
            if count == K:
                return int(next_num)
            else:
                queue.append(next_num)
        # e.g.) 123 --> 1233
        count += 1
        next_num = "".join([num, str(d1)])
        if count == K:
            return int(next_num)
        else:
            queue.append(next_num)
        # e.g.) 123 --> 1234
        if d1 + 1 <= 9:
            count += 1
            next_num = "".join([num, str(d1 + 1)])
            if count == K:
                return int(next_num)
            else:
                queue.append(next_num)


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

    if K <= 9:
        ans = K
    else:
        ans = bfs(K)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

k = int(input())
l = 10
A = [str(i+1) for i in range(9)]
B = ["0"] + A
ans = []
#print(l)

def dfs(num,l):
    if len(num) >= l:
        ans.append(int(num))
    else:
        ans.append(int(num))
        for i in B:
            if abs(int(num[-1])-int(i)) < 2:
                dfs(num + i,l)
if k <= 9:
    print(k)
else:
    for i in A:
        dfs(i,l)
    ans = sorted(ans)
    #print(ans)
    print(ans[k-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque


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


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    K = int(input())
    q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
    for i in range(K):
        d = q.popleft()
        a = d % 10
        if a == 0:
            q.append(d * 10)
            q.append(d * 10 + 1)
        elif a == 9:
            q.append(d * 10 + a - 1)
            q.append(d * 10 + a)
        else:
            q.append(d * 10 + a - 1)
            q.append(d * 10 + a)
            q.append(d * 10 + a + 1)
    print(d)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def bfs(K):
    number = list(range(10))
    q = deque(list(range(1, 10)))

    cnt = 0
    while cnt < K:
        i = q.popleft()
        cnt += 1
        if cnt == K:
            return i

        last = int(str(i)[-1])
        for n in number:
            if abs(last - n) <= 1:
                next = str(i) + str(n)
                next = int(next)
                q.append(next)


def main():
    K = int(input())
    ans = bfs(K)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k=int(input())

dp=[[] for i in range(10**4)]

if k<=9:
    print(k)
    exit()

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

n=9
i=1
while n<k:
    for mo in dp[i]:
        simo=int(mo[-1])
        rr=[str(simo-1),str(simo),str(simo+1)]
        for r in rr:
            if 0<=int(r)<=9:
                n+=1
                gen=mo+r
                dp[i+1].append(gen)
                if n==k:
                    ans=gen
                    print(ans)
                    exit()
    i+=1

Submission status: Accepted

Solution code:
from collections import deque

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

count = 0
while True:
    n = que.popleft()
    count += 1
    if count == K:
        print(n)
        exit()
    if 1 <= n%10 <= 8: 
        que.append(n*10 + n%10 - 1)
        que.append(n*10 + n%10)
        que.append(n*10 + n%10 + 1)
    elif n%10 == 0:
        que.append(n*10 + n%10)
        que.append(n*10 + n%10 + 1)
    else:
        que.append(n*10 + n%10 - 1)
        que.append(n*10 + n%10)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
K = int(input())

ans_list = []

def dfs(l):
    if len(l)==1 and l[0]!="0":
        ans_list.append(int("".join(l)))
    if l!=[] and l[0]=="0":
        return
    if l!=[] and int("".join(l))>3234566667:
        return
    for i in ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]:
        l.append(i)
        #ここで絶対値1以下になるものだけdfs
        if len(l)==1:
            dfs(l)
            l.pop()
        elif abs(int(l[len(l)-2])-int(l[len(l)-1]))<=1:
            dfs(l)
            ans_list.append(int("".join(l)))
            l.pop()
        else:
            l.pop()

    return

dfs([])
ans_list.sort()
print(ans_list[K-1])

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    k = ni()

    que = queue.Queue()

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

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

    cnt = 9
    flg = True
    while flg:
        tmp = que.get()
        grade1 = tmp % 10

        for i in (-1, 0, 1):
            if -1 < grade1 + i < 10:
                que.put(tmp * 10 + grade1 + i)
                cnt += 1
                if cnt == k:
                    print(tmp * 10 + grade1 + i)
                    exit(0)


if __name__ == '__main__':
    main()

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

print(x)

Submission status: Accepted

Solution code:
# ABC161D

def f(k):
    if 1 <= k <= 9:
        print(k)
    else:
        nxt = [[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]]
        cum_npi = [0, 9, 35, 110, 327, 956, 2782, 8089, 23527, 68468, 199368]
        for length, begin in enumerate(cum_npi):
            if k < begin:
                found = cum_npi[length - 1]
                break
        begin = 10 ** (length - 1)
        # length, begin, found
        k -= found
        x = [[]] * (length + 1)
        x[1] = list(range(1, 10))
        # x

        terminate = False
        i = 1
        while True:
            #print(f"a) i = {i}  x = {x}")
            if len(x[i]): # len(x[i])
                digit = x[i][0]
                if i < length: # i, length
                    i += 1
                    x[i] = nxt[digit].copy()
                    #print(f"x) digit = {digit}  nxt[digit] = {nxt[digit]}  i = {i}  x[i] = {x[i]}")
                    #print(f"b) i = {i}  x = {x}")
                    if i == length: # i, length
                        while len(x[i]): # i, x[i]
                            k -= 1
                            #print(f"c) i = {i}  x = {x}, k = {k}")
                            if k == 0:
                                x.pop(0)
                                #print("answer =", x)
                                ans = "".join([str(j.pop(0)) for j in x])
                                print(ans)
                                terminate = True
                                break
                            else:
                                x[i].pop(0)
                            #print(f"d) i = {i}  x = {x}")
                        else:
                            #print(f"e) i = {i}  x = {x}")
                            while len(x[i]) == 0:
                                i -= 1
                                x[i].pop(0)
                        if terminate:
                            break

f(int(input()))

Submission status: Accepted

Solution code:
from itertools import product


def solve(string):
    k = int(string)
    if k < 10:
        return str(k)

    t = [[0] * 12 for _ in range(10)]
    t[0] = [0] + [1] * 10 + [0]
    ac = 9
    for i, j in product(range(1, 10), range(1, 11)):
        t[i][j] = t[i - 1][j - 1] + t[i - 1][j] + t[i - 1][j + 1]
        ac += t[i][j] if j > 1 else 0
        if ac >= k:
            k -= ac - t[i][j]
            break
    ans = str(j - 1)
    while i > 0:
        i -= 1
        j -= 1
        tmp = t[i][j]
        while tmp < k:
            j += 1
            tmp += t[i][j]
        k -= tmp - t[i][j]
        ans += str(j - 1)
    return ans


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def main():
    K = int(readline())
    dq = []
    for i in range(1, 10):
        dq.append(i)
    for i in range(K):
        v = dq[i]
        r = v%10
        if r == 9:
            dq.append(v*10+8)
            dq.append(v*10+9)
        elif r == 0:
            dq.append(v*10)
            dq.append(v*10+1)
        else:
            dq.append(v*10+(r-1))
            dq.append(v*10+r)
            dq.append(v*10+(r+1))
    print(dq[K-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

    counter = 9

    if k <= 9:
        print(k)
        exit()

    temp = [0]*2

    while True:
        x = que.popleft()
        for j in [-1,0,1]:
            if x[0]+j < 0 or x[0]+j >= 10:
                continue
            temp[0] = x[0] + j
            temp[1] = x[1]*10 + x[0] + j
            counter += 1
            if counter == k:
                print(temp[1])
                exit()
            que.append(temp)
            temp = [0] * 2
                



k = int(input())
dfs()
#幅優先探索で良いとのこと

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    """
    X is ルンルン数 ⇔ Xを10進数表記したとき、隣り合うどの2つの桁の値についても、差の絶対値が1以下
    """
    K = int(input())
    
    # table[0] = [0]
    # table[1] = [1,...,9]
    #            0, 1, 1, 1, 1, 1, 1, 1, 1, 1
    # table[2]   1, 2, 3, 3, 3, 3, 3, 3, 3, 2
    # table[3]   3, 6, 8, 9, 9, 9, 9, 9, 8, 5
    table = [list(range(1, 10))]
    table_size_prev = 0
    table_size = len(table[-1])
    while table_size < K:
        table.append([])
        # 以前の数字に末尾を追加していく
        for num in table[-2]:
            base_num = num * 10
            digit1 = num % 10
            if digit1 == 0:
                table[-1] += [base_num, base_num+1]
            elif digit1 == 9:
                table[-1] += [base_num+8, base_num+9]
            else:
                table[-1] += [base_num+digit1-1, base_num+digit1, base_num+digit1+1]
        
        table_size_prev = table_size
        table_size += len(table[-1])
    
    print(table[-1][K-table_size_prev-1])

Submission status: Accepted

Solution code:
k = int(input())
queue = [1,2,3,4,5,6,7,8,9]
cnt = 0
ans = 0
while(True):
    n = queue.pop(0)
    cnt+=1
    last = n%10
    if(0<=(last-1)):
        queue.append(10*n+(last-1))
    queue.append(10*n+last)
    if((last+1)<10):
        queue.append(10*n+last+1)

    if(k==cnt):
        ans = n
        break

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    K = int(input())

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

    cnt = 0
    
    while cnt < K:
        cnt += 1
        temp = que.popleft()

        push1 = temp*10 + temp%10 - 1
        push2 = temp*10 + temp%10
        push3 = temp*10 + temp%10 + 1

        if temp%10 != 0:
            que.append(push1)
        
        que.append(push2)

        if temp%10 != 9:
            que.append(push3)
        
    print(temp)



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def make_lun(lun):
  temp_lun=[]
  i=0
  while(i<len(lun)):
    if(lun[i][0]=="0"):
      temp_lun.append("1"+lun[i])
    elif(lun[i][0]=="1"):
      temp_lun.append("1"+lun[i])
      temp_lun.append("2"+lun[i])
    elif(lun[i][0]=="9"):
      temp_lun.append("9"+lun[i])
      temp_lun.append("8"+lun[i])
    else:
      temp_lun.append(str(int(lun[i][0])+1)+lun[i])
      temp_lun.append(str(int(lun[i][0]))+lun[i])
      temp_lun.append(str(int(lun[i][0])-1)+lun[i])

    if(lun[i][-1]=="0"):
      temp_lun.append(lun[i]+"0")
      temp_lun.append(lun[i]+"1")
    elif(lun[i][-1]=="9"):
      temp_lun.append(lun[i]+"9")
      temp_lun.append(lun[i]+"8")
    else:
      temp_lun.append(lun[i]+str(int(lun[i][-1])+1))
      temp_lun.append(lun[i]+str(int(lun[i][-1])))
      temp_lun.append(lun[i]+str(int(lun[i][-1])-1))
    i+=1
  temp2_lun=list(set(temp_lun))
  temp3_lun=temp2_lun.sort()
  return temp2_lun

K=int(input())

lun=[str(n) for n in range(1,10)]
while(len(lun)<K):
  K-=len(lun)
  lun=make_lun(lun)
ans = lun[K-1]
print(ans)

Submission status: Accepted

Solution code:
k = int(input())

ans = []

def dfs(d, val):
    ans.append(val)

    if(d==10): return

    for i in range(-1, 2):
        add = (val%10) + i
        if 0 <= add <= 9:
            dfs(d+1, val*10+add)

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

ans.sort()

print(ans[k-1])

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    # ルンルン数
    # 1,2,3,4,5,6,7,8,9,(9通り)
    # => 1ケタ:9通り
    # 10,11,12,(3)
    # 21,22,23,(3)
    # ...
    # 87,88,89,(3)
    # 98,99,(2)
    # => 2ケタ:3*9-1=26通り

    lun = [1,2,3,4,5,6,7,8,9]
    tmp = lun
    count = 9
    while count<K:
        add = []
        for l in tmp:
            k = l%10
            a = l*10+k
            if k==0:
                add.extend([a,a+1])
            elif k==9:
                add.extend([a-1,a])
            else:
                add.extend([a-1,a,a+1])
        count += len(add)
        tmp = add
        lun.extend(add)
    print(lun[K-1])

main()

Submission status: Accepted

Solution code:
ln_l = [1,2,3,4,5,6,7,8,9]

def dps(curr_num):
    end_num = curr_num[-1]
    for i in [-1,0,1]:
        added_num = int(end_num) + i
        if added_num == -1 or added_num == 10:
            continue
        curr_num_plus = curr_num + str(added_num)
        ln_l.append(int(curr_num_plus))
        if len(curr_num_plus) < 10:
            dps(curr_num_plus)

def main():
    k = int(input())
    for i in range(1,9+1):
        dps(str(i))
    ln_l.sort()
    print(ln_l[k-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
q = deque([i for i in range(1, 10)])

cnt = 0
while cnt < K-1:
    n = q.popleft()
    d = int(str(n)[-1])
    cnt += 1
    for i in [d-1, d, d+1]:
        if i < 0 or 10 <= i:
            continue
        q.append(10*n+i)
print(q.popleft())

Submission status: Accepted

Solution code:
k = int(input())

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

for _ in range(9):
    tmp = []
    for val in cand[-1]:
        if val % 10 != 0:
            tmp.append(val * 10 + (val%10 -1))
        tmp.append(val * 10 + (val % 10 ))
        if val % 10 != 9:
            tmp.append(val * 10 + (val % 10 + 1))
    cand.append(tmp)
ans = []
for i in range(len(cand)):
    for val in cand[i]:
        ans.append(val)
ans=sorted(ans)
print(ans[k-1])

Submission status: Accepted

Solution code:
k=int(input())
x=set()
for i in range(1,10):
	x.add(i)

while len(x)<=10**5:
	y=list(x)
	for i in y:
		j=int(str(i)[-1])
		l=i*10+(j-1)
		m=i*10+j
		r=i*10+(j+1)
		x.add(m)
		if j!=0:
			x.add(l)
		if j!=9:
			x.add(r)

y=sorted(list(x))

print(y[k-1])

Submission status: Accepted

Solution code:
k=int(input())
# 最大のk=100000
# ->3234566667
import sys
sys.setrecursionlimit(10**7)
def dfs(s):# 先頭がsのルンルンナンバーを返す。s自体もルンルンナンバー
    if len(str(s))==10:
        return[s]
    ret=[s]
    si=str(s)[-1]
    if si=='9':
        ret+=dfs(10*s+8)
        ret+=dfs(10*s+9)
        return ret
    elif si=='0':
        ret+=dfs(10*s)
        ret+=dfs(10*s+1)
        return ret
    else:
        ret+=dfs(10*s+s%10-1)
        ret+=dfs(10*s+s%10)
        ret+=dfs(10*s+s%10+1)
        return ret
lunlun=dfs(1)+dfs(2)+dfs(3)+dfs(4)+dfs(5)+dfs(6)+dfs(7)+dfs(8)+dfs(9)
lunlun.sort()
print(lunlun[k-1])

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])  # K 回目に取り出す最小値

Submission status: Accepted

Solution code:
def generator(n):
    if n == 1:
        for i in range(1, 10):
            yield i
    else:
        for a in generator(n - 1):
            for i in range(10):
                if abs(i - (a % 10)) <= 1:
                    yield 10 * a + i


k = int(input())
A = []
for i in range(1, 11):
    for a in generator(i):
        A.append(a)
print(A[k - 1])

Submission status: Accepted

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

if k <= 9:
  print(k)
  exit()

que = deque([1,2,3,4,5,6,7,8,9])
cnt = len(que)
while cnt < k:
  x = que.popleft()
  m = x%10
  if m != 0:
    que.append(10*x+m-1)
    cnt+=1
    if cnt == k: print(que.pop()); exit();
  que.append(10*x+m)
  cnt+=1
  if cnt == k: print(que.pop()); exit();
  if m != 9:
    que.append(10*x+m+1)
    cnt+=1
    if cnt == k: print(que.pop()); exit();

Submission status: Accepted

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

for i in range(1,k):
  num = arr[i]
  val = num*10 + num%10
  if val%10 != 0: arr.append(val - 1) #繰り下がりを回避
  arr.append(val)
  if val%10 != 9: arr.append(val + 1) #繰り上がりを回避

ans = arr[k]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
 
K = int(input())
que = deque(range(1, 10))
 
for _ in range(K - 1):
    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(que.popleft())

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    k=int(input())
    que=deque([1,2,3,4,5,6,7,8,9])
    for _ in range(k-1):
        q=que.popleft()
        if q%10>0:que.append(10*q+q%10-1)
        que.append(10*q+q%10)
        if q%10<9:que.append(10*q+q%10+1)
    print(que[0])


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
que = deque(list(range(1, 10)))
for i in range(K):
    x = que.popleft()
    last = x % 10
    if last != 0:
        que.append(x*10 + last-1)
    que.append(x*10 + last)
    if last != 9:
        que.append(x*10 + last+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)
count=0
while count<k:
    a=q.get()
    #print(a)
    if a%10==0:
        x=a%10
        q.put(10*(a)+x)
        q.put(10*a+x+1)
    elif a%10==9:
        x=a%10
        q.put(10*a+x-1)
        q.put(10*a+x)
    else:
        x=a%10
        q.put(10*a+x-1)
        q.put(10*(a)+x)
        q.put(10*a+x+1)
    count+=1
print(a)

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
num_li = deque()
for i in range(1,10):
    num_li.append(i)
while True:
    l = len(num_li)
    if l >= k:
        print(num_li[k-1]);exit()
    else:
        k -= l
        for i in range(l):
            left = num_li.popleft()
            last = left%10
            add1,add2,add3 = 10*left+last-1,10*left+last,10*left+last+1
            if 0 < last < 9:
                num_li.append(add1)
                num_li.append(add2)
                num_li.append(add3)
            elif last == 0:
                num_li.append(add2)
                num_li.append(add3)
            else:
                num_li.append(add1)
                num_li.append(add2)

Submission status: Accepted

Solution code:
k=int(input())
cand=[[1,2,3,4,5,6,7,8,9]]
for _ in range(9): #上記の操作を9回繰り返せば10^5個以上のルンルン数を列挙できる
 tmp=[]
 for val in cand[-1]:
   if val%10!=0: #末尾が0のときは(末尾-1)を付け加えた数はルンルン数にならない
     tmp.append(val*10+(val%10-1))
   tmp.append(val*10+(val%10))
   if val%10!=9: #末尾が9のときは(末尾+1)を付け加えた数はルンルン数にならない
     tmp.append(val*10+(val%10+1))
 cand.append(tmp)
ans=[]
for i in range(len(cand)):
 for val in cand[i]:
   ans.append(val)
ans=sorted(ans)
print(ans[k-1])

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

readline = stdin.buffer.readline

INF = 10 ** 10

K = int(readline())

results = []

def dfs(A):
    if len(A) > 10:
        return

    if A:
        results.append(int("".join(A)))

    if len(A) >= 1:
        n = int(A[-1])
        for i in [str(n-1), str(n), str(n+1)]:
            if int(i) < 0 or int(i) > 9:
                continue
            A.append(i)
            dfs(A)
            A.pop()
    else:
        for i in range(1, 10):
            A.append(str(i))
            dfs(A)
            A.pop()
            

dfs([])

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

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
que = deque(range(1, 10))

for _ in range(K - 1):
    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(que.popleft())

Submission status: Accepted

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

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

tmp=9

while tmp<K:
    a=q.get()
    d=a%10
    if d != 0:
        hoge=a*10+(d-1)
        q.put(hoge)
        tmp+=1
        if tmp==K:
            break
    
    hoge=a*10+d
    q.put(hoge)
    tmp+=1
    if tmp==K:
        break

    if d != 9:
        hoge=(a*10)+(d+1)
        q.put(hoge)
        tmp+=1
        if tmp==K:
            break

if K <= 9:
    print(K)
else:
    print(hoge)

Submission status: Accepted

Solution code:
from queue import Queue

K = int(input())

# 1 2 3 4 5 6 7 8 9 10 11 12 21 22 23 32 33 34 ... 98 99 100

q = Queue()

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

for _ in range(K):
    x = q.get()
    
    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)

Submission status: Accepted

Solution code:
import numpy as np
K = int(input())
table = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
c = 9
result = []
for i in table:
  runrun = i
  if runrun[-1] == '0':
    table.extend([runrun + str(int(runrun[-1])), 
                   runrun + str(int(runrun[-1])+1)])
    c += 2
  elif runrun[-1] == '9':
    table.extend([runrun + str(int(runrun[-1])-1), 
                   runrun + str(int(runrun[-1]))])
    c += 2
  else:
    table.extend([runrun + str(int(runrun[-1])-1), 
                   runrun + str(int(runrun[-1])), 
                   runrun + str(int(runrun[-1])+1)])
    c += 3
  if c>=K:
    print(table[K-1])
    exit()

Submission status: Accepted

Solution code:
K = int(input())
table = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
c = 9
result = []
for i in table:
  runrun = i
  if runrun[-1] == '0':
    table.extend([runrun + str(int(runrun[-1])), 
                   runrun + str(int(runrun[-1])+1)])
    c += 2
  elif runrun[-1] == '9':
    table.extend([runrun + str(int(runrun[-1])-1), 
                   runrun + str(int(runrun[-1]))])
    c += 2
  else:
    table.extend([runrun + str(int(runrun[-1])-1), 
                   runrun + str(int(runrun[-1])), 
                   runrun + str(int(runrun[-1])+1)])
    c += 3
  if c>=K:
    print(table[K-1])
    exit()

Submission status: Accepted

Solution code:
import copy
keta_lunlun = [1,2,3,4,5,6,7,8,9]
nexketa_lunlun = []
K = 0
keta = 1
def lunlun_gen(lunlun):
    global K
    global keta_lunlun
    global nexketa_lunlun
    global keta
    if(keta>=10):
        return lunlun
    nexketa_lunlun.clear()
    for i in range(len(keta_lunlun)):
        if(0<keta_lunlun[i]%10<9):
            lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10)-1)
            lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10)  )
            lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10)+1)
            nexketa_lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10-1))
            nexketa_lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10  ))
            nexketa_lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10+1))
          
        elif(keta_lunlun[i]%10 == 9):
            lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10)-1)
            lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10)  )
            nexketa_lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10-1))
            nexketa_lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10))
        else:
            lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10))
            lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10)+1)
            nexketa_lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10))
            nexketa_lunlun.append(keta_lunlun[i]*10+(keta_lunlun[i]%10+1))
    keta_lunlun.clear()
    keta_lunlun.extend(nexketa_lunlun)
    keta +=1
    return lunlun_gen(lunlun)

def main():
    global K
    K = int(input())
    lunlun = [1,2,3,4,5,6,7,8,9]
    ans = lunlun_gen(lunlun)
    print(ans[K-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
queue = deque(list(range(1,10,1)))
#print(queue)

if n <= 9:
    ans = queue[n-1]
else:
    i = 9
    while(True):
        x = queue.popleft()
        if x % 10 != 0:
            next_num = 10 * x + (x % 10) - 1 
            i += 1
            if i == n:
                ans = next_num
                break
            queue.append(next_num)
        #必ず
        i += 1
        next_num = 10 * x + (x % 10)
        if i == n:
            ans = next_num
            break
        queue.append(next_num)
        if x % 10 != 9:
            next_num = 10 * x + (x % 10) + 1 
            i += 1
            if i == n:
                ans = next_num
                break
            queue.append(next_num)
        #print(queue)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
stack = deque([x for x in range(1, 10)])
cnt = 9
flag = False
while len(stack) > 0:
    if k < 10:
        print(stack[k - 1])
        break
    now_num = stack.popleft()
    if now_num % 10 == 0:
        for x in [0, 1]:
            next_num = str(now_num) + str(x)
            next_num = int(next_num)
            stack.append(next_num)
            cnt += 1
            if cnt == k:
                print(stack.pop())
                flag = True
                break
    elif now_num % 10 == 9:
        for x in [8, 9]:
            next_num = str(now_num) + str(x)
            next_num = int(next_num)
            stack.append(next_num)
            cnt += 1
            if cnt == k:
                print(stack.pop())
                flag = True
                break
    else:
        for x in range(now_num % 10 - 1, now_num % 10 + 2):
            next_num = str(now_num) + str(x)
            next_num = int(next_num)
            stack.append(next_num)
            cnt += 1
            if cnt == k:
                print(stack.pop())
                flag = True
                break
    if flag:
        break