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):
import sys
sys.setrecursionlimit(10**9)

k=int(input())

def dfs(keta,num):
  global ans
  ans.append(int(''.join(num)))

  if keta==10:
    return

  min_n=max(0,int(num[-1])-1)
  max_n=min(9,int(num[-1])+1)
  for i in range(min_n,max_n+1):
    dfs(keta+1,num+[str(i)])

ans=[]
for i in range(1,10):
  dfs(1,[str(i)])

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

Solution (Python):
import sys

k=int(input())

def dfs(keta,num):
  global ans
  ans.append(int(''.join(num)))

  if keta==10:
    return

  min_n=max(0,int(num[-1])-1)
  max_n=min(9,int(num[-1])+1)
  for i in range(min_n,max_n+1):
    dfs(keta+1,num+[str(i)])

ans=[]
for i in range(1,10):
  dfs(1,[str(i)])

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

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

def dfs(keta,num):
  global ans
  ans.append(int(''.join(num)))

  if keta==10:
    return

  min_n=max(0,int(num[-1])-1)
  max_n=min(9,int(num[-1])+1)
  for i in range(min_n,max_n+1):
    dfs(keta+1,num+[str(i)])

ans=[]
for i in range(1,10):
  dfs(1,[str(i)])

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

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

def f(n, k, a):
    if k == n:
        return 1
    res = 0
    res += f(n, k+1, a)
    if a > 0:
        res += f(n, k+1, a-1)
    if a < 9:
        res += f(n, k+1, a+1)
    return res


cnt = 0
for n in range(1, 12):
    c2 = 0
    for a in range(1, 10):
        c2 += f(n, 1, a)
        if cnt+c2 >= K:
            num = n
            ini = a
            cnt += c2-f(n, 1, a)
            c2 = -1
            break
    if c2 < 0:
        break
    cnt += c2

ans = [ini]
for k in range(2, num+1):
    for a in range(max(0, ans[-1]-1), min(10, ans[-1]+2)):
        cnt += f(num, k, a)
        if cnt >= K:
            ans.append(a)
            cnt -= f(num, k, a)
            break

for i in range(len(ans)):
    ans[i] = str(ans[i])
print("".join(ans))

Solution (Python):
from collections import deque
K = int(input())
A = deque([str(i) for i in range(1,10)])
cnt = 0
while cnt<K:
    a = A.popleft()
    cnt += 1
    if a[-1]=="0":
        a0 = a+"0"
        a1 = a+"1"
        A.append(a0)
        A.append(a1)
    elif a[-1]=="9":
        a0 = a+"8"
        a1 = a+"9"
        A.append(a0)
        A.append(a1)
    else:
        b = a[-1]
        a0 = a+str(int(b)-1)
        a1 = a+b
        a2 = a+str(int(b)+1)
        A.append(a0)
        A.append(a1)
        A.append(a2)
print(a)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def dfs(s):
  if len(s)==11:
    return
  if s!="":
    a.append(int(s))
  for c in "0123456789":
    if s=="" and c=="0":continue
    if s!="":
      if abs(ord(c)-ord(s[-1]))<=1:
        dfs(s+c)
    else:
      dfs(s+c)

k=int(input())
a=[]
dfs("")
a=list(set(a))
a.sort()
print(a[k-1])

Solution (Python):
N = int(input())
if N <= 9:
  print(N)
  exit()
A = [[] for _ in range(11)]
A[0] = [1,2,3,4,5,6,7,8,9]
now = 9
keta = 1
while True:
  for x in A[keta-1]:
    x = str(x)
    last = int(x[-1])
    if last - 1 >= 0:
      temp = x+str(last-1)
      A[keta].append(int(temp))
      now += 1
      if now == N:
        print(temp)
        exit()
    temp = x+str(last)
    A[keta].append(int(temp))
    now += 1
    if now == N:
      print(temp)
      exit()
    if last+1 <= 9:
      temp = x+str(last+1)
      A[keta].append(int(temp))
      now += 1
      if now == N:
        print(temp)
        exit()
  keta += 1

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


def dfs(d, n, buf):
    buf.append(n)

    if d == 10:
        return

    lsd = n % 10

    if lsd != 0:
        dfs(d + 1, n * 10 + lsd - 1, buf)

    dfs(d + 1, n * 10 + lsd, buf)

    if lsd != 9:
        dfs(d + 1, n * 10 + lsd + 1, buf)


buf = []

for n in range(1, 10):
    dfs(1, n, buf)

print(sorted(buf)[K - 1])

Solution (Python):
from collections import deque

K = int(input())

queue = deque(range(1, 10))

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

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

k = K - 1

numbers = {
    0: 1
}

while k > 0:
    k -= 1
    for i in range(len(numbers)):
        n = numbers[i]
        if n == 9:
            continue

        if abs(numbers.get(i - 1, n) - (n + 1)) <= 1 and abs(numbers.get(i + 1, n) - (n + 1)) <= 1:
            numbers[i] += 1
            j = i - 1
            while j >= 0:
                numbers[j] = max(numbers[j + 1] - 1, 0)
                j -= 1
            break
    else:
        for key in numbers.keys():
            numbers[key] = 0
        numbers[len(numbers)] = 1

print(''.join([str(numbers[i]) for i in range(len(numbers))])[::-1])

Solution (Python):
from collections import deque

k = int(input())
q = deque(range(1, 10))

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

ans = q.popleft()
print(ans)

Solution (Python):
from collections import deque
k = int(input())
que = deque(list(range(1,10)))
for i in range(k):
    x = que.popleft()
    if x%10!=0:
        que.append(10*x+x%10-1)
    que.append(10*x+x%10)
    if x%10!=9:
        que.append(10*x+x%10+1)
print(x)

Solution (Python):
import sys
from heapq import heapify, heappop, heappush
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

heapify(a)
while len(a):
    tmp = heappop(a)
    keta = len(str(tmp))
    one = tmp % 10
    k -= 1
    
    if one != 0: heappush(a, tmp * 10 + one - 1)
    heappush(a, tmp * 10 + one)
    if one != 9: heappush(a, tmp * 10 + one + 1)
    if k == 0:
        print(tmp)
        exit()

Solution (Python):
import sys
from heapq import heapify, heappop, heappush
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

heapify(a)
while len(a):
    tmp = heappop(a)
    keta = len(str(tmp))
    one = tmp % 10
    k -= 1
    for i in range(0, 10):
        if abs(one - i) <= 1:
            heappush(a, tmp * 10 + i)
    if k == 0:
        print(tmp)
        exit()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    vec = list(range(1, 10))
    for i in range(K):
        tail = vec[i] % 10
        n10 = vec[i] * 10
        if tail == 0:
            vec.append(n10 + tail)
            vec.append(n10 + tail + 1)
        elif tail == 9:
            vec.append(n10 + tail - 1)
            vec.append(n10 + tail)
        else:
            vec.append(n10 + tail - 1)
            vec.append(n10 + tail)
            vec.append(n10 + tail + 1)

        if len(vec) >= K:
            break

    print(vec[K - 1])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    vec = list(range(1, 10))
    for i in range(K):
        tail = vec[i] % 10
        if tail == 0:
            vec.append(vec[i] * 10 + tail)
            vec.append(vec[i] * 10 + tail + 1)
        elif tail == 9:
            vec.append(vec[i] * 10 + tail - 1)
            vec.append(vec[i] * 10 + tail)
        else:
            vec.append(vec[i] * 10 + tail - 1)
            vec.append(vec[i] * 10 + tail)
            vec.append(vec[i] * 10 + tail + 1)

        if len(vec) == K:
            break

    print(vec[K - 1])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    vec = list(range(1, 10))
    for i in range(K):
        tail = vec[i] % 10
        n10 = vec[i] * 10
        if tail == 0:
            vec.append(n10 + tail)
            vec.append(n10 + tail + 1)
        elif tail == 9:
            vec.append(n10 + tail - 1)
            vec.append(n10 + tail)
        else:
            vec.append(n10 + tail - 1)
            vec.append(n10 + tail)
            vec.append(n10 + tail + 1)
            
        if len(vec) == K:
            break

    print(vec[K - 1])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    vec = list(range(1, 10))
    for i in range(K):
        tail = vec[i] % 10
        n10 = vec[i] * 10
        if tail == 0:
            vec.append(n10 + tail)
            vec.append(n10 + tail + 1)
        elif tail == 9:
            vec.append(n10 + tail - 1)
            vec.append(n10 + tail)
        else:
            vec.append(n10 + tail - 1)
            vec.append(n10 + tail)
            vec.append(n10 + tail + 1)

    print(vec[K - 1])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    queue = deque(range(1, 10))
    for _ in range(K):
        n = queue.popleft()

        tail = n % 10
        n10 = n * 10
        if tail == 0:
            queue.append(n10 + tail)
            queue.append(n10 + tail + 1)
        elif tail == 9:
            queue.append(n10 + tail - 1)
            queue.append(n10 + tail)
        else:
            queue.append(n10 + tail - 1)
            queue.append(n10 + tail)
            queue.append(n10 + tail + 1)

    print(n)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    queue = deque(range(1, 10))
    for _ in range(K):
        n = queue.popleft()

        tail = n % 10
        n10 = n * 10
        if tail != 0:
            queue.append(n10 + tail - 1)
        queue.append(n10 + tail)
        if tail != 9:
            queue.append(n10 + tail + 1)

    print(n)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    n = 0

    def dfs(vec, d):
        nonlocal n
        if d == 0:
            n += 1
            if n == K:
                print(''.join(map(str, vec)))
                return
            else:
                return

        for i in range(max(0, vec[-1] - 1), min(9, vec[-1] + 1) + 1):
            vec.append(i)
            dfs(vec, d - 1)
            if n >= K:
                return
            vec.pop()

    for d in range(10 ** 20):
        for i in range(1, 10):
            vec = [i]
            dfs(vec, d)
            if n >= K:
                return

    return


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import chain

K = int(input())

L = 10
lunlun = [[] for _ in range(L+1)]

lunlun[1] = list(range(1,10))

for i in range(1,L):
    for x in lunlun[i]:
        r = x%10
        if r == 0:
            lunlun[i+1] += [x*10 + r, x*10 + r+1]
        elif r == 9:
            lunlun[i+1] += [x*10 + r-1, x*10 + r]
        else:
            lunlun[i+1] += [x*10 + r-1, x*10 + r, x*10 + r+1]

res = list(chain.from_iterable(lunlun))

print(res[K-1])

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

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


dp = [[0]*10 for _ in range(10)]    
i = 0
flg = False

for k in range(10):
    dp[0][k] = 1

S = 8
while True:
    i += 1
    for k in range(10):
        if k==9:
            dp[i][k] = dp[i-1][k] + dp[i-1][k-1]
        elif k == 0:
            dp[i][k] = dp[i - 1][k + 1] + dp[i - 1][k]
        else:
            dp[i][k] = dp[i - 1][k + 1] + dp[i - 1][k] + dp[i - 1][k - 1]
        if k != 0:
            S += dp[i][k]
        if S >= K-1:
            flg = True
            break
    if flg:
        break
i_max, k_max = i, k
i_max -= 1
res = [k_max]
for i in range(i_max, -1, -1):
    for k in reversed(range(k_max-1,k_max+2)):
        if k > 9 or k < 0:
            continue
        if S - dp[i][k] >= K-1:
            S -= dp[i][k]
        else:
            break
    k_max = k
    res.append(k)

print(*res, sep="")

Solution (Python):
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

k = INT()
q = Queue()

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

Solution (Python):
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

k = INT()
s = list('00000000000')

for i in range(k):
    for j in range(len(s)):
        if s[j] != '9' and ( int("".join(s[j+1:])) == 0 or int(s[j]) < int(s[j+1]) + 1 ):
            s[j] = str(int(s[j]) + 1)
        else:
            continue

        while j > 0:
            j -= 1
            s[j] = str(max(0, int(s[j+1])-1))
        break

ans = int("".join(reversed(s)))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
S = []
def add(a):
    if a > 3234566667:
        return
    x = a % 10
    if x != 0:
        S.append(a * 10 + x - 1)
        add(a * 10 + x - 1)
    S.append(a * 10 + x)
    add(a * 10 + x)
    if x != 9:
        S.append(a * 10 + x + 1)
        add(a * 10 + x + 1)
for i in range(9):
    S.append(i+1)
    add(i+1)
S.sort()
print(S[int(input())-1])

Solution (Python):
k=int(input())
l=[i for i in range(1,10)]
for i in range(k):
    r=l.pop(0)
    rr=r%10
    if rr!=0:
        l.append(10*r+rr-1)
    l.append(10*r+rr)
    if rr!=9:
        l.append(10*r+rr+1)
print(r)

Solution (Python):
import sys
import queue


def solve(k):
    q = queue.Queue()
    for i in range(1, 10):
        q.put(i)
    for i in range(k):
        n = q.get()
        if i == k - 1:
            return n
        if n % 10 == 0:
            q.put(n * 10)
            q.put(n * 10 + 1)
        elif n % 10 == 9:
            q.put(n * 10 + 8)
            q.put(n * 10 + 9)
        else:
            l = n % 10
            q.put(n * 10 + l - 1)
            q.put(n * 10 + l)
            q.put(n * 10 + l + 1)


def main():
    input = sys.stdin.buffer.readline
    k = int(input())
    print(solve(k))


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
K = int(input())
d = deque([1,2,3,4,5,6,7,8,9])
count = 0
while True:
    tag = d.popleft()
    tmp1 = tag % 10
    tmp2 = tmp1 + tag * 10
    if tmp1 == 9:
        d.append(tmp2 - 1)
        d.append(tmp2)
    elif tmp1 == 0:
        d.append(tmp2)
        d.append(tmp2 + 1)
    else:
        d.append(tmp2 - 1)
        d.append(tmp2)
        d.append(tmp2 + 1)
    count += 1
    if count == K:
        print(tag)
        break

Solution (Python):
import collections

K = int(input())

L = [1,2,3,4,5,6,7,8,9]
Q = collections.deque(L)
count = 0 

while count < K-1:
    V = Q.popleft()
    count+=1
    if V%10 == 0:
        Q.append(10*V)
        Q.append(10*V+1)
    elif V%10 == 9:
        Q.append(10*V+8)
        Q.append(10*V+9)
    else:
        Q.append(10*V+(V%10)-1)
        Q.append(10*V+(V%10))
        Q.append(10*V+(V%10)+1)

print(Q.popleft())

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

Lunlun = []
K = int(input())

def dfs(i,before):
    if i == 10:
        return
    Lunlun.append(before)
    x = before%10
    for d in (-1,0,1):
        y = x + d
        if y < 0 or y >= 10:
            continue
        dfs(i + 1,before*10 + y)

for i in range(1,10):
    dfs(0,i)
Lunlun.sort()
ans = Lunlun[K - 1]
print(ans)

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

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

while queue: 
    tmp = queue.popleft() 
    if len(ptns) < n: 
        ptns.append(tmp)
    else:
        break
 
    if tmp[-1] != 0:
        queue.append(tmp + [tmp[-1] -1])

    queue.append(tmp + [tmp[-1]])

    if tmp[-1] != 9:
        queue.append(tmp + [tmp[-1] +1])


print(''.join(map(str, ptns[-1])))

Solution (Python):
def main():
    k = int(input())
    hp = [i for i in range(k+4)]
    r, w = 1, 10
    while w <= k:
        n = hp[r]
        r += 1
        nm = n % 10
        val = n * 10 + nm
        
        if nm != 0:
            hp[w] = val - 1
            w += 1
        hp[w] = val
        w += 1
        if nm != 9:
            hp[w] = val + 1
            w += 1

    print(hp[k])

main()

Solution (Python):
def main():
    k = int(input())
    hp = list(range(1, 10))
    for i in range(k-1):
        n = hp.pop(0)
        nm = n % 10
        val = n * 10 + nm
        
        if nm != 0:
            hp.append(val - 1)
        hp.append(val)
        if nm != 9:
            hp.append(val + 1)
    print(hp[0])

main()

Solution (Python):
from collections import deque
K = int(input())
q = deque()
for i in range(1, 10):
    q.append(i)
i = 0
run = []
while i < K:
    i += 1
    x = q.popleft()
    if x % 10 != 0:
        q.append(10*x + x%10 - 1)
    q.append(10*x + x%10)
    if x % 10 != 9:
        q.append(10*x + x%10 + 1)
    run.append(x)

print(run[K - 1])

Solution (Python):
def incr_lunlun(num):
    num[0] += 1
    if len(num) == 1:
        if num[0] == 10:
            num.append(1)
            num[0] = 0
    
    elif num[0] > num[1] + 1 or num[0] == 10:
        suffix = incr_lunlun(num[1:])
        digit = max(0, suffix[0] - 1)
        num = [digit] + list(suffix)

    return num


def main():
    k = int(input())
    num = [1]
    for i in range(k-1): 
        num = incr_lunlun(num)

    print(int(''.join(str(i) for i in reversed(num))))



main()

Solution (Python):
import queue

k=int(input())

q = queue.Queue()


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


for n in range(1,k+1):
    a = q.get()
    c = a % 10
    if c != 0:
       q.put(10*a + c-1)
    q.put(10*a + c)
    if c != 9:
       q.put(10*a + c+1)

print(a)

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


while len(numbers) <= 100000:  
    
    qq = set([])
    for i in q:
        
        if i % 10 != 0:
            n = i * 10 + (i % 10) - 1
            qq.add(n)
        if i % 10 != 9:
            n = i * 10 + (i % 10) + 1
            qq.add(n)
        n = i * 10 + (i % 10)
        qq.add(n)
    numbers |= q
    
    
    q = qq

numbers = sorted(map(int, numbers))

ans = numbers[K - 1]
print(ans)

Solution (Python):
K = int(input())
numbers = set([])
q = set(list(map(str, [1, 2, 3, 4, 5, 6, 7, 8, 9])))


while len(numbers) <= 100000:  
    
    qq = set([])
    for i in q:
        
        if len(i) == 1:
            if i == '0':
                n = i + '0'
                qq.add(n)
                n = i + '1'
                qq.add(n)
            elif i == '9':
                n = i + '9'
                qq.add(n)
                n = i + '8'
                qq.add(n)
            else:
                v = int(i)
                n = i + str(v - 1)
                qq.add(n)
                n = i + str(v)
                qq.add(n)
                n = i + str(v + 1)
                qq.add(n)
        else:
            if i[-1] == '0':
                n = i + '0'
                qq.add(n)
                n = i + '1'
                qq.add(n)
            elif i[-1] == '9':
                n = i + '9'
                qq.add(n)
                n = i + '8'
                qq.add(n)
            else:
                v = int(i[-1])
                n = i + str(v - 1)
                qq.add(n)
                n = i + str(v)
                qq.add(n)
                n = i + str(v + 1)
                qq.add(n)
    
    numbers |= q
    
    
    q = qq

numbers = sorted(map(int, numbers))

ans = numbers[K - 1]
print(ans)

Solution (Python):
def resolve():
	from collections import deque
	K = int(input())
	q = deque(str(i) for i in range(1, 10))
	cnt = 9
	if K < 10:
		print(K); return
	while True:
		tmp = q.popleft()
		las = int(tmp[-1])
		for i in range(las-1, las+2):
			if 0<=i<=9:
				q.append(tmp + str(i))
				cnt += 1
				if cnt==K:
					print(q.pop()); return
resolve()

Solution (Python):
def resolve():
	from collections import deque
	K = int(input())
	q = deque(str(i) for i in range(1, 10))
	cnt = 9
	if K < 10:
		print(K); return
	while True:
		tmp = q.popleft()
		las = int(tmp[-1])
		for i in range(las-1, las+2):
			if 0<=i<=9:
				q.append(tmp + str(i))
				cnt += 1
				if cnt==K:
					print(q.pop()); return
resolve()

Solution (Python):
k=int(input())
q=[1,2,3,4,5,6,7,8,9]
for i in range(k):
    l=q[i]
    if l%10!=0:
        q.append(10*l+l%10-1)
    q.append(10*l+l%10)
    if l%10!=9:
        q.append(10*l+l%10+1)
print(l)

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

C = [[0]*10 for _ in range(10)]
C[0] = [1]*10
D = {0: [0, 1], 1: [0, 1, 2], 2: [1, 2, 3], 3: [2, 3, 4], 4: [3, 4, 5], 5: [4, 5, 6], 6: [5, 6, 7], 7: [6, 7, 8], 8: [7, 8, 9], 9: [8, 9]}

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

ans = []
temp = K
Flag = True

for i in range(10):
  if Flag:
    for j in range(1, 10):
      temp -= C[i][j]
      if temp <= 0:
        temp += C[i][j]
        r = i
        ans.append(j)
        Flag = False
        break
  else:
    break

def f(x, r):
  temp = x
  r -= 1
  for j in D[ans[-1]]:
    temp -= C[r][j]
    if temp <= 0:
      temp += C[r][j]
      ans.append(j)
      break
  return temp, r

while r >= 1:
  temp, r = f(temp, r)

print("".join([str(i) for i in ans]))

Solution (Python):
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    k = int(input())
    from collections import deque
    que = deque(range(1, 10))
    for i in range(k):
        now = que.popleft()
        r = now%10
        nx = now*10
        if r == 0:
            for j in [0, 1]:
                que.append(nx+r+j)
        elif r == 9:
            for j in [-1, 0]:
                que.append(nx+r+j)
        else:
            for j in [-1, 0, 1]:
                que.append(nx+r+j)
    print(now)

if __name__ == '__main__':
    main()

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

q = deque([1,2,3,4,5,6,7,8,9])
while q:
  a = q.popleft()
  ans.append(a)
  if len(ans) > k:
    break
  tmp = int(str(a)[-1])
  if tmp-1 >= 0:
    q.append(10*a + tmp-1)
  q.append(10*a + tmp)
  if tmp+1 <= 9:
    q.append(10*a + tmp+1)
print(ans[k-1])

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

i = 0

ans = []

def rec(n):
    ans.append(n)
    if n >= 10000000000:
        return
    for j in range(-1, 2, 1):
        add = n % 10 + j
        if 0 <= add <= 9:
            rec(10 * n + add)
for i in range(1, 10):
    rec(i)
ans.sort()
print(ans[k - 1])

Solution (Python):
def nextLunlun(l):
  l[-1]+=1
  for i in range(len(l)-1):
    if abs(l[-i-1]-l[-i-2])>=2 or l[-i-1]==10:
      l[-i-2]+=1
      l[-i-1]=0

  if l[0]>=10:
    l.insert(0,1)
    l[1]=0
    
  for i in range(len(l)-1):
    if abs(l[i]-l[i+1])>=2:
      l[i+1]=max(0,l[i]-1)
  
  return l

l=[0]
n=int(input())

for i in range(n):
  nextLunlun(l)
for num in l:
  print(num,end='')
print()

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

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

while True:
  if len(que)>=k:
    break
  k-=len(que)
  for q in que[:]:
    que.remove(q)
    lq=int(str(q)[-1])
    for r in (lq-1,lq,lq+1):
        if 0<=r<=9:
            que.append(int(str(q)+str(r)))
 
  if len(que)>=k:
    break
 
que.sort()
print(que[k-1])

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

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

digit_len = 1

def df(num, depth):
    if len(str(num)) == depth:
        return [num]

    df_result = []
    tmp_num = int(str(num)[-1])
    tmp = [tmp_num]
    if tmp_num-1>=0:
        tmp.append(tmp_num-1)
    if tmp_num+1<10:
        tmp.append(tmp_num+1)
    for i in tmp:
        df_result.extend(df(int(str(num)+str(i)), depth))
    return df_result

num_list = []
while 1:
    tmp = []
    for i in range(1,10):
        tmp.extend(df(i, digit_len))
    num_list.extend(sorted(tmp))
    if len(num_list)>=k:
        break
    digit_len+=1

print(num_list[k-1])

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

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

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

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

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

i=0
while len(ans)<k:
    v=ans[i]

    mod=v%10

    if mod==0:
        ans.append(10*v+mod)
        ans.append(10*v+mod+1)
    elif mod==9:
        ans.append(10*v+mod-1)
        ans.append(10*v+mod)
    else:
        ans.append(10*v+mod-1)
        ans.append(10*v+mod)
        ans.append(10*v+mod+1)

    i+=1

print(ans[k-1])

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

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

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

i=0
while len(ans)<k:
    v=str(ans[i])
    n=len(v)
    
    v_last=int(v[-1])

    if v_last==0:
        ans.append(int(v+'0'))
        ans.append(int(v+'1'))
    elif v_last==9:
        ans.append(int(v+'8'))
        ans.append(int(v+'9'))
    else:
        ans.append(int(v+str(v_last-1)))
        ans.append(int(v+str(v_last)))
        ans.append(int(v+str(v_last+1)))
    i+=1

print(ans[k-1])

Solution (Python):
k=int(input())
cnt=0
queue=['1','2','3','4','5','6','7','8','9']
while len(queue)>0:
  if cnt==k:
    print(queue[-1][:-1])
    exit()
  now=queue.pop(0)
  if now[-1]=='9':
    queue.append(now+'8')
    queue.append(now+'9')
  elif now[-1]=='0':
    queue.append(now+'0')
    queue.append(now+'1')
  else:
    queue.append(now+str(int(now[-1])-1))
    queue.append(now+str(int(now[-1])))
    queue.append(now+str(int(now[-1])+1))
  cnt+=1

Solution (Python):
def make(i):
    if int(i) > 3234566667:  return
    lun.append(int(i))
    if int(i[-1]) - 1 >= 0:  make(i + str(int(i[-1]) - 1))
    make(i + i[-1])
    if int(i[-1]) + 1 <= 9:  make(i + str(int(i[-1]) + 1))

lun = []
for i in range(1, 10):  make(str(i))
lun = sorted(lun)
print(lun[int(input()) - 1])

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

def make(i):
    if int(i) > 3234566667:  return
    lun.append(int(i))
    if i[-1] == "0":
        temp = i + "0"
        make(temp)
        temp = i + "1"
        make(temp)
    elif i[-1] == "9":
        temp = i + "8"
        make(temp)
        temp = i + "9"
        make(temp) 
    else:
        temp = i + str(int(i[-1]) - 1)
        make(temp)
        temp = i + i[-1]
        make(temp)   
        temp = i + str(int(i[-1]) + 1)
        make(temp)
        
lun = []
for i in range(1, 10):
    make(str(i))
lun = sorted(lun)
ans = lun[K - 1]
print(ans)

Solution (Python):
from collections import deque
K=int(input())
d=deque()
for i in range(1,10):
  d.append(i)
ans=0
while ans!=K-1:
  ans+=1
  x=d.popleft()
  if x%10!=0:
    d.append(10*x+x%10-1)
  d.append(10*x+x%10)
  if x%10!=9:
    d.append(10*x+x%10+1)
print(d.popleft())

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

runrun_table = [[0 for _ in range(10)] for _ in range(10)]

for i in range(10):
    runrun_table[0][i] = 1
for keta in range(1, 10):
    for i in range(10):
        if i == 0:
            runrun_table[keta][i] = runrun_table[keta - 1][i] + \
                                    runrun_table[keta - 1][i + 1]
        elif i == 9:
            runrun_table[keta][i] = runrun_table[keta - 1][i - 1] + \
                                    runrun_table[keta - 1][i]
        else:
            runrun_table[keta][i] = runrun_table[keta - 1][i - 1] + \
                                    runrun_table[keta - 1][i] + \
                                    runrun_table[keta - 1][i + 1]

keta = 0
ans = ''
while sum(runrun_table[keta][1:]) < K:
    K -= sum(runrun_table[keta][1:])
    keta += 1

for piv in range(1, 10):
    if runrun_table[keta][piv] >= K:
        ans += str(piv)
        keta -= 1
        break
    K -= runrun_table[keta][piv]

while keta >= 0:
    if piv == 0:
        piv_range = [0, 1]
    elif piv == 9:
        piv_range = [8, 9]
    else:
        piv_range = range(piv-1, piv+2)
    for piv in piv_range:
        if runrun_table[keta][piv] >= K:
            ans += str(piv)
            keta -= 1
            break
        K -= runrun_table[keta][piv]

print(ans)

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

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

def next_n(n):
    if n == 0:
        return [0, 1]
    elif n == 9:
        return [8, 9]
    else:
        return [n-1, n, n+1]

for _ in range(K-1):
    now = q.popleft()
    for next_ in next_n(now%10):
        q.append(now*10 + next_)

print(q[0])