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):
from collections import deque
K = int(input())
queue = deque([1,2,3,4,5,6,7,8,9])
count = 1
while count <= K:
  num = queue.popleft()
  if num%10!=0:
    queue.append(num*10+num%10-1)
  queue.append(num*10+num%10)
  if num%10!=9:
    queue.append(num*10+num%10+1)
  count+=1
  
print(num)

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

d = deque()
c = 0
for i in range(1, 10):
  d.append(i)

while True:
  tmp = d.popleft()
  c += 1
  if c == k:
    ans = tmp
    break
  if tmp % 10 != 0:
    d.append(tmp * 10 + (tmp % 10 - 1))
  d.append(tmp * 10 + tmp % 10)
  if tmp % 10 != 9:
    d.append(tmp * 10 + (tmp % 10 + 1))
print(ans)

Solution (Python):
from collections import deque
K = int(input())
nums = deque([])
for i in range(1, 10):
  nums.appendleft(i)
count = 1
while count < K:
  num = nums.pop()
  last = int(str(num)[-1])
  for i in range(max(0, last-1), min(10, last+2)):
    nums.appendleft(int(str(num)+str(i)))
  count += 1
print(nums.pop())

Solution (Python):
from collections import deque

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

while len(queue) < 10 ** 5:
    n_str = queue.popleft()
    last_c = n_str[len(n_str) - 1]
    if last_c == "0":
        queue.append(n_str + "0")
        queue.append(n_str + "1")

        lunlun.append(n_str + "0")
        lunlun.append(n_str + "1")
    elif last_c == "1":
        queue.append(n_str + "0")
        queue.append(n_str + "1")
        queue.append(n_str + "2")

        lunlun.append(n_str + "0")
        lunlun.append(n_str + "1")
        lunlun.append(n_str + "2")
    elif last_c == "2":
        queue.append(n_str + "1")
        queue.append(n_str + "2")
        queue.append(n_str + "3")

        lunlun.append(n_str + "1")
        lunlun.append(n_str + "2")
        lunlun.append(n_str + "3")
    elif last_c == "3":
        queue.append(n_str + "2")
        queue.append(n_str + "3")
        queue.append(n_str + "4")

        lunlun.append(n_str + "2")
        lunlun.append(n_str + "3")
        lunlun.append(n_str + "4")
    elif last_c == "4":
        queue.append(n_str + "3")
        queue.append(n_str + "4")
        queue.append(n_str + "5")

        lunlun.append(n_str + "3")
        lunlun.append(n_str + "4")
        lunlun.append(n_str + "5")
    elif last_c == "5":
        queue.append(n_str + "4")
        queue.append(n_str + "5")
        queue.append(n_str + "6")

        lunlun.append(n_str + "4")
        lunlun.append(n_str + "5")
        lunlun.append(n_str + "6")
    elif last_c == "6":
        queue.append(n_str + "5")
        queue.append(n_str + "6")
        queue.append(n_str + "7")

        lunlun.append(n_str + "5")
        lunlun.append(n_str + "6")
        lunlun.append(n_str + "7")
    elif last_c == "7":
        queue.append(n_str + "6")
        queue.append(n_str + "7")
        queue.append(n_str + "8")

        lunlun.append(n_str + "6")
        lunlun.append(n_str + "7")
        lunlun.append(n_str + "8")
    elif last_c == "8":
        queue.append(n_str + "7")
        queue.append(n_str + "8")
        queue.append(n_str + "9")

        lunlun.append(n_str + "7")
        lunlun.append(n_str + "8")
        lunlun.append(n_str + "9")
    elif last_c == "9":
        queue.append(n_str + "8")
        queue.append(n_str + "9")

        lunlun.append(n_str + "8")
        lunlun.append(n_str + "9")

print(lunlun[K-1])

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

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

    start1 = ["1"]
    start2 = ["2"]
    start3 = ["3"]
    start4 = ["4"]
    start5 = ["5"]
    start6 = ["6"]
    start7 = ["7"]
    start8 = ["8"]
    start9 = ["9"]

    while len(lunlun) < 10 ** 5:
        next_starts = []
        for i in range(1, 10):
            news = []
            if i == 1:
                for n in start1:
                    if len(n) == 1:
                        new_n = n + "0"
                    else:
                        if abs(int(n[0])) > 1 or abs(int(n[1])) > 1:
                            break
                        new_n = n[0] + "0" + n[1:]
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start1:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start2:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 2:
                for n in start1:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start2:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start3:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 3:
                for n in start2:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start3:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start4:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 4:
                for n in start3:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start4:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start5:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 5:
                for n in start4:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start5:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start6:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 6:
                for n in start5:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start6:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start7:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 7:
                for n in start6:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start7:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start8:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 8:
                for n in start7:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start8:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start9:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 9:
                for n in start8:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start9:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)

        start1 = next_starts[0]
        start2 = next_starts[1]
        start3 = next_starts[2]
        start4 = next_starts[3]
        start5 = next_starts[4]
        start6 = next_starts[5]
        start7 = next_starts[6]
        start8 = next_starts[7]
        start9 = next_starts[8]

    print(lunlun[K-1])

main()

Solution (Python):
from collections import deque
 
K = int(input())
 
count = 0
Q = deque([1,2,3,4,5,6,7,8,9])
while count != K:
  a = Q.popleft()
  b = a%10
  if b != 0:
    Q.append(a*10 + b - 1)
  Q.append(a*10 + b)
  if b != 9:
    Q.append(a*10 + b + 1)
  count += 1
  
print(a)

Solution (Python):
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())
import sys
sys.setrecursionlimit(10**6)

def valid(i):
    ar=[]
    if i-1>=0:
        ar.append(i-1)
    ar.append(i)
    if i+1<=9:
        ar.append(i+1)
    return ar

k=int(input())
cur=[1,2,3,4,5,6,7,8,9]
if k<=9:
    print(cur[k-1])
else:
    while(k>len(cur)):
        new_cur=[]
        for i in cur:
            temp=valid(i%10)
            for j in temp:
                new_cur.append(i*10 + j)
        k-=len(cur)
        cur=new_cur.copy()
    print(cur[k-1])

Solution (Python):
from collections import deque

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

for i in range(K):
    runrun = q.popleft()
    rem = runrun % 10
    if rem == 0:
        q.append(runrun * 10)
        q.append(runrun * 10 + rem + 1)
    elif rem == 9:
        q.append(runrun * 10 + rem - 1)
        q.append(runrun * 10 + rem)
    else:
        q.append(runrun * 10 + rem - 1)
        q.append(runrun * 10 + rem)
        q.append(runrun * 10 + rem + 1)

print(runrun)

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

print(a)

Solution (Python):

from collections import deque

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

if k <= 9:
    print(q[k-1])
    exit()

i = 9
while 1:
    a = q.popleft()
    b = a % 10
    if b == 0:
        q.append(a * 10)
        i += 1
        if i == k:
            print(q[-1])
            exit()
        q.append(a * 10 + b + 1)
        i += 1
        if i == k:
            print(q[-1])
            exit()
    elif b == 9:
        q.append(a * 10 + b - 1)
        i += 1
        if i == k:
            print(q[-1])
            exit()
        q.append(a * 10 + b)
        i += 1
        if i == k:
            print(q[-1])
            exit()
    else:
        q.append(a * 10 + b - 1)
        i += 1
        if i == k:
            print(q[-1])
            exit()
        q.append(a * 10 + b)
        i += 1
        if i == k:
            print(q[-1])
            exit()
        q.append(a * 10 + b + 1)
        i += 1
        if i == k:
            print(q[-1])
            exit()

Solution (Python):
K = int(input())
A = [1,2,3,4,5,6,7,8,9]

for i in A:
  if K<len(A):
    break
  x = i%10
  for j in range(max(x-1,0),min(x+2,10)):
    A.append(10*i+j)

print(A[K-1])

Solution (Python):
import queue
def resolve():
    n = int(input())
    q = queue.Queue()
    for i in range(1,10):
        q.put(i)
    for _ in range(n):
        x = q.get()
        if x%10!=0:
            q.put(10*x+(x%10)-1)
        q.put(10*x+(x%10))
        if x%10!=9:
            q.put(10*x+(x%10)+1)
    print(x)
resolve()

Solution (Python):
import heapq
K = int(input())
def NewLun(strX):
    if strX[-1] != '0' and strX[-1] != '9':
        intX0 = int(strX[-1])
        heapq.heappush(Lun,int(strX + str(intX0+1)))
        heapq.heappush(Lun,int(strX + str(intX0)))
        heapq.heappush(Lun,int(strX + str(intX0-1)))
    elif strX[-1] == '0':
        heapq.heappush(Lun,int(strX + '0'))
        heapq.heappush(Lun,int(strX+'1'))
    else:
        heapq.heappush(Lun,int(strX +'9'))
        heapq.heappush(Lun,int(strX+'8'))
Lun = [i for i in range(1,10)]
heapq.heapify(Lun)
for _ in range(K):
    Ans = heapq.heappop(Lun)
    NewLun(str(Ans))
print(Ans)

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

Solution (Python):
from collections import deque

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

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

print(ans)

Solution (Python):
def update_queue(n, queue):
    out = queue[n]
    mod10 = out % 10
    if mod10 != 0:
        queue.append(10 * out + mod10 - 1)
    queue.append(10 * out + mod10)
    if mod10 != 9:
        queue.append(10 * out + mod10 + 1)

    return out, queue

N = int(input())
Q = [1,2,3,4,5,6,7,8,9]

for i in range(N):
    out, Q = update_queue(i, Q)

print(out)

Solution (Python):

"""
Created on Sat Sep 12 22:49:54 2020

@author: liang
"""

""" 
【小さいものから探索　⇒　キューを用いる】
【幅優先探索の応用】
     10 + 1 + 1
1 => 10 + 1 + 0
     10 + 1 - 1

10 => 100 + 0 + 1
      100 + 0 + 0
      100 + 0 - 1 *
"""

from collections import deque

K = int(input())

q = deque()
for i in range(1,10):
    q.append(i)
    
cnt = 0
while cnt  != K:
    cnt += 1
    ans = q.popleft()
    
    if ans % 10 != 0:
        q.append(10*ans + ans%10 - 1)
    q.append(10*ans + ans%10 )
    if ans % 10 != 9:
        q.append(10*ans + ans%10 + 1)
print(ans)

Solution (Python):
from collections import deque

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

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

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

if K <= 10:
    print(K)

else:
    cnt = 9
    l = deque(list(range(1,10)))
    while True:
        a = l.popleft()
        a1 = a% 10
        if a1 != 0:
            a2 = a*10 + a1 - 1
            cnt += 1
            if cnt == K:
                print(a2)
                break
            l.append(a2)
        
        a2 = a*10 + a1
        cnt += 1
        if cnt == K:
            print(a2)
            break
        l.append(a2)

        if a1 != 9:
            a2 = a*10 + a1 + 1
            cnt += 1
            if cnt == K:
                print(a2)
                break
            l.append(a2)

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

ans = 1

def next(n):
    nStr = list(map(int, list(str(n))))

    r = len(nStr)-1
    while r > 0:
        if nStr[r] <= nStr[r-1] and not (nStr[r-1] == 9 and nStr[r] == 9):
            break
        r -= 1

    if r == 0 and nStr[0] == 9:
        nStr = [1] + [0] * len(nStr)
    else:
        extra = len(nStr)-1-r
        nStr = nStr[:r] + [nStr[r]+1]

        for _ in range(extra):
            nStr.append(max(0, nStr[-1]-1))

    return int("".join(map(str, nStr)))

for i in range(k-1):
    ans = next(ans)

print(ans)

Solution (Python):
from collections import deque
K=int(input())
lunlun=[]
q=deque(list(range(1,10)))
while 1:
    r=q.popleft()
    lunlun.append(r)
    n=str(r)[-1]
    if n!='0':
        q.append(r*10+int(n)-1)
    q.append(r*10+int(n))
    if n!='9':
        q.append(r*10+int(n)+1)
    if len(lunlun)>K:
        break
print(lunlun[K-1])

Solution (Python):
from collections import deque

K = int(input())

d = deque(i for i in range(1, 10))

count = 0

while count != K:
    x = d.popleft()
    a = (10 * x) + (x % 10)
    if x % 10 != 0:
        d.append(a - 1)

    d.append(a)

    if x % 10 != 9:
        d.append(a + 1)

    count += 1

print(x)

Solution (Python):
def dfs(cnt, num, top):
    if cnt == 10:
        return
    v.add(int(num))
    if top == 0:
        dfs(cnt+1, "0"+num, top)
        dfs(cnt+1, "1"+num, top+1)
    elif top == 9:
        dfs(cnt+1, "8"+num, top-1)
        dfs(cnt+1, "9"+num, top)
    else:
        dfs(cnt+1, str(top-1)+num, top-1)
        dfs(cnt+1, str(top)+num, top)
        dfs(cnt+1, str(top+1)+num, top+1)


k = int(input())
v = set()
for i in range(10):
    dfs(0, str(i), i)
v = list(v)
v.sort()
v.pop(0)
print(v[k-1])

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

from collections import deque
q = deque(list(range(1, 10)))

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

Solution (Python):
L=[]

def make_lunlun(A):
    
    
   
    if not 0<A<10**10 :
        return
    
    global L
    
    
    L.append(A)
    
    if(A%10 != 9):
        make_lunlun(A*10 + (A%10)+1)

    
    if(A!=0):
        make_lunlun(A*10+(A%10))

    
    if(A%10 != 0):
        make_lunlun(A*10 +(A%10)- 1)

    
k=int(input())


for i in range(10):
    make_lunlun(i)
  
L=list(set(L))
L.sort()

print(L[k-1])

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    lunlun = [i for i in range(10)]
    def make(s,keta):
        lst = []
        end = int(s[-1])
        if end == 0:
            lst = [s+"0",s+"1"]
        elif end == 9:
            lst = [s+"8",s+"9"]
        else:
            lst = [s+str(end+i) for i in range(-1,2)]
        if keta == 1:
            for lun in lst:
                lunlun.append(int(lun))
        else:
            for lun in lst:
                make(lun,keta-1)
            
    for keta in range(1,10):
        for i in range(1,10):
            make(str(i),keta)

    k = I()
    ans = lunlun[k]
    print(ans) 
                
        

main()

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

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

print(x)

Solution (Python):
import sys
k = int(input())
lst = [[0]*10 for i in range(10)]
for i in range(10):
  lst[0][i] = 1
l_sum = [9]  


for i in range(1,10):
  s = 0
  for j in range(10):
    if j == 0:
      lst[i][j] = lst[i-1][j] + lst[i-1][j+1]
    elif j == 9:
      lst[i][j] = lst[i-1][j] + lst[i-1][j-1] 
    else:
      lst[i][j] = lst[i-1][j-1] + lst[i-1][j] + lst[i-1][j+1] 
      
    if j !=0:
      s += lst[i][j]
  l_sum.append(s+l_sum[-1])
    


i = 0
if k < l_sum[0]:
  print(k)
  sys.exit()
else:
  while True:
    if k < l_sum[i]:
      break
    i += 1
  k = k - l_sum[i-1]
   
  ans = []
  for j in reversed(range(0, i+1)):
    
    if j == i:
      p = 1
      while True:
        if k - lst[j][p] <= 0:
          ans.append(p)
          break
        else:
          k -= lst[j][p]
          p += 1
          
    else:
      if p == 0:
        if k <= lst[j][p]:
          ans.append(p)
        else:
          k -= lst[j][p]
          p += 1
          ans.append(p)
          
      elif p == 9:
        if k <= lst[j][p-1]:
          p = p-1
          ans.append(p)
        else:
          k -= lst[j][p-1]
          ans.append(p)
          
      else:
        if k <= lst[j][p-1]:
          p = p-1
          ans.append(p)
        else:
          k -= lst[j][p-1]
          if k <= lst[j][p]:
            ans.append(p)
          else:
            k -= lst[j][p]
            p = p+1
            ans.append(p)
              
l_s = [str(q) for q in ans]
print(''.join(l_s))

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

q = deque()
for i in range(1, 10):
    q.append(i)
cnt = 0
while True:
    a = q.popleft()
    cnt += 1
    if cnt == k:
        print(a)
        exit()
    b = a % 10
    for i in (-1, 0, 1):
        if 0 <= b + i <= 9:
            q.append(a*10 + b+i)

Solution (Python):
import bisect

k = int(input())

def runrun(n):
    str_n = str(n)
    for i in range(len(str_n)-1):
        if abs(int(str_n[i]) - int(str_n[i+1])) > 1:
            return False
    return True

def build_runrun(d):
    r = ["0","1","2","3","4","5","6","7","8","9"]
    ans = []
    for i in r:
        if i == "0":
            continue
        queue = [[i,1,i]]
        while queue != []:
            q = queue.pop(0)
            if q[1] > d:
                continue
            if q[1] == d:
                bisect.insort(ans,int(q[2]))
                continue

            queue.append([q[0],q[1]+1,q[2]+q[0]])

            low = int(q[0])-1
            if low >= 0:
                queue.append([str(low),q[1]+1,q[2]+str(low)])
            high = int(q[0])+1
            if high < 10:
                queue.append([str(high),q[1]+1,q[2]+str(high)])

    return ans

run = []
d = 1
while len(run) < k:
    run.extend(build_runrun(d))
    d+=1

print(run[k-1])

Solution (Python):
import bisect

k = int(input())

def runrun(n):
    str_n = str(n)
    for i in range(len(str_n)-1):
        if abs(int(str_n[i]) - int(str_n[i+1])) > 1:
            return False
    return True

def build_runrun(d):
    r = ["0","1","2","3","4","5","6","7","8","9"]
    ans = []
    for i in r:
        if i == "0":
            continue
        queue = [[i,1,i]]
        while queue != []:
            q = queue.pop(0)
            if q[1] > d:
                continue
            if q[1] == d:
                bisect.insort(ans,int(q[2]))
                continue

            queue.append([q[0],q[1]+1,q[2]+q[0]])

            low = int(q[0])-1
            if low >= 0:
                queue.append([str(low),q[1]+1,q[2]+str(low)])
            high = int(q[0])+1
            if high < 10:
                queue.append([str(high),q[1]+1,q[2]+str(high)])

    return ans

run = []
d = 1
while len(run) < k:
    run.extend(build_runrun(d))
    d+=1

print(run[k-1])

Solution (Python):
def lu(n):
  L.append(n)
  a=n%10
  if len(str(n))>11:
    return 1
  if a==0:
    lu(n*10+1)
    lu(n*10)
  elif a==9:
    lu(n*10+9)
    lu(n*10+8)
  else:
    lu(n*10+1+a)
    lu(n*10+a-1)
    lu(n*10+a)
L=list()
lu(1)
lu(2)
lu(3)
lu(4)
lu(5)
lu(6)
lu(7)
lu(8)
lu(9)
L=sorted(set(L))
k=int(input())
print(L[k-1])

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

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

count = 0
while True:
    count += 1
    if count == k:
        print(d.popleft())
        exit()
    t = d.popleft()
    r = t % 10
    if r != 0:
        d.append(10*t + r - 1)
    d.append(10*t + r)
    if r != 9:
        d.append(10*t + r + 1)

Solution (Python):


import sys

import heapq


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = int(input())
    if n < 10:
        print(n)
        return
    cnt = 0
    hq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    while cnt < n:
        i = heapq.heappop(hq)
        cnt += 1
        if cnt == n:
            print(i)
            return
        r = int(str(i)[::-1][0])
        heapq.heappush(hq, int(str(i) + str(r)))
        if r != 9:
            heapq.heappush(hq, int(str(i) + str(r + 1)))
        if r != 0:
            heapq.heappush(hq, int(str(i) + str(r - 1)))
    return


if __name__ == "__main__":
    main()

Solution (Python):
def is_good(mid, key):
    S = list(map(int, str(mid)))
    N = len(S)
    dp = [[[0] * 11 for _ in range(2)] for _ in range(N + 1)]
    dp[1][1][10] = 1
    for k in range(1, S[0]):
        dp[1][1][k] = 1
    dp[1][0][S[0]] = 1
    for i in range(1, N):
        for k in range(1, 11):
            dp[i + 1][1][k] += dp[i][0][10] + dp[i][1][10]
        for is_less in range(2):
            for k in range(10):
                for l in range(k - 1, k + 2):
                    if not 0 <= l <= 9 or (not is_less and l > S[i]):
                        continue
                    dp[i + 1][is_less or l < S[i]][l] += dp[i][is_less][k]
    return sum(dp[N][0][k] + dp[N][1][k] for k in range(10)) >= key


def binary_search(bad, good, key):
    while good - bad > 1:
        mid = (bad + good) // 2
        if is_good(mid, key):
            good = mid
        else:
            bad = mid
    return good


K = int(input())
print(binary_search(0, 3234566667, K))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5)


def dfs(v):
    if v > 3234566667:
        return
    ans.append(v)
    d = v % 10
    if d - 1 >= 0:
        dfs(v * 10 + d - 1)
    dfs(v * 10 + d)
    if d + 1 < 10:
        dfs(v * 10 + d + 1)


K = int(input())
ans = []
[dfs(i) for i in range(1, 10)]
print(sorted(ans)[K - 1])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5)


def dfs(v):
    ans.append(v)
    if v > 1_000_000_000:
        return
    for d in range(10):
        if abs(d - v % 10) <= 1:
            nv = v * 10 + d
            dfs(nv)


K = int(input())
ans = []
[dfs(i) for i in range(1, 10)]
print(sorted(ans)[K - 1])

Solution (Python):
from queue import Queue as Q
k = int(input())
q = Q()
[q.put(i) for i in range(1, 10)]

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

print(x)

Solution (Python):






from collections import deque





K = int(input())





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

Solution (Python):
import sys
input = sys.stdin.readline




'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

k=int(input())

from queue import Queue
que=Queue()
for i in range(1,10):
    que.put(str(i))
cnt=0
while True:
    a=que.get()
    cnt+=1
    
    if cnt==k:
        print(a)
        sys.exit()
    if a[-1]=="0":
        que.put(a+"0")
        que.put(a+"1")
    elif a[-1]=="9":
        que.put(a+"8")
        que.put(a+"9")
    else:
        
        que.put(a+chr(ord(a[-1])-1))
        que.put(a+a[-1])
        que.put(a+chr(ord(a[-1])+1))

Solution (Python):
K = int(input())
a = []

def DFS(n):
    if n > 3234566667:
        return
    a.append(n)
    l = n % 10
    if l == 0:
        DFS(10 * n)
        DFS(10 * n + 1)
    elif l == 9:
        DFS(10 * n + 9)
        DFS(10 * n + 8)
    else:
        DFS(10 * n + l)
        DFS(10 * n + l + 1)
        DFS(10 * n + l - 1)

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

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

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    k = i_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)


if __name__=="__main__":
    main()

Solution (Python):
from collections import deque

def main():
    k = int(input())
    l = list(range(1, 10))
    Q = deque(l)
    for _ in range(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)
    print(q)

if __name__ == '__main__':
    main()

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

def list2int(digits):
    return int("".join(map(str, digits)))

def int2list(n):
    return list(map(int, str(n)))

def search(digits):
    ret = []
    v = digits[-1]
    for d in [-1, 0, 1]:
        if 0 <= v+d <= 9:
            ret.append(list2int(digits + [v+d]))
    return(ret)

result = list(range(1, 9+1))

i = 0
while len(result) < K:
    digits = int2list(result[i])
    result.extend(search(digits))
    i += 1

print(result[K-1])

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

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

A = [0 for d in range(20)]
A[0] = 1
dit_max = 0


for ct in range(2,K+1):
  dit_now = 0
  while dit_max > dit_now and (A[dit_now] == A[dit_now+1]+1 or A[dit_now] == 9):
    dit_now += 1
  if dit_max > dit_now:
    A[dit_now] += 1
  elif dit_max == dit_now:
    if A[dit_now] == 9:
      dit_max += 1
      dit_now += 1
    A[dit_now] += 1
  for d in range(dit_now-1,-1,-1):
      A[d] = max(A[d+1] - 1,0)
  
    
      
ans = 0
for i in range(20):
  ans += A[i] * 10**i
print(ans)

Solution (Python):
import queue
k=int(input())
q=queue.Queue()
for i in range(1,10):
    q.put(i)
lunlun=list(range(1,10))
cnt=9

while cnt<=k:
    v=q.get()
    last=v%10
    if last!=0:
        new=v*10+last-1
        q.put(new)
        lunlun.append(new)
        cnt+=1
    new=v*10+last
    q.put(new)
    lunlun.append(new)
    cnt+=1
    if last!=9:
        new=v*10+last+1
        q.put(new)
        lunlun.append(new)
        cnt+=1
print(lunlun[k-1])