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
que = deque([i for i in range(1,10)])
n = int(input())

for i in range(n):
    x = que.popleft()
    xl = [x%10-1, x%10,x%10 + 1]
    for j in xl:
        if j == -1 or j == 10:
            continue
        else:
            que.append(10*x+j)
        
print(x)

Solution (Python):
import queue
count=9
target=int(input())
q=queue.Queue()
for i in range(1,10):
    q.put(i)
if count>=target:
    print(target)

if count<target:
    while(1):
        a=q.get()
        if a%10!=0:
            q.put(a*10+a%10-1)
            count+=1
            if count==target:
                print(a*10+a%10-1)
                break
        q.put(a*10+a%10)
        count+=1
        if count==target:
            print(a*10+a%10)
            break
        if a%10!=9:
            q.put(a*10+a%10+1)
            count+=1
            if count==target:
                print(a*10+a%10+1)
                break

Solution (Python):
from collections import deque

K = int(input())

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

    result = []

    while len(result) <= n:
        x = q.popleft()
        result.append(x)
        m = x % 10
        if m == 0:
            q.append(x * 10 + m)
            q.append(x*10+ m +1)
        elif m == 9:
            q.append(x*10 + m - 1)
            q.append(x * 10 + m)
        else:
            q.append(x*10 + m - 1)
            q.append(x * 10 + m)
            q.append(x*10 + m + 1)

    print(result[n-1])


calculate(K)

Solution (Python):
kk = int(input())
if kk < 10:
    print(kk)
    exit()
 
 
dp = [[0] * 10 for _ in range(15)]
dp[0] = [1] * 10
for i in range(14):
    
    for j in range(10):
        for k in range(-1, 2):
            if not (0 <= j + k < 10):
                continue
            dp[i + 1][j + k] += dp[i][j]
 
a = 0
for i in range(15):
    if a+sum(dp[i][1:]) >= kk:
        break
    a += sum(dp[i][1:])
 
ii = i
 
 
for j in range(1, 10):
    if a + dp[i][j] >= kk:
        kk -= a
        break
    a += dp[i][j]
 
ans = j
for i in reversed(range(ii)):
    a = 0
    for k in range(-1, 2):
        if not (0 <= j + k < 10):
            continue
        if a + dp[i][j + k] >= kk:
            kk -= a
            j = j + k
            ans = ans * 10 + j
 
            break
        a += dp[i][j + k]
 
 
print(ans)

Solution (Python):
from collections import deque

k = int(input())

ll = [x for x in range(1, 10)]
q = deque(ll)

cnt = 0

while True:
    n = q.popleft()
    mod = n % 10
    if mod == 0:
        q.append(n * 10 + mod)
        q.append(n * 10 + mod + 1)
    elif 1 <= mod <= 8:
        q.append(n * 10 + mod - 1)
        q.append(n * 10 + mod)
        q.append(n * 10 + mod + 1)
    else:  
        q.append(n * 10 + mod - 1)
        q.append(n * 10 + mod)

    cnt += 1
    if cnt == k:
        print(n)
        exit(0)

Solution (Python):

import sys
from collections import deque
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(K: int):

    h = deque([])

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

    for i in range(K-1):
        s = h.popleft()
        for j in range(-1, 2):
            add = (s % 10)+j
            if 0 <= add <= 9:
                h.append(s*10+add)
    print(h.popleft())
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  
    solve(K)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)  
to_index = lambda x: int(x) - 1  
print_list_in_2D = lambda x: print(*x, sep="\n")  


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

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())


def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))


def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

K = input_int()

if K < 10:  
    print(K)
else:  
    dq = deque([i for i in range(1, 10)])
    count = 0
    while True:
        x = dq.popleft()
        count += 1
        if count == K:
            print(x)
            exit()
        d = x % 10
        if d != 0:
            dq.append(10 * x + d - 1)
        dq.append(10 * x + d)
        if d != 9:
            dq.append(10 * x + d + 1)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(K: int):

    X = set()

    def rec(keta, val):
        X.add(val)
        if keta == 10:
            return

        for j in range(-1, 2):
            add = (val % 10)+j
            if add >= 0 and add <= 9:
                rec(keta+1, val*10+add)

    for i in range(1, 10):
        rec(1, i)
    X = sorted(X)
    print(X[K-1])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  
    solve(K)


if __name__ == '__main__':
    main()

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

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):
    a = d.popleft()
    l = [a%10-1, a%10, a%10+1]
    for j in l:
        if j==-1 or j==10:
            continue
        d.append(a*10 + j)

print(a)

Solution (Python):
from collections import deque
k = int(input())
d = deque([1,2,3,4,5,6,7,8,9])

ans = []
while len(ans) < k:
    a = d.popleft()
    ans.append(a)
    l = [a%10-1, a%10, a%10+1]
    for i in l:
        if i==-1 or i==10:
            continue
        d.append(a*10 + i)

print(ans[k-1])

Solution (Python):
def abs(x):
    if x >= 0:
        return x;
    else:
        return -x;

def Next(v, n):
    list = [];
    for i in range(n - 1, -1, -1):
        if v[i] != 9 and (i == 0 or abs(v[i - 1] - (v[i] + 1)) <= 1):
            for j in range(i):
                list.append(v[j]);
            list.append(v[i] + 1);
            for j in range(i + 1, n):
                list.append(max(list[j - 1] - 1, 0));
            return list;
    list.append(1);
    for i in range(n):
        list.append(0);
    return list;

k = int(input());

curr = [];
curr.append(0);

for i in range(k):
    curr = Next(curr, len(curr));
    

for i in curr:
    print(i, end = "");

Solution (Python):
import queue

K = int(input())

q = queue.Queue()

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

for i in range(K-1):
  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(q.get())

Solution (Python):
K=int(input())
A=[1,2,3,4,5,6,7,8,9]
for _ in range(K-1):
    if K <= len(A): break
    K -= len(A)
    B=[]
    A,B=B,A
    for b in B:
        if b%10!=0: A.append(10*b+(b%10-1))
        A.append(10*b+b%10)
        if b%10!=9: A.append(10*b+(b%10+1))
print(A[K-1])

Solution (Python):
import sys
import heapq
k = int(input())
q = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 0
while q:
    cur = heapq.heappop(q)
    count += 1
    if (count == k):
        print(cur)
        sys.exit()
    else:
        if (cur % 10 != 0):
            heapq.heappush(q, (cur*10) + (cur%10) - 1)
        if (cur % 10 != 9):
            heapq.heappush(q, (cur * 10) + (cur % 10) + 1)
        heapq.heappush(q, (cur * 10) + (cur % 10))

Solution (Python):
from collections import deque
que = deque()
L = []
k = int(input())
for i in range(1, 10):
  L.append(str(i))
  que.append(str(i))
while len(L) < k:
  top = que.popleft()
  e = int(top[-1])
  for i in range(max(e-1, 0), min(e+2, 10)):
    x = top + str(i)
    L.append(x)
    que.append(x)
ans = L[k-1]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
L = []
def lunlun(x, cnt, c):
  if cnt == 10:
    L.append(int(x))
    return
  e = int(x[-1])
  if c:
    for i in range(max(e-1, 0), min(e+2, 10)):
      lunlun(x+str(i), cnt+1, 1)
  else:
    lunlun(x+"0", cnt+1, 0)
    for i in range(1, 10):
      lunlun(x+str(i), cnt+1, 1)
lunlun("0", 1, 0)
for i in range(1, 10):
  lunlun(str(i), 1, 1)

k = int(input())
ans = L[k]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
L = []
def lunlun(x, cnt, c):
  if cnt == 10:
    L.append(int(x))
    return
  e = int(x[-1])
  if c:
    for i in range(max(e-1, 0), min(e+2, 10)):
      lunlun(x+str(i), cnt+1, 1)
  else:
    lunlun(x+"0", cnt+1, 0)
    for i in range(1, 10):
      lunlun(x+str(i), cnt+1, 1)
lunlun("0", 1, 0)
for i in range(1, 10):
  lunlun(str(i), 1, 1)
L.sort()

k = int(input())
ans = L[k]
print(ans)

Solution (Python):
from collections import deque
k = int(input())
Q = deque()
for i in range(1, 10):
  Q.append(i)

for _ in range(k-1):
  a = Q.popleft()
  d = a % 10
  if d != 0:
    Q.append(10 * a + d - 1)
  Q.append(10 * a + d)
  if d != 9:
    Q.append(10 * a + d + 1)

print(Q.popleft())

Solution (Python):

import copy

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

    if K <= 9:
        print(K)
        return

    que = [i for i in range(1, 10)]
    cnt = 9

    while True:
        tmp_que = copy.deepcopy(que)
        que = []
        for i in tmp_que:
            a = i%10
            for j in range(a-1, a+2):
                if j < 0 or j > 9:
                    continue
                cnt += 1
                new = i*10+j
                if K == cnt:
                    print(new)
                    return
                que.append(new)


if __name__ == "__main__":
    solve()

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

import queue

q = queue.Queue()
initial_number = [1,2,3,4,5,6,7,8,9]
for i in initial_number:
    q.put(i)

count = 0
while True:
    x = q.get()
    count += 1
    if count == K:
        print(x)
        break
    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)

Solution (Python):
K = int(input())
Q = [i for i in range(1, 10)]
k = 0
for q in Q:
  if k >= K:
    break
  r = q%10
  if r != 0:
    Q.append(q*10 + r - 1)
    k += 1
  Q.append(q*10 + r)
  k += 1
  if r != 9:
    Q.append(q*10 + r + 1)
    k += 1
print(Q[K-1])

Solution (Python):


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


def dfs(x):
    if x<= 3234566667:
        lunlun_arr.append(x)
        for i in range(10):
            if abs(x%10-i)<=1:
                dfs(10*x + i)
    return lunlun_arr

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

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

Solution (Python):

import sys

def next_lunlun(x):
    K = len(x)
    if len(x) == 1:
        return str(int(x) + 1)
    elif x[-1] == '9':
        next =  next_lunlun(x[:-1])
        if int(next[-1]) - 1 >= 0:
            return next + str(int(next[-1]) - 1)
        else:
            return next + '0'
    elif x[-2] >= x[-1]:
        return x[:-1] + str(int(x[-1]) + 1)
    elif x[-2] < x[-1]:
        next = next_lunlun(x[:-1])
        if int(next[-1]) - 1 >= 0:
            return next + str(int(next[-1]) - 1)
        else:
            return next + '0'


def solve(K: int):
    x = '0'
    for k in range(K):
        x = next_lunlun(x)
    print(x)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  
    solve(K)

if __name__ == '__main__':
    main()

Solution (Python):
a = [1,2,3,4,5,6,7,8,9]
i = -1
N = int(input())

while True:
    if  len(a) >= N:
        print(a[N-1])
        break
    i = i + 1
    n = int(str(a[i])[-1])
    x = a[i]*10 + n-1
    y = a[i]*10 + n
    z = a[i]*10 + n+1
    if n != 9 and n != 0:
        w = (x,y,z)
        a.extend(w)
    elif n == 9:
        w = (x,y)
        a.extend(w)
    elif n == 0:
        w = (y,z)
        a.extend(w)

Solution (Python):

import copy

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

    if K <= 9:
        print(K)
        return

    que = [i for i in range(1, 10)]
    cnt = 9

    while True:
        tmp_que = copy.deepcopy(que)
        que = []
        for i in tmp_que:
            a = i%10
            if 0 <= (a-1) <= 9:
                cnt += 1
                new = i*10 + (a-1)
                if K == cnt:
                    print(new)
                    return
                que.append(new)
            if 0 <= a <= 9:
                cnt += 1
                new = i*10 + a
                if K == cnt:
                    print(new)
                    return
                que.append(new)
            if 0 <= (a+1) <= 9:
                cnt += 1
                new = i*10 + (a+1)
                if K == cnt:
                    print(new)
                    return
                que.append(new)



if __name__ == "__main__":
    solve()

Solution (Python):









import os
import sys
from collections import deque

def main():
    K=int(input())
    Q=deque()
    for i in range(1,10):
        Q.append(i)

    count=0
    while Q:
        count+=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)
        if count==K:
            print(x)
            return


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin, stdout
from functools import lru_cache
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()

def num_digs(n):
	return len(str(n))

@lru_cache(None)
def lunlun(n, pos, tight, prev):
	if pos >= len(n):
		return 1
	md = n[pos] if tight else 9
	sd = 1 if pos == 0 else 0
	count = 0
	for d in range(sd, md + 1):
		new_tight = 1 if tight and d == n[pos] else 0
		if (pos == 0) or (d in {prev - 1, prev, prev + 1}):
			count += lunlun(n, pos  + 1, new_tight, d)
	return count 

def lunlun2(n):
	ans = 0
	for i in range(1, num_digs(n)):
		tupn = tuple(9 for _ in range(i))
		pt = lunlun(tupn, 0, 1, 0)
		ans += pt
	tupn = tuple(int(x) for x in str(n))
	ans += lunlun(tupn, 0, 1, 0)
	return ans	

def main():
	k = int(rl())
	n, jump = 10**19, 10**19
	while jump >= 1:
		while n - jump >= 0 and lunlun2(n - jump) >= k:
			n -= jump
		jump //= 2
	stdout.write(str(n));stdout.write("\n")
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
n = int(input())
D = []

def FindOtvet(i, j, otv):
    if i == 0:
        return ''
    if j == 0:
        if (otv + D[i - 1][j]) < n:
            otv += D[i - 1][j]
            return str(j + 1) + FindOtvet(i - 1, j + 1, otv)
        else:
            return str(j) + FindOtvet(i - 1, j, otv)
    elif j == 9:
        if (otv + D[i - 1][j - 1]) < n:
            otv += D[i - 1][j - 1]
            return str(j) + FindOtvet(i - 1, j, otv)
        else:
            return str(j - 1) + FindOtvet(i - 1, j - 1, otv)
    else:
        if (otv + D[i - 1][j - 1]) < n:
            otv += D[i - 1][j - 1]
            if (otv + D[i - 1][j]) < n:
                otv += D[i - 1][j]
                return str(j + 1) + FindOtvet(i - 1, j + 1, otv)
            else:
                return str(j) + FindOtvet(i - 1, j, otv)
        else:
            return str(j - 1) + FindOtvet(i - 1, j - 1, otv)

arr = []
if n < 10:
    print(n)
    exit()
for i in range(10):
    arr.append(1)
D.append(arr)
totalSum = 9
i = 1
respI = 0
respJ = 0
while respI == 0 and respJ == 0:
    arr = []
    for j in range(10):
        if j == 0:
            arr.append(D[i - 1][j] + D[i - 1][j + 1])
        elif j < 9:
            arr.append(D[i - 1][j - 1] + D[i - 1][j] + D[i - 1][j + 1])
        else:
            arr.append(D[i - 1][j - 1] + D[i - 1][j])
        if j > 0:
            if (totalSum + arr[j]) >= n:
                respI = i
                respJ = j
                break
            totalSum += arr[j]
    D.append(arr)
    i += 1
respStr = str(respJ)
print(respStr + FindOtvet(respI, respJ, totalSum))

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

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

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


def dfs(x):
    a.append(x)
    if x > 3234566667:
        return
    for i in range(10):
        if abs(x % 10 - i) <= 1:
            dfs(x * 10 + i)


for i in range(1, 10):
    dfs(i)
a = sorted(a)
print(a[k - 1])

Solution (Python):
import queue

k = int(input())
li = [1,2,3,4,5,6,7,8,9]
a = queue.Queue()
for l in li:
  a.put(l)

if k <= 9:
  print(li[k-1])
else:
  n = 9
  f=False
  while True:
    x = a.get()
    for i in [-1, 0, 1]:
      if x%10+i==10 or x%10+i==-1:
        continue
      d = (x+i)%10
      t=x*10+d
      a.put(t)
      n+=1
      if n==k:
        print(t)
        f=True
        break
    if f:
      break

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

from collections import deque
d = [-1,0,1]

que = deque()
for i in range(1,10):
    que.append(i)
 
cnt = 0
while que:
    p = que.popleft()
    cnt += 1
    if cnt == k:
        print(p)
        break
    for i in d:
        if 0 <= int(str(p)[-1]) + i <= 9:
            que.append(int(str(p) + str(int(str(p)[-1]) + i)))

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

l = [[0 for i in range(10)] for j in range(10)]

for j in range(10):
	l[0][j] = 1

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


ai = 0
aj = 0
sum = 0
ret = 0
for i in range(10):
	for j in range(1,10):
		sum += l[i][j]
		if(sum >= k):
			ai = i
			aj = j
			sum -= l[i][j]

			break
	if(ai != 0)or(aj != 0):
		break

ret = aj*(10**ai)
m = aj
for i in range(ai):
	if(ai-1-i < 0):
		break
	if(m != 0):
		sum += l[ai-1-i][m-1]

		if(sum >= k):
			sum -= l[ai-1-i][m-1]
			m = m-1
			ret += m*(10**(ai-1-i))

			continue
	
	sum += l[ai-1-i][m]
	if(sum >= k):
		sum -=l[ai-1-i][m]
		ret += m*(10**(ai-1-i))

		continue
	
	m = m+1
	ret += m*(10**(ai-1-i))



print(ret)

Solution (Python):
from collections import deque

K = int(input())
d = deque()
for i in range(1, 10):
    d.append(i)

cnt = 0
while d:
    tmp = d.popleft()
    cnt += 1
    if cnt == K:
        print(tmp)
        break
    r = tmp % 10
    if r != 0:
        d.append(tmp * 10 + r - 1)
    d.append(tmp * 10 + r)
    if r != 9:
        d.append(tmp * 10 + r + 1)

Solution (Python):
from collections import deque
K = int(input())
q = deque(list(range(1, 10)))
for i in range(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(x)

Solution (Python):
from collections import deque

K = int(input())

q = deque(list(range(1,10)))

for _ in range(K-1):
    p = q.popleft()

    if p%10 > 0:
        q.append(p*10 + p%10 - 1)
    
    q.append(p*10 + p%10)

    if p%10 < 9:
        q.append(p*10 + p%10 + 1)

print(q.popleft())

Solution (Python):
K = int(input())
from collections import deque
que=deque([1,2,3,4,5,6,7,8,9])
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):
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(10*x+x%10-1)
  d.append(10*x+x%10)
  if x%10!=9:
    d.append(10*x+x%10+1)
print(x)

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

L = [1,2,3,4,5,6,7,8,9]
nL = [1,2,3,4,5,6,7,8,9]
nL2 = []

def D1(a):
    if a == 0:
        return [0,1]
    elif a == 9:
        return [8,9]
    else:
        return [a-1,a,a+1]
        
for _ in range(9):

    for l in nL:
        for l2 in D1(int(str(l)[-1])):
            nL2.append(int(str(l)+str(l2)))
    
    
    nL = nL2.copy()
    L += nL
    nL2.clear()
    
    
    
    
    

print(L[K-1])

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

nums = [[] for _ in range(11)]
for x in range(1, 10):
    nums[0].append(x)

def push(x, n):
    global nums, cnt
    nums[x].append(n)
    cnt += 1
    if cnt == K:
        print(n)
        sys.exit()
    

if 1 <= K <= 9:
    print(K)
    sys.exit()

cnt = 9
for x in range(1, 11):
    for n in nums[x - 1]:
        if str(n)[-1] == "0":
            push(x, int(str(n) + "0"))
            push(x, int(str(n) + "1"))
        elif str(n)[-1] == "9":
            push(x, int(str(n) + "8"))
            push(x, int(str(n) + "9"))
        else:
            for i in range(-1, 2):
                push(x, int(str(n) + str(int(str(n)[-1]) + i)))

Solution (Python):
from collections import deque

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

    lunluns = deque(range(1, 10))

    lunlun = -1

    for _ in range(k):
        lunlun = lunluns.popleft()

        ones_place = lunlun % 10
        if ones_place > 0:
            lunluns.append(lunlun * 10 + ones_place -1)
        lunluns.append(lunlun * 10 + ones_place)
        if ones_place < 9:
            lunluns.append(lunlun * 10 + ones_place + 1)
    return lunlun

print(main())

Solution (Python):
from queue import Queue
k = int(input())
q = Queue(maxsize = 10000000)
for i in range(1,10):
    q.put(i)
if(k<10):
    print(k)
else:
    count = 0
    while(count<k-1):
        ele = q.get()
        temp = ele%10
        if(temp-1>=0):
            q.put(int(str(ele)+str(temp-1)))
        q.put(int(str(ele)+str(temp)))
        if(temp+1<=9):
            q.put(int(str(ele)+str(temp+1)))
        count+=1
    print(q.get())

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

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

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

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

Solution (Python):
import sys


import queue

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

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

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

print(x)

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

Solution (Python):
K = int(input())
cand = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
for _ in range(9):
    tmp = []
    for v in cand[-1]:
        if v%10 != 0:
            tmp.append(v*10 + (v%10-1))
        tmp.append(v*10 + (v%10))
        if v%10 != 9:
            tmp.append(v*10 + (v%10+1))
    cand.append(tmp)
ans = []
for i in range(len(cand)):
    for v in cand[i]:
        ans.append(v)
ans = sorted(ans)
print(ans[K-1])

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok

def check(x):
    x = str(x)
    N = len(x)
    dp0 = list2d(N+1, 10, 0)
    dp1 = list2d(N+1, 10, 0)
    a = int(x[0])
    dp0[1][a] = 1
    for j in range(1, a):
        dp1[1][j] = 1
    for i in range(2, N+1):
        for j in range(1, 10):
            dp1[i][j] = 1
    for i, a in enumerate(x):
        a = int(a)
        for j in range(10):
            for k in range(10):
                if abs(j - k) >= 2:
                    continue
                if k > a:
                    dp1[i+1][k] += dp1[i][j]
                elif k == a:
                    dp0[i+1][k] += dp0[i][j]
                    dp1[i+1][k] += dp1[i][j]
                else:
                    dp1[i+1][k] += dp0[i][j]
                    dp1[i+1][k] += dp1[i][j]
    ans = sum(dp0[N]) + sum(dp1[N])
    return ans >= K

K = INT()

res = bisearch_min(0, 10**10, check)
print(res)

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

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

Solution (Python):
from collections import deque
def main():
    K = int(input())
    l = deque([i for i in range(1,10)])
    for i in range(K):
        t = l.popleft()
        u = t % 10
        if u != 0:
            l.append(t * 10 + u - 1)
        l.append(t*10 + u)
        if u != 9:
            l.append(t*10 + u + 1)
    return t
print(main())

Solution (Python):



from collections import deque


K = int(input())



que = deque(list(range(1, 10)))
lunlun_number = 0
for k 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)

    
    lunlun_number = x

print(lunlun_number)

Solution (Python):
k = int(input())
q = [0]*100003
for i in range(9):
    q[i] = i + 1
c = 9
for i in range(k):
    x = q[i]
    y = x % 10
    if y != 0:
        q[c] = 10 * x + y - 1
        c = c + 1
    q[c] = 10 * x + y
    c = c + 1
    if y != 9:
        q[c] = 10 * x + y + 1
        c = c + 1
    if c > k:
        break
print(q[k - 1])

Solution (Python):
def is_count_k(count,n):
    count +=1
    if count == k :
        print(n)
        exit()
    
    return count
def make_tree(G,keta,count):
    num_list = G[keta-2]
    new_list =[]
    for num in num_list:
        r = num%10
        if r != 0 :
            count = is_count_k(count,num*10 + (r-1))
            new_list.append(num*10 + r-1)
        count = is_count_k(count,num*10+r)
        new_list.append(num*10 + r)
        if r != 9:
            count = is_count_k(count,num*10+(r +1))
            new_list.append(num*10+(r +1))
    G.append(new_list)
    make_tree(G,keta+1,count)
k = int(input())
G=[]
if k < 10:
    print(k)
    exit()
G.append([1,2,3,4,5,6,7,8,9])
make_tree(G,2,9)

Solution (Python):

import collections


class Solution:
    def solve(self, k):
        lunlunNumbers = [i for i in range(1, 10)]

        for i in range(k-1):
            lunlun = lunlunNumbers[i]

            if lunlun % 10 != 0:
                lunlunNumbers.append(lunlun * 10 + lunlun % 10 - 1)

            lunlunNumbers.append(lunlun * 10 + lunlun % 10)

            if lunlun % 10 != 9:
                lunlunNumbers.append(lunlun * 10 + lunlun % 10 + 1)

        
        return lunlunNumbers[k-1]


sol = Solution()

k = int(input().strip())
print(sol.solve(k))

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

Lunlun = set()
for a in range(0,10):
    now = a
    Lunlun.add(now)
    for b in range(a-1, a+2):
        if b < 0 or b > 9:
            continue
        now = a +b*10
        Lunlun.add(now)
        for c in range(b-1, b+2):
            if c < 0 or c > 9:
                continue
            now = a +b*10 + c*100
            Lunlun.add(now)
            for d in range(c-1, c+2):
                if d < 0 or d > 9:
                    continue
                now = a +b*10 + c*100 + d*1000
                Lunlun.add(now)
                for e in range(d-1, d+2):
                    if e < 0 or e > 9:
                        continue
                    now = a +b*10 + c*100 + d*1000 + e*10000
                    Lunlun.add(now)
                    for f in range(e-1, e+2):
                        if f < 0 or f > 9:
                            continue
                        now = a +b*10 + c*100 + d*1000 + e*10000 + f*100000
                        Lunlun.add(now)
                        for g in range(f-1, f+2):
                            if g < 0 or g > 9:
                                continue
                            now = a +b*10 + c*100 + d*1000 + e*10000 + f*100000 + g*(10**6)
                            Lunlun.add(now)
                            for h in range(g-1, g+2):
                                if h < 0 or h > 9:
                                    continue
                                now = a +b*10 + c*100 + d*1000 + e*10000 + f*100000 + g*(10**6) + h*(10**7)
                                Lunlun.add(now)
                                for i in range(h-1, h+2):
                                    if i < 0 or i > 9:
                                        continue
                                    now = a +b*10 + c*100 + d*1000 + e*10000 + f*100000 + g*(10**6) + h*(10**7) + i*(10**8)
                                    Lunlun.add(now)
                                    for j in range(i-1, i+2):
                                        if j < 0 or j > 9:
                                            continue
                                        now = a +b*10 + c*100 + d*1000 + e*10000 + f*100000 + g*(10**6) + h*(10**7) + i*(10**8) +j*(10**9)
                                        Lunlun.add(now)


Lunlun = sorted(Lunlun)

ans = Lunlun[k]
print(ans)