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.

Solution (Python):
def LunLun(k, count, base):
    nx = []
    n = len(base)
    if count + n >= k:
        ans = base[k - count - 1]
        print(ans)
        exit()

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

Solution (Python):
def LunLun(k, count, base):
    nx = []
    n = len(base)
    if count + n >= k:
        ans = base[k - count - 1]
        print(ans)
        exit()

    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)
    LunLun(k, 0, base)
    

if __name__ == '__main__':
    main()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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])
        
        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)
        
        count += 1
        next_num = "".join([num, str(d1)])
        if count == K:
            return int(next_num)
        else:
            queue.append(next_num)
        
        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()

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

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


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[k-1])

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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

Solution (Python):
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)

Solution (Python):
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)
        
        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])

Solution (Python):
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()))



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

Solution (Python):
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()))



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

Solution (Python):
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)

Solution (Python):


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)
        
        k -= found
        x = [[]] * (length + 1)
        x[1] = list(range(1, 10))
        

        terminate = False
        i = 1
        while True:
            
            if len(x[i]): 
                digit = x[i][0]
                if i < length: 
                    i += 1
                    x[i] = nxt[digit].copy()
                    
                    
                    if i == length: 
                        while len(x[i]): 
                            k -= 1
                            
                            if k == 0:
                                x.pop(0)
                                
                                ans = "".join([str(j.pop(0)) for j in x])
                                print(ans)
                                terminate = True
                                break
                            else:
                                x[i].pop(0)
                            
                        else:
                            
                            while len(x[i]) == 0:
                                i -= 1
                                x[i].pop(0)
                        if terminate:
                            break

f(int(input()))

Solution (Python):
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()))

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
if __name__ == "__main__":
    """
    X is ルンルン数 ⇔ Xを10進数表記したとき、隣り合うどの2つの桁の値についても、差の絶対値が1以下
    """
    K = int(input())
    
    
    
    
    
    
    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])

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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])

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

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

Solution (Python):
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()

Solution (Python):
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())

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
k=int(input())


import sys
sys.setrecursionlimit(10**7)
def dfs(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])

Solution (Python):
from heapq import heapify, heappop, heappush


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]  
heapify(queue)

for _ in range(K-1):
    now = heappop(queue)  
    
    for next_i in next_num(now%10):
        heappush(queue, now*10 + next_i)

print(queue[0])

Solution (Python):
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])

Solution (Python):
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();

Solution (Python):
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)

Solution (Python):
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())

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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()
    
    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)

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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())

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
from queue import Queue

K = int(input())



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)

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()

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


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