AtCoder Beginner Contest 161 - Lunlun Number

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-----
15

-----Sample Output-----
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.

Difficulty: MEDIUM

Starter code:

Solutions:
from collections import deque
k = int(input())
que = deque([i for i in range(1, 10, 1)])
for i in range(k):
	x = que.popleft()
	if x % 10 == 0:
		que.append(x * 10)
		que.append(x * 10 + 1)
	elif x % 10 == 9:
		que.append(x * 10 + 8)
		que.append(x * 10 + 9)
	else:
		que.append(x * 10 + x % 10 - 1)
		que.append(x * 10 + x % 10)
		que.append(x * 10 + x % 10 + 1)
print(x)


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


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

def dfs(x):
	if x >= 3234566667:
		return
	for i in range(max(0, x % 10 - 1), min(10, x % 10 + 2)):
		ans.append(10 * x + i)
		dfs(10 * x + i)
for i in range(1, 10):
	dfs(i)
print(sorted(ans)[k - 1])


from collections import deque
K = int(input())
d = deque(range(1, 10))
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)


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


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


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


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


k = int(input())
if k < 9:
	print(k)
	exit()
t = [i for i in range(1, 10)]
c = 9
while c < k:
	a = t.pop(0)
	for i in range(max(0, a % 10 - 1), min(10, a % 10 + 2)):
		t.append(a * 10 + i)
		c += 1
print(t[-1 - c + k])


k = int(input())
que = [i for i in range(1, 10)]
for i in range(k):
	now = que.pop(0)
	too = now % 10
	if too != 0:
		que.append(now * 10 + too - 1)
	que.append(now * 10 + too)
	if too != 9:
		que.append(now * 10 + too + 1)
print(now)


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

def f(d, now, L):
	L.append(now)
	if d == 10:
		return
	for j in range(-1, 2):
		v = now % 10 + j
		if 0 <= v <= 9:
			f(d + 1, now * 10 + v, L)
for l in range(1, 10):
	f(1, l, L)
L.sort()
print(L[k - 1])


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)


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


k = int(input())
L = list(range(10))
i = 1
while len(L) <= k:
	Li = L[i]
	a = Li % 10
	for b in range(a - 1, a + 2):
		if b < 0 or b > 9:
			continue
		L.append(Li * 10 + b)
	i += 1
print(L[k])


from collections import deque

def main() -> None:
	k = int(input())
	d = deque(list(range(1, 10)))
	for _ in range(k):
		num = d.popleft()
		if num % 10 != 0:
			d.append(num * 10 + (num % 10 - 1))
		d.append(num * 10 + num % 10)
		if num % 10 != 9:
			d.append(num * 10 + (num % 10 + 1))
	print(num)
	return

def __starting_point():
	main()
__starting_point()


from collections import deque
K = int(input())
Q = list(range(1, 10))
for i in range(K):
	x = Q[i]
	y = x % 10
	if y != 0:
		Q.append(10 * x + y - 1)
	Q.append(10 * x + y)
	if y != 9:
		Q.append(10 * x + y + 1)
print(Q[K - 1])


from collections import deque
K = int(input())
que = deque(map(str, range(1, 10)))
while K > 1:
	n = que.popleft()
	K -= 1
	R = int(n[-1])
	for r in (R - 1, R, R + 1):
		if 0 <= r <= 9:
			que.append(n + str(r))
print(que[0])


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


k = int(input())
q = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
x = 9
for i in q:
	if x > 100000:
		break
	x += 1
	a = i[-1]
	for j in [-1, 0, 1]:
		bb = int(a) + j
		if bb < 10 and bb >= 0:
			q.append(i + str(bb))
print(q[k - 1])


k = int(input())
import queue
que = queue.Queue()
for i in range(1, 10):
	que.put(i)
for i in range(1, k + 1):
	ans = que.get()
	keta1 = ans % 10
	if keta1 == 0:
		append_list = [ans * 10, ans * 10 + 1]
	elif keta1 == 9:
		append_list = [ans * 10 + 8, ans * 10 + 9]
	else:
		append_list = [ans * 10 + keta1 - 1, ans * 10 + keta1, ans * 10 + keta1 + 1]
	for ite in append_list:
		que.put(ite)
print(ans)


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


from collections import deque
k = int(input())
d = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
num = [1, 2, 3, 4, 5, 6, 7, 8, 9]
while d:
	now = d.popleft()
	hitoketa = now % 10
	for i in [-1, 0, 1]:
		if 0 <= hitoketa + i <= 9:
			nxt = now * 10 + hitoketa + i
			if nxt <= 3234566667:
				num.append(nxt)
				d.append(nxt)
num.sort()
print(num[k - 1])


import queue
k = int(input())
q = queue.Queue()
num = 0
for i in range(1, 10):
	q.put(i)
while num < k:
	i = q.get()
	l = i % 10
	if l != 0:
		q.put(i * 10 + l - 1)
	q.put(i * 10 + l)
	if l != 9:
		q.put(i * 10 + l + 1)
	num += 1
print(i)


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

def dfs(v, n):
	u = []
	for x in v:
		for d in [-1, 0, 1]:
			if 0 <= x % 10 + d <= 9:
				u.append(x * 10 + x % 10 + d)
	if n + len(u) >= K:
		u.sort()
		print(u[K - n - 1])
	else:
		dfs(u, n + len(u))
dfs(range(1, 10), 9)


from collections import *
d = deque([i for i in range(1, 10)])
for _ in range(int(input())):
	i = d.popleft()
	j = i % 10
	if j != 0:
		d.append(i * 10 - 1 + j)
	d.append(i * 10 + j)
	if j != 9:
		d.append(i * 10 + 1 + j)
print(i)


k = int(input())

def make_lunlun(lunlun_lst):
	ret_lunlun = []
	for num in lunlun_lst:
		num_str = str(num)
		if num_str[-1] != '0':
			num_tmp = num_str + str(int(num_str[-1]) - 1)
			ret_lunlun.append(int(num_tmp))
		if num_str[-1] != '9':
			num_tmp = num_str + str(int(num_str[-1]) + 1)
			ret_lunlun.append(int(num_tmp))
		num_tmp = num_str + num_str[-1]
		ret_lunlun.append(int(num_tmp))
	return ret_lunlun
lunlun_lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
while 1:
	if len(lunlun_lst) < k:
		k -= len(lunlun_lst)
		lunlun_lst = make_lunlun(lunlun_lst)
	else:
		lunlun_lst.sort()
		print(lunlun_lst[k - 1])
		break


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


L = [1] + [0] * 10
for _ in range(1, int(input())):
	for i in range(10):
		if (L[i] - L[i + 1] < 1 or sum(L[i + 1:]) < 1) and L[i] < 9:
			for j in range(i + 1):
				L[j] = max(L[i] + 1 - i + j, 0)
			break
print(sum((l * 10 ** i for (i, l) in enumerate(L))))


import itertools
K = int(input())
dp = [[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
lunlun_cnt = [9]
i = 1
while True:
	dp.append([0] * 10)
	lunlun_cnt_tmp = 0
	for j in range(10):
		if j == 0:
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j + 1]
		elif j == 9:
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
		else:
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1]
		lunlun_cnt_tmp += dp[i][j]
	i += 1
	if lunlun_cnt[-1] + lunlun_cnt_tmp >= K:
		break
	else:
		lunlun_cnt.append(lunlun_cnt[-1] + lunlun_cnt_tmp)
if K <= 9:
	pos = K
	digit = 0
else:
	pos = K - lunlun_cnt[-1]
	digit = len(lunlun_cnt)
cnt = 0
flag = False
keta = [-1, 0, 1]
for i in range(9):
	for keta_shift in itertools.product(keta, repeat=digit):
		flag2 = False
		r = i + 1
		for j in range(digit):
			r += keta_shift[j]
			if r < 0 or r > 9:
				flag2 = True
				break
		if flag2:
			continue
		cnt += 1
		if cnt == pos:
			flag = True
			break
	if flag:
		break
res = [i + 1]
for i in range(digit):
	res.append(res[-1] + keta_shift[i])
print(''.join(list(map(str, res))))


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


k = int(input())
l = list(range(1, 10))
for i in l:
	if len(l) > k:
		break
	for j in range(max(i % 10 - 1, 0), min(i % 10 + 2, 10)):
		l.append(i * 10 + j)
print(l[k - 1])


import collections
K = int(input())
ls = [1, 2, 3, 4, 5, 6, 7, 8, 9]
deq = collections.deque(ls)
i = 0
while i != K:
	x = deq.popleft()
	if x % 10 != 0:
		deq.append(10 * x + x % 10 - 1)
	deq.append(10 * x + x % 10)
	if x % 10 != 9:
		deq.append(10 * x + x % 10 + 1)
	i += 1
print(x)


(_, *s) = range(10)
for v in s:
	(*t,) = range(v * 10 + max(0, v % 10 - 1), v * 10 + min(10, v % 10 + 2))
	s += t * (v < 400000000.0)
print(s[int(input()) - 1])


from collections import deque
D = deque()
for i in range(1, 10):
	D.append(i)
for _ in range(int(input())):
	x = D.popleft()
	y = x % 10
	if y != 0:
		D.append(10 * x + y - 1)
	D.append(10 * x + y)
	if y != 9:
		D.append(10 * x + y + 1)
print(x)


import sys
input = sys.stdin.readline
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)
		return
	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))


k = int(input())
lun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(10 ** 5 + 1):
	if len(lun) >= k:
		break
	di = lun[i] % 10
	for j in range(max(0, di - 1), min(9, di + 1) + 1):
		lun.append(lun[i] * 10 + j)
print(lun[k - 1])


from collections import deque
K = int(input())
d = deque(list(range(1, 10)))
for i in range(K - 1):
	a = d[0]
	b = 10 * a + a % 10
	if a % 10 != 0:
		d.append(b - 1)
	d.append(b)
	if a % 10 != 9:
		d.append(b + 1)
	d.popleft()
print(d[0])


from collections import deque
k = int(input())
lunlun = deque((i for i in range(1, 10)))
for _ in range(k - 1):
	p = lunlun.popleft()
	if p % 10 != 0:
		lunlun.append(10 * p + p % 10 - 1)
	lunlun.append(10 * p + p % 10)
	if p % 10 != 9:
		lunlun.append(10 * p + p % 10 + 1)
print(lunlun.popleft())


k = int(input())
a = []

def dfs(x):
	if x > 3234566667:
		return
	a.append(x)
	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])


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


def dfs(c, l):
	n = list()
	for i in l:
		for j in range(max(0, i % 10 - 1), min(i % 10 + 2, 10)):
			n.append(i * 10 + j)
			c -= 1
			if c == 0:
				return i * 10 + j
	else:
		return dfs(c, n)
K = int(input())
print(K if K < 10 else dfs(K - 9, [1, 2, 3, 4, 5, 6, 7, 8, 9]))


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)


k = int(input())
s = list(range(1, 10))
l = []
while s:
	p = s.pop()
	l.append(p)
	n = p % 10
	for d in range(max(0, n - 1), min(10, n + 2)):
		if p * 10 + d <= 3234566667:
			s.append(p * 10 + d)
l.sort()
print(l[k - 1])


from collections import deque
k = int(input())
q = deque(range(1, 10))
while k:
	k -= 1
	t = q.popleft()
	if t % 10 != 0:
		q.append(10 * t + t % 10 - 1)
	q.append(10 * t + t % 10)
	if t % 10 != 9:
		q.append(10 * t + t % 10 + 1)
print(t)


import sys
import queue
I = input()
K = int(I)
Q = queue.Queue()
for _ in range(1, 10):
	Q.put(_)
x = 0
for _ 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)


k = int(input())
all_lun = []

def dfs(d):
	all_lun.append(d)
	if len(str(d)) == 10:
		return
	for i in [-1, 0, 1]:
		if 0 <= d % 10 + i < 10:
			dfs(d * 10 + d % 10 + i)
for i in range(1, 10):
	dfs(i)
all_lun.sort()
print(all_lun[k - 1])


import queue
q = queue.Queue()
for i in range(1, 10):
	q.put(i)
k = int(input())
a = 0
for i in range(k):
	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(a)


import queue
N = int(input())
Q = [i for i in range(1, 10)]
q = queue.Queue()
for i in Q:
	q.put(i)
count = 0
while count < N:
	n = q.get()
	d = n % 10
	for i in range(max([d - 1, 0]), min([d + 2, 10])):
		q.put(n * 10 + i)
	count += 1
print(n)


from collections import deque
k = int(input())
queue = deque(range(1, 10))
x = 0
for _ in range(k):
	x = queue.popleft()
	if not x % 10 == 0:
		queue.append(10 * x + x % 10 - 1)
	queue.append(10 * x + x % 10)
	if not x % 10 == 9:
		queue.append(10 * x + x % 10 + 1)
print(x)


N = int(input())
import queue
q = queue.Queue()
for i in range(1, 10):
	q.put(i)
while N != 1:
	a = q.get()
	b = a % 10
	c = [10 * a + i for i in range(max(0, b - 1), min(10, b + 2))]
	for j in c:
		q.put(j)
	N -= 1
print(q.get())


K = int(input())
a = list(range(1, 10))
for i in a:
	if len(a) > K:
		break
	x = i % 10
	for j in range(max(0, x - 1), min(x + 2, 10)):
		a.append(i * 10 + j)
print(a[K - 1])


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


from collections import deque
k = int(input())
q = deque(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)


k = int(input())
c = [i for i in range(1, 10)]
for k in range(k + 1):
	n = c[k]
	m = n % 10
	for i in range(-1, 2):
		if 0 <= m + i <= 9:
			c.append(n * 10 + m + i)
print(c[k - 1])


n = int(input())
l = list(range(1, 10))
c = 1
for i in l:
	c += 1
	if c > n:
		print(i)
		break
	for j in range(max(i % 10 - 1, 0), min(i % 10 + 2, 10)):
		l += [i * 10 + j]


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)


from collections import *
d = deque([i for i in range(1, 10)])
for _ in range(int(input())):
	i = d.popleft()
	j = i % 10
	for k in range(max(0, j - 1), min(10, j + 2)):
		d.append(i * 10 + k)
print(i)


from collections import deque
d = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
k = int(input())
cnt = 0
while k > cnt:
	x = d.popleft()
	cnt += 1
	if x % 10 != 0:
		d.append(x * 10 + x % 10 - 1)
	d.append(x * 10 + x % 10)
	if x % 10 != 9:
		d.append(x * 10 + x % 10 + 1)
print(x)


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


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


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


k = int(input())
q = [1, 2, 3, 4, 5, 6, 7, 8, 9]
c = 0
for i in range(k):
	num = q[c]
	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)
	c += 1
print(q[k - 1])


from collections import deque
k = int(input())
dq = deque(list(range(1, 10)))
rep = 0
while rep < k:
	now = dq.popleft()
	rep += 1
	for i in (-1, 0, 1):
		if 0 <= now % 10 + i < 10:
			dq.append(now * 10 + now % 10 + i)
print(now)


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


k = int(input())
lis = [1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 0
while len(lis) < k:
	m = lis[i] % 10
	if m != 0:
		lis.append(int(str(lis[i]) + str(m - 1)))
	lis.append(int(str(lis[i]) + str(m)))
	if m != 9:
		lis.append(int(str(lis[i]) + str(m + 1)))
	i += 1
print(lis[k - 1])


k = int(input())
lunlun = list(range(1, 10))
for i in range(k - 1):
	a = lunlun[i]
	b = a * 10 + a % 10
	if a % 10 != 0:
		lunlun.append(b - 1)
	lunlun.append(b)
	if a % 10 != 9:
		lunlun.append(b + 1)
print(lunlun[k - 1])


K = int(input())
tab = [[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], [0, 2, 3, 3, 3, 3, 3, 3, 3, 3, 2, 0], [0, 5, 8, 9, 9, 9, 9, 9, 9, 8, 5, 0], [0, 13, 22, 26, 27, 27, 27, 27, 26, 22, 13, 0], [0, 35, 61, 75, 80, 81, 81, 80, 75, 61, 35, 0], [0, 96, 171, 216, 236, 242, 242, 236, 216, 171, 96, 0], [0, 267, 483, 623, 694, 720, 720, 694, 623, 483, 267, 0], [0, 750, 1373, 1800, 2037, 2134, 2134, 2037, 1800, 1373, 750, 0], [0, 2123, 3923, 5210, 5971, 6305, 6305, 5971, 5210, 3923, 2123, 0], [0, 6046, 11256, 15104, 17486, 18581, 18581, 17486, 15104, 11256, 6046, 0]]
seq = [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 2, 8, 9, 9, 9, 9, 9, 9, 8, 5, 22, 26, 27, 27, 27, 27, 26, 22, 13, 61, 75, 80, 81, 81, 80, 75, 61, 35, 171, 216, 236, 242, 242, 236, 216, 171, 96, 483, 623, 694, 720, 720, 694, 623, 483, 267, 1373, 1800, 2037, 2134, 2134, 2037, 1800, 1373, 750, 3923, 5210, 5971, 6305, 6305, 5971, 5210, 3923, 2123, 11256, 15104, 17486, 18581, 18581, 17486, 15104, 11256, 6046]
i = 1
while K > seq[i - 1]:
	K -= seq[i - 1]
	i += 1
if i % 9 != 0:
	d = i // 9
	num = i % 9
else:
	d = (i - 1) // 9
	num = 9
letter = [str(num)]
while d >= 1:
	if K <= tab[d - 1][num]:
		num -= 1
	elif tab[d - 1][num] < K <= tab[d - 1][num] + tab[d - 1][num + 1]:
		K -= tab[d - 1][num]
	else:
		K -= tab[d - 1][num] + tab[d - 1][num + 1]
		num += 1
	d -= 1
	letter.append(str(num))
print(''.join(letter))


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


k = int(input())
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
while True:
	if k <= len(a):
		print(a[k - 1])
		return
	k -= len(a)
	b = list()
	(a, b) = (b, a)
	for x in b:
		for i in range(-1, 2):
			d = x % 10 + i
			if d < 0 or d > 9:
				continue
			nx = x * 10 + d
			a.append(nx)


lun_array = [i for i in range(1, 10)]
k = int(input())
num_array = 9
seed_index = 0
while num_array < k:
	if lun_array[seed_index] % 10 != 0:
		lun_array.append(lun_array[seed_index] * 10 + lun_array[seed_index] % 10 - 1)
		num_array += 1
	lun_array.append(lun_array[seed_index] * 10 + lun_array[seed_index] % 10)
	num_array += 1
	if lun_array[seed_index] % 10 != 9:
		lun_array.append(lun_array[seed_index] * 10 + lun_array[seed_index] % 10 + 1)
		num_array += 1
	seed_index += 1
print(lun_array[k - 1])


K = int(input())
lun = list(range(1, 10))
for n in range(K):
	lm = lun[n] % 10
	if lm > 0:
		lun.append(lun[n] * 10 + (lm - 1))
	lun.append(lun[n] * 10 + lm)
	if lm < 9:
		lun.append(lun[n] * 10 + (lm + 1))
print(lun[K - 1])


K = int(input())
l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in l:
	if i % 10 == 0:
		l += [i * 10, i * 10 + 1]
	if i % 10 == 9:
		l += [i * 10 + 8, i * 10 + 9]
	if 0 < i % 10 < 9:
		l += [i * 10 + (i - 1) % 10, i * 10 + i % 10, i * 10 + (i + 1) % 10]
	if len(l) > 10 ** 5:
		break
print(l[K - 1])


K = int(input())
N = 0
lun = list(range(1, 10))
while 1:
	N += 1
	x = lun[N - 1]
	if x % 10 != 0:
		lun.append(10 * x + x % 10 - 1)
	lun.append(10 * x + x % 10)
	if x % 10 != 9:
		lun.append(10 * x + x % 10 + 1)
	if N == K:
		break
print(lun[N - 1])


k = int(input())
lunList = [i for i in range(1, 10)]
for i in range(k - 9):
	x = lunList[i]
	for j in range(-1, 2):
		d = x % 10 + j
		if 0 <= d <= 9:
			lunList.append(10 * x + d)
print(lunList[k - 1])


from sys import setrecursionlimit
setrecursionlimit(10 ** 8)
k = int(input())
if k <= 10:
	print(k)
else:

	def dp(i):
		if i == 10:
			return 10
		N = str(dp(i - 1))
		ans = 0
		l = len(N)
		for (j, n) in enumerate(N[::-1]):
			if j == l - 1:
				if int(n) != 9:
					x = int(n) + 1
					ans = 0
					l -= 1
					while x != 0 and l >= 0:
						ans += x * 10 ** l
						x -= 1
						l -= 1
					return ans
				else:
					return 10 ** l
			if n == '9':
				continue
			if int(N[l - j - 2]) - int(n) >= 0:
				ans = int(N[:l - j - 1]) * 10 ** (j + 1)
				l = j
				x = int(n) + 1
				while x != 0 and l >= 0:
					ans += x * 10 ** l
					x -= 1
					l -= 1
				return ans
	print(dp(k))


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


N = int(input()) + 1
Ans = []

def dfs(depth, p):
	if depth == 0:
		Ans.append(p)
		if len(Ans) == N:
			print(p)
			return
		return
	if p != 0:
		for digit in range(max(0, p % 10 - 1), min(10, p % 10 + 2)):
			dfs(depth - 1, p * 10 + digit)
	else:
		for digit in range(10):
			dfs(depth - 1, p * 10 + digit)
dfs(10, 0)


from collections import deque
k = int(input())
D = deque()
for i in range(1, 10):
	D.append(i)
for _ in range(k):
	d = D.popleft()
	r = d % 10
	if r != 0:
		D.append(d * 10 + r - 1)
	D.append(d * 10 + r)
	if r != 9:
		D.append(d * 10 + r + 1)
print(d)


from heapq import heappush, heappop
K = int(input())
hq = []
for i in range(1, 10):
	heappush(hq, i)
cnt = 0
while cnt < K:
	x = heappop(hq)
	cnt += 1
	for i in [-1, 0, 1]:
		d = x % 10 + i
		if 0 <= d <= 9:
			heappush(hq, x * 10 + d)
print(x)


import sys
from collections import deque, defaultdict, namedtuple
import heapq
from math import sqrt, factorial, gcd, ceil, atan, pi

def input():
	return sys.stdin.readline()[:-1]
import string
import operator
import random
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
MOD = int(1000000000.0) + 7
INF = float('inf')

def print_lines(data):
	sys.stdout.write('\n'.join((str(x) for x in data)))

def solve():
	n = int(input())
	q = deque([x for x in range(1, 10)])
	cur = 0
	while n:
		cur = q.popleft()
		last = cur % 10
		if last == 0:
			q.append(cur * 10)
			q.append(cur * 10 + 1)
		elif last == 9:
			q.append(cur * 10 + last - 1)
			q.append(cur * 10 + last)
		else:
			q.append(cur * 10 + last - 1)
			q.append(cur * 10 + last)
			q.append(cur * 10 + last + 1)
		n -= 1
	print(cur)
T = 1
for case in range(1, T + 1):
	ans = solve()


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


K = int(input())
l = list(range(1, 10))
for x in l:
	if x > 3234566667:
		break
	back = int(str(x)[-1])
	for b in [back - 1, back, back + 1]:
		if 0 <= b <= 9:
			l.append(10 * x + b)
print(l[K - 1])


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)


k = int(input())
from collections import deque
d = deque(range(1, 10))
i = 0
while d:
	l = d.popleft()
	i += 1
	if i == k:
		print(l)
		return
	if l % 10 > 0:
		d.append(l * 10 + l % 10 - 1)
	d.append(l * 10 + l % 10)
	if l % 10 < 9:
		d.append(l * 10 + l % 10 + 1)


K = int(input())
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
I = 0
while I <= K:
	if not A[I] % 10 == 0:
		A.append(A[I] % 10 + 10 * A[I] - 1)
	A.append(A[I] % 10 + 10 * A[I])
	if not A[I] % 10 == 9:
		A.append(A[I] % 10 + 10 * A[I] + 1)
	if len(A) >= K:
		break
	I += 1
print(A[K - 1])


def main():

	def rec(d: int, val: int, all: list):
		all.append(val)
		if d == 10:
			return
		for j in range(-1, 2):
			add = val % 10 + j
			if add >= 0 and add <= 9:
				rec(d + 1, val * 10 + add, all)
	k = int(input())
	all = []
	for v in range(1, 10):
		rec(1, v, all)
	print(sorted(all)[k - 1])

def __starting_point():
	main()
__starting_point()


k = int(input())
ans = [1, 2, 3, 4, 5, 6, 7, 8, 9]
now = 0
for i in ans:
	if now == 100000:
		break
	x = int(str(i)[-1])
	for j in range(max(0, x - 1), min(x + 2, 10)):
		mini_ans = i * 10 + j
		ans.append(mini_ans)
		now += 1
print(ans[k - 1])


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


from itertools import accumulate
K = int(input())
(a0, a1, a2, a3, a4, a5, a6, a7, a8, a9) = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
Alist = [[a0, a1, a2, a3, a4, a5, a6, a7, a8, a9]]
sumation = 9
sumations = [0, 9]
digit = 0
ans = []
while sumation < K:
	an0 = a0 + a1
	an1 = a0 + a1 + a2
	an2 = a1 + a2 + a3
	an3 = a2 + a3 + a4
	an4 = a3 + a4 + a5
	an5 = a4 + a5 + a6
	an6 = a5 + a6 + a7
	an7 = a6 + a7 + a8
	an8 = a7 + a8 + a9
	an9 = a8 + a9
	(a0, a1, a2, a3, a4, a5, a6, a7, a8, a9) = (an0, an1, an2, an3, an4, an5, an6, an7, an8, an9)
	sumation += a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9
	digit += 1
	Alist.append([a0, a1, a2, a3, a4, a5, a6, a7, a8, a9])
	sumations.append(sumation)
K -= sumations[-2]
for num in range(9):
	l = list(accumulate(Alist[-1]))
	if l[num] - l[0] < K <= l[num + 1] - l[0]:
		K -= l[num] - l[0]
		break
ans.append(str(num + 1))
for i in range(digit):
	for n in range(max(0, num), min(num + 3, 10)):
		K -= Alist[-i - 2][n]
		if K <= 0:
			K += Alist[-i - 2][n]
			break
	num = n - 1
	ans.append(str(num + 1))
print(int(''.join(ans)))


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


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


from collections import deque
K = int(input())
q = deque([i for i in range(1, 10)])
for _ in range(K - 1):
	num = q.popleft()
	for i in range(-1, 2):
		if 0 <= int(str(num)[-1]) + i <= 9:
			q.append(num * 10 + int(str(num)[-1]) + i)
print(q[0])


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


from collections import deque
a = deque(list(range(1, 10)))
for _ in range(int(input())):
	i = a.popleft()
	m = i % 10
	i = 10 * i + m
	if m > 0:
		a.append(i - 1)
	a.append(i)
	if m < 9:
		a.append(i + 1)
print(i // 10)


from collections import deque
K = int(input())
q = deque()
for i in range(1, 10):
	q.append(i)
ans = 0
if K >= 10:
	cnt = 9
	while len(q) > 0:
		current = q.popleft()
		dn = [-1, 0, 1]
		for i in dn:
			if current % 10 + i < 0 or current % 10 + i > 9 or cnt >= K:
				continue
			q.append(current * 10 + current % 10 + i)
			cnt += 1
	else:
		ans = current
else:
	ans = K
print(ans)


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)
		return
	b = a % 10
	for i in (-1, 0, 1):
		if 0 <= b + i <= 9:
			q.append(a * 10 + b + i)


from collections import deque
K = int(input())
queue = deque(list(range(1, 10)))
for i in range(K):
	k = queue.popleft()
	mod = k % 10
	for diff in range(mod - 1, mod + 2):
		if diff < 0 or 9 < diff:
			continue
		queue.append(10 * k + diff)
print(k)


k = int(input())
a = []

def dfs(v):
	if v > 3234566667:
		return
	a.append(v)
	for i in range(max(0, v % 10 - 1), min(v % 10 + 2, 10)):
		dfs(10 * v + i)
for i in range(1, 10):
	dfs(i)
a.sort()
print(a[k - 1])


import queue
K = int(input())
L = queue.Queue()
for i in range(1, 10):
	L.put(i)
for i in range(K - 1):
	x = L.get()
	p = 10 * x
	m = x % 10
	if m != 0:
		L.put(p + m - 1)
	L.put(p + m)
	if x % 10 != 9:
		L.put(p + m + 1)
print(L.get())


k = int(input())
a = [i for i in range(1, 10)]
for x in a:
	if k <= len(a):
		break
	if x % 10 != 0:
		a.append(10 * x + x % 10 - 1)
	a.append(10 * x + x % 10)
	if x % 10 != 9:
		a.append(10 * x + x % 10 + 1)
print(a[k - 1])


from collections import deque
K = int(input())
q = deque([i for i in range(1, 10)])
for _ in range(K - 1):
	x = deque.popleft(q)
	a = x % 10
	if a != 0 and a != 9:
		deque.append(q, x * 10 + a - 1)
		deque.append(q, x * 10 + a)
		deque.append(q, x * 10 + a + 1)
	elif a == 0:
		deque.append(q, x * 10)
		deque.append(q, x * 10 + 1)
	else:
		deque.append(q, x * 10 + 8)
		deque.append(q, x * 10 + 9)
print(deque.popleft(q))


from collections import deque
k = int(input())
s = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
for i in range(k):
	c = s.popleft()
	d = int(str(c)[-1])
	for j in range(max(0, d - 1), min(10, d + 2)):
		s.append(int(str(c) + str(j)))
print(c)


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)


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


def dfs(d: int, v: int, all: list):
	if d == 11:
		return
	all.append(v)
	if list(str(v))[-1] == '0':
		dfs(d + 1, 10 * v + int(list(str(v))[-1]) + 1, all)
		dfs(d + 1, 10 * v + int(list(str(v))[-1]), all)
	elif list(str(v))[-1] == '9':
		dfs(d + 1, 10 * v + int(list(str(v))[-1]) - 1, all)
		dfs(d + 1, 10 * v + int(list(str(v))[-1]), all)
	else:
		dfs(d + 1, 10 * v + int(list(str(v))[-1]) + 1, all)
		dfs(d + 1, 10 * v + int(list(str(v))[-1]), all)
		dfs(d + 1, 10 * v + int(list(str(v))[-1]) - 1, all)
k = int(input())
all = []
for i in range(1, 10):
	dfs(1, i, all)
all.sort()
print(all[k - 1])


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)

def __starting_point():
	main()
__starting_point()


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


k = int(input())
a = [str(i) for i in range(1, 10)]
cnt = 9
if k <= 9:
	print(k)
	return
else:
	while True:
		b = a.pop(0)
		c = int(b) % 10
		d = c + 1
		e = c - 1
		if b[-1] == '0':
			a.append(str(b) + str(c))
			a.append(str(b) + str(d))
			cnt += 2
		elif b[-1] == '9':
			a.append(str(b) + str(e))
			a.append(str(b) + str(c))
			cnt += 2
		else:
			a.append(str(b) + str(e))
			a.append(str(b) + str(c))
			a.append(str(b) + str(d))
			cnt += 3
		if cnt >= k:
			break
print(a[-(cnt - k + 1)])


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


cur = []

def recur(n):
	if n > 10 ** 10:
		return
	cur.append(n)
	for i in range(10):
		if abs(n % 10 - i) <= 1:
			recur(10 * n + i)
for i in range(1, 10):
	recur(i)
cur.sort()
n = int(input())
print(cur[n - 1])


K = int(input())
num = list(range(1, 10))
for i in range(K):
	a = num[i]
	b = 10 * a + a % 10
	if a % 10 != 0:
		num.append(b - 1)
	num.append(b)
	if a % 10 != 9:
		num.append(b + 1)
print(num[K - 1])


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)
	return
else:
	while True:
		if k < l_sum[i]:
			break
		i += 1
	k = k - l_sum[i - 1]
	ans = []
	for j in reversed(list(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
		elif 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)
		elif 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))


K = int(input())
idx = 0
l = list(range(1, 10))
while len(l) < K:
	m = l[idx]
	for i in (-1, 0, 1):
		n = m % 10 + i
		if n in {-1, 10}:
			continue
		tmp = m * 10 + n
		l.append(tmp)
	idx = idx + 1
print(l[K - 1])


import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf, log10
from copy import deepcopy
import numpy as np
import scipy as sp
INF = inf
MOD = 1000000007
k = int(input())
tmp = deque(list(range(1, 10)))
res = 0
for i in range(k - 1):
	x = tmp.popleft()
	if x % 10 == 0:
		tmp.append(10 * x + x % 10)
		tmp.append(10 * x + x % 10 + 1)
	elif x % 10 == 9:
		tmp.append(10 * x + x % 10 - 1)
		tmp.append(10 * x + x % 10)
	else:
		tmp.append(10 * x + x % 10 - 1)
		tmp.append(10 * x + x % 10)
		tmp.append(10 * x + x % 10 + 1)
res = tmp.popleft()
print(res)


k = int(input())
a = list(range(1, 10))
b = []
n = int(len(a))
x = k
while x > n:
	x -= n
	for i in range(n):
		for l in range(3):
			c = a[i] % 10 - 1 + l
			if 0 <= c <= 9:
				a.append(a[i] * 10 + c)
	del a[0:n]
print(a[x - 1])


q = []
for i in range(1, 10):
	q.append(i)
n = int(input())
ans = 0
for i in range(n):
	size = len(q)
	a = q[size - (size - i)]
	if a % 10 != 0:
		q.append(10 * a + a % 10 - 1)
	q.append(10 * a + a % 10)
	if a % 10 != 9:
		q.append(10 * a + a % 10 + 1)
print(q[n - 1])


import sys
sys.setrecursionlimit(10 ** 6 + 1)
K = int(input())
ans = []

def dfs(A):
	if len(A) >= 2:
		A_str = [str(i) for i in A]
		A_str = ''.join(A_str)
		ans.append(int(A_str))
	if len(A) == 10:
		return
	if len(A) >= 1:
		if A[-1] == 9:
			sta = 8
			fin = 9 + 1
		elif A[-1] == 0:
			sta = 0
			fin = 1 + 1
		else:
			sta = A[-1] - 1
			fin = A[-1] + 1 + 1
		for v in range(sta, fin):
			A.append(v)
			dfs(A)
			A.pop()
	else:
		for v in range(1, 9 + 1):
			A.append(v)
			dfs(A)
			A.pop()
dfs([])
ans = sorted(ans, reverse=False)
if K <= 9:
	print(K)
else:
	print(ans[K - 10])


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


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

def gen_lunlun(x):
	if x <= 3234566667:
		d = x % 10
		for i in [-1, 0, 1]:
			if d + i < 0 or d + i >= 10:
				continue
			nex = x * 10 + d + i
			ans.append(nex)
			gen_lunlun(nex)
for i in range(1, 10):
	ans.append(i)
	gen_lunlun(i)
ans = sorted(ans)
print(ans[k - 1])


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


k = int(input())
from queue import Queue
q = Queue()
for i in range(1, 10):
	q.put(i)
cnt = 0
while 1:
	cnt += 1
	x = q.get()
	if cnt == k:
		print(x)
		exit()
	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)


from sys import setrecursionlimit
setrecursionlimit(10 ** 5)
k = int(input())

def dfs(d, val, alls):
	alls.append(val)
	if d == 10:
		return
	for i in range(-1, 2):
		a = val % 10 + i
		if a >= 0 and a <= 9:
			dfs(d + 1, val * 10 + a, alls)
alls = list()
for i in range(1, 10):
	dfs(1, i, alls)
alls.sort()
print(alls[k - 1])


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


from heapq import *
a = [*list(range(1, 10))]
heapify(a)
i = 0
k = int(input())
c = 0
while True:
	t = str(heappop(a))
	i += 1
	if i == k:
		break
	if t[-1] != '0':
		heappush(a, int(t + str(int(t[-1]) - 1)))
	heappush(a, int(t + t[-1]))
	if t[-1] != '9':
		heappush(a, int(t + str(int(t[-1]) + 1)))
print(t)


k = int(input())
total_ls = []

def dfs(A):
	if int(A) > 3234566667:
		return
	nonlocal total_ls
	total_ls.append(int(A))
	last = int(A[-1])
	if last == 0:
		nex = [1, 0]
	elif last == 9:
		nex = [8, 9]
	else:
		nex = [last - 1, last, last + 1]
	for n in nex:
		A += str(n)
		dfs(A)
		A = A[:-1]
for i in range(1, 10):
	dfs(str(i))
total_ls.sort()
print(total_ls[k - 1])


from collections import deque
K = int(input())
que = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
for i in range(K):
	a = que.popleft()
	if not a % 10 == 0:
		que.append(a * 10 + a % 10 - 1)
	que.append(a * 10 + a % 10)
	if not a % 10 == 9:
		que.append(a * 10 + a % 10 + 1)
print(a)


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)


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


from collections import deque

def main():
	N = int(input())
	for n in range(N):
		x = ans.popleft()
		if x % 10 != 0:
			ans.append(10 * x + x % 10 - 1)
		ans.append(10 * x + x % 10)
		if x % 10 != 9:
			ans.append(10 * x + x % 10 + 1)
	print(x)

def __starting_point():
	ans = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
	main()
__starting_point()


import collections
K = int(input())
Q = collections.deque([i for i in range(1, 10)])
for _ in range(K):
	x = Q.popleft()
	r = x % 10
	if r != 0:
		Q.append(x * 10 + r - 1)
	Q.append(x * 10 + r)
	if r != 9:
		Q.append(x * 10 + r + 1)
print(x)


from collections import deque

def __starting_point():
	k = int(input())
	d = deque()
	ans = 0
	for i in range(1, 10):
		d.append(i)
	if k <= 9:
		print(k)
		return
	cnt = 9
	while True:
		x = d.popleft()
		if x % 10 != 0:
			tmp = 10 * x + x % 10 - 1
			d.append(tmp)
			cnt += 1
			if cnt >= k:
				ans = tmp
				break
		tmp = 10 * x + x % 10
		d.append(tmp)
		cnt += 1
		if cnt >= k:
			ans = tmp
			break
		if x % 10 != 9:
			tmp = 10 * x + x % 10 + 1
			d.append(tmp)
			cnt += 1
			if cnt >= k:
				ans = tmp
				break
	print(ans)
__starting_point()


from queue import Queue
K = int(input())
q = Queue()
for i in range(1, 10):
	q.put(i)
for i in range(K):
	x = q.get()
	right = x % 10
	for j in range(max(0, right - 1), min(right + 2, 10)):
		q.put(x * 10 + j)
print(x)


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])
	return
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])
			return
		q.append(a * 10 + b + 1)
		i += 1
		if i == k:
			print(q[-1])
			return
	elif b == 9:
		q.append(a * 10 + b - 1)
		i += 1
		if i == k:
			print(q[-1])
			return
		q.append(a * 10 + b)
		i += 1
		if i == k:
			print(q[-1])
			return
	else:
		q.append(a * 10 + b - 1)
		i += 1
		if i == k:
			print(q[-1])
			return
		q.append(a * 10 + b)
		i += 1
		if i == k:
			print(q[-1])
			return
		q.append(a * 10 + b + 1)
		i += 1
		if i == k:
			print(q[-1])
			return


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)


k = int(input())
lun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 0
while len(lun) < 10 ** 5:
	if lun[i] % 10 == 0:
		lun.append(lun[i] * 10 + lun[i] % 10 - 0)
		lun.append(lun[i] * 10 + lun[i] % 10 + 1)
	elif lun[i] % 10 == 9:
		lun.append(lun[i] * 10 + lun[i] % 10 - 1)
		lun.append(lun[i] * 10 + lun[i] % 10 - 0)
	else:
		lun.append(lun[i] * 10 + lun[i] % 10 - 1)
		lun.append(lun[i] * 10 + lun[i] % 10 - 0)
		lun.append(lun[i] * 10 + lun[i] % 10 + 1)
	i += 1
print(lun[k - 1])


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)


K = int(input())
arr = list(range(1, 10))
i = 0
while len(arr) < K:
	num = arr[i]
	last = list(filter(lambda x: 0 <= x <= 9, [num % 10 - 1, num % 10, num % 10 + 1]))
	arr.extend((num * 10 + t for t in last))
	i += 1
print(arr[K - 1])


from collections import deque
n = int(input()) - 10
q = deque(range(1, 10))
while n >= 0:
	a = str(q.popleft())
	a = int(a + a[-1])
	for i in range(a - 1, a + 2):
		if str(i)[-2] == str(a)[-1]:
			q.append(i)
			n -= 1
print(q[n])


n = int(input())
import queue
q = queue.Queue()
for i in range(1, 10):
	q.put(i)
while n != 1:
	x = q.get()
	k = x % 10
	for j in [10 * x + i for i in range(max(0, k - 1), min(10, k + 2))]:
		q.put(j)
	n -= 1
print(q.get())


a = {0}
(_, *s) = range(10)
while s:
	v = s.pop()
	a |= {v}
	for w in range(max(0, v % 10 - 1), min(10, v % 10 + 2)):
		w += v * 10
		if w < 4000000000.0:
			s += (w,)
print(sorted(a)[int(input())])


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)


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


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


k = int(input())

def dfs(keta, val):
	lunlun.append(val)
	if keta == 10:
		return
	for i in range(-1, 2):
		add = val % 10 + i
		if 0 <= add <= 9:
			dfs(keta + 1, val * 10 + add)
lunlun = []
for i in range(1, 10):
	dfs(1, i)
lunlun.sort()
print(lunlun[k - 1])


from collections import deque
k = int(input())
Q = deque(range(1, 10))
for _ in range(k):
	x = Q.popleft()
	y = x % 10
	z = 10 * x + y
	if y != 0:
		Q += [z - 1]
	Q += [z]
	if y != 9:
		Q += [z + 1]
print(x)


import sys
input = lambda : sys.stdin.readline().rstrip()
input_nums = lambda : list(map(int, input().split()))
from collections import deque

def main():
	K = int(input())
	runrun_lst = []

	def rec(num_of_digit, runrun_val):
		runrun_lst.append(runrun_val)
		if num_of_digit == 10:
			return
		for i in range(-1, 2):
			add = runrun_val % 10 + i
			if 0 <= add <= 9:
				rec(num_of_digit + 1, runrun_val * 10 + add)
	for v in range(1, 10):
		rec(1, v)
	runrun_lst.sort()
	print(runrun_lst[K - 1])

def __starting_point():
	main()
__starting_point()


from queue import deque
k = int(input())
que = deque()
for i in range(1, 10):
	que.append(i)
for i in range(k):
	now = que.popleft()
	too = now % 10
	if too != 0:
		que.append(now * 10 + too - 1)
	que.append(now * 10 + too)
	if too != 9:
		que.append(now * 10 + too + 1)
print(now)


k = int(input())
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
cnt = 1
for num in nums:
	if cnt == k:
		print(num)
		return
	elif num % 10 == 0:
		nums.append(num * 10)
		nums.append(num * 10 + 1)
	elif num % 10 == 9:
		nums.append(num * 10 + 8)
		nums.append(num * 10 + 9)
	else:
		nums.append(num * 10 + num % 10 - 1)
		nums.append(num * 10 + num % 10)
		nums.append(num * 10 + num % 10 + 1)
	cnt += 1


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)


k = int(input())
x = [i for i in range(1, 10)]
for i in range(k // 2):
	if x[i] % 10 != 0:
		x.append(10 * x[i] + x[i] % 10 - 1)
	x.append(10 * x[i] + x[i] % 10)
	if x[i] % 10 != 9:
		x.append(10 * x[i] + x[i] % 10 + 1)
print(x[k - 1])


def main():
	k = int(input())
	sm = 9
	d = {}
	lunlun = [i for i in range(1, 10)]
	for i in range(10):
		d[1, i] = ([str(i)], 1)
	dig = 2
	while sm < k:
		for i in range(10):
			out = []
			length = 0
			for j in (-1, 0, 1):
				if i + j < 0 or i + j > 9:
					continue
				out += [str(i) + x for x in d[dig - 1, i + j][0]]
				length += d[dig - 1, i + j][1]
			d[dig, i] = (out, length)
			if i >= 1:
				sm += length
				lunlun += out
		dig += 1
	print(lunlun[k - 1])
main()


from collections import deque

def main():
	K = int(input())
	q = deque()
	for i in range(1, 10, 1):
		q.append(i)
	list = []
	while len(list) <= 100002:
		v = q.popleft()
		list.append(v)
		amari = v % 10
		if amari != 0 and amari != 9:
			q.append(v * 10 + amari - 1)
			q.append(v * 10 + amari)
			q.append(v * 10 + amari + 1)
		elif amari == 0:
			q.append(v * 10 + amari)
			q.append(v * 10 + amari + 1)
		else:
			q.append(v * 10 + amari - 1)
			q.append(v * 10 + amari)
	return list[K - 1]
print(main())


L = []

def search(x):
	if x > 3234566667:
		return
	L.append(x)
	search(10 * x + x % 10)
	if x % 10 != 0:
		search(10 * x + x % 10 - 1)
	if x % 10 != 9:
		search(10 * x + x % 10 + 1)
for i in range(1, 10):
	search(i)
L.sort()
k = int(input())
print(L[k - 1])


K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 0
for i in range(K - 1):
	t = queue[i]
	if t % 10 != 0:
		queue.append(t * 10 + pow(t, 1, 10) - 1)
	queue.append(t * 10 + pow(t, 1, 10))
	if t % 10 != 9:
		queue.append(t * 10 + pow(t, 1, 10) + 1)
print(queue[K - 1])


K = int(input())
table = [n + 1 for n in range(9)]
for i in table:
	if len(table) > K:
		break
	x = i % 10
	for j in range(max(0, x - 1), min(x + 2, 10)):
		table.append(i * 10 + j)
print(table[K - 1])


k = int(input())
maximum = 3234566667
lst = list(range(1, 10))
from collections import deque
que = deque()
for i in range(1, 10):
	que.append(i)
	while que:
		now = que.pop()
		if now >= maximum:
			continue
		for j in range(max(0, now % 10 - 1), min(10, now % 10 + 2)):
			lst.append(now * 10 + j)
			que.append(now * 10 + j)
lst.sort()
print(lst[k - 1])


from collections import deque
K = int(input())
q = deque()
for i in range(1, 10):
	q.append(str(i))
while K > 0:
	n = q.popleft()
	t = int(n[-1])
	K -= 1
	for i in range(max(0, t - 1), min(9, t + 1) + 1):
		q.append(n + str(i))
print(n)


k = int(input())
a = []

def judge(x):
	if x > 3234566667:
		return
	a.append(x)
	for i in range(10):
		if abs(x % 10 - i) <= 1:
			judge(x * 10 + i)
for i in range(1, 10):
	judge(i)
a.sort()
print(a[k - 1])


import queue
q = queue.Queue()
for i in range(1, 10):
	q.put(i)
K = int(input())
t = 0
ans = 0
while t < K:
	t += 1
	ans = q.get()
	p = int(str(ans)[-1])
	for i in range(-1, 2):
		if 0 <= p + i < 10:
			q.put(int(str(ans) + str(p + i)))
print(ans)


k = int(input())
s = 9
l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 0
while s < 10 ** 5 + 1:
	t = l[n]
	z = int(str(t)[-1])
	if z > 0:
		l.append(t * 10 + z - 1)
		s += 1
	l.append(t * 10 + z)
	s += 1
	if z < 9:
		l.append(t * 10 + z + 1)
		s += 1
	n += 1
l.sort()
print(l[k - 1])


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

def __starting_point():
	main()
__starting_point()


from collections import deque
K = int(input())
Q = deque(list(range(1, 10)))
for _ 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)


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


from queue import deque
k = int(input())
Q = deque([i for i in range(1, 10)])
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)


from collections import deque
k = int(input())
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
b = deque(a)
while b:
	v = b.popleft()
	if v % 10 == 0:
		f = v * 10 + 1
		if f <= 3234566667:
			b.append(f)
			a.append(f)
		g = v * 10
		if g <= 3234566667:
			b.append(g)
			a.append(g)
	elif v % 10 == 9:
		f = v * 10 + 8
		g = v * 10 + 9
		if f <= 3234566667:
			b.append(f)
			a.append(f)
		if g <= 3234566667:
			b.append(g)
			a.append(g)
	else:
		f = v * 10 + v % 10 - 1
		g = v * 10 + v % 10
		h = v * 10 + v % 10 + 1
		if f <= 3234566667:
			b.append(f)
			a.append(f)
		if g <= 3234566667:
			b.append(g)
			a.append(g)
		if h <= 3234566667:
			b.append(h)
			a.append(h)
a.sort()
print(a[k - 1])


from collections import *
k = int(input())
q = deque(range(1, 10))
c = 0
while c < k:
	t = q.popleft()
	for j in range(max(t % 10 - 1, 0), min(t % 10 + 2, 10)):
		q += [t * 10 + j]
	c += 1
print(t)


import sys
sys.setrecursionlimit(10 ** 5)

def dfs(v):
	ans.append(v)
	if v > 1000000000:
		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])


from collections import deque
k = int(input())
num = []

def dfs(lun):
	num.append(lun)
	if lun > 3234566667:
		return
	now = lun % 10
	for i in [-1, 0, 1]:
		if 0 <= now + i <= 9:
			dfs(lun * 10 + now + i)
for i in range(1, 10):
	dfs(i)
num.sort()
print(num[k - 1])


from collections import deque
k = int(input())
d = deque()
for i in range(1, 10):
	d.append(i)
for j in range(k):
	a = d.popleft()
	b = a % 10
	if b != 0:
		d.append(10 * a + b - 1)
	d.append(10 * a + b)
	if b != 9:
		d.append(10 * a + b + 1)
print(a)


from collections import deque
K = int(input())
dq = deque(list(range(1, 10)))
for i in range(K):
	now = dq.popleft()
	for i in (-1, 0, 1):
		add = now % 10 + i
		if 0 <= add < 10:
			dq.append(now * 10 + add)
print(now)


k = int(input())
a = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
i = 0
while len(a) <= k:
	b = a[i]
	c = int(b[-1])
	i += 1
	for j in range(-1, 2):
		if 0 <= c + j < 10:
			a.append(b + str(c + j))
print(a[k - 1])


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)


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

def dfs(d, val, al):
	al.append(val)
	if d == 10:
		return
	r = val % 10
	for i in range(-1, 2):
		if 0 <= r + i <= 9:
			dfs(d + 1, val * 10 + r + i, al)
al = list()
for i in range(1, 10):
	dfs(1, i, al)
al.sort()
print(al[k - 1])


from collections import deque
K = int(input())
q = deque(list(range(1, 10)))
for _ in range(K - 1):
	u = q.popleft()
	n = u % 10
	for x in range(max(0, n - 1), min(9, n + 1) + 1):
		q.append(u * 10 + x)
print(q.popleft())


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)


K = int(input())
cand = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
for i in range(9):
	tmp = []
	for val in cand[-1]:
		if str(val)[-1] != '0':
			tmp.append(val * 10 + int(str(val)[-1]) - 1)
		tmp.append(val * 10 + int(str(val)[-1]))
		if str(val)[-1] != '9':
			tmp.append(val * 10 + int(str(val)[-1]) + 1)
	cand.append(tmp)
ans = []
for l in cand:
	for i in l:
		ans.append(i)
ans.sort()
print(ans[K - 1])


def solver(d, v, a):
	a.append(v)
	if d == 10:
		return
	for i in range(-1, 2):
		add = v % 10 + i
		if add < 0 or 9 < add:
			continue
		solver(d + 1, v * 10 + add, a)

def main():
	k = int(input())
	a = []
	for i in range(1, 10):
		solver(1, i, a)
	a.sort()
	print(a[k - 1])

def __starting_point():
	main()
__starting_point()


from collections import deque
K = int(input())
lunlundeque = deque()
for i in range(1, 10):
	lunlundeque.append(i)
nowlunlun = 0
index = 0
while index < K:
	index += 1
	nowlunlun = lunlundeque.popleft()
	if nowlunlun % 10 != 0:
		lunlundeque.append(nowlunlun * 10 + nowlunlun % 10 - 1)
	lunlundeque.append(nowlunlun * 10 + nowlunlun % 10)
	if nowlunlun % 10 != 9:
		lunlundeque.append(nowlunlun * 10 + nowlunlun % 10 + 1)
print(nowlunlun)


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


from collections import deque
K = int(input())
count = 0
todo = deque(range(1, 10))
while todo:
	x = todo.popleft()
	count += 1
	if count == K:
		print(x)
		break
	i = x % 10
	if 0 < i:
		todo.append(x * 10 + i - 1)
	todo.append(x * 10 + i)
	if i < 9:
		todo.append(x * 10 + i + 1)


K = int(input())
cnt = 0
ans = ''

def dfs(n_str, digit):
	nonlocal cnt, ans
	if len(n_str) >= digit:
		cnt += 1
		if cnt == K:
			ans = n_str
		return
	last = int(n_str[-1])
	for i in range(max(0, last - 1), min(9, last + 1) + 1):
		dfs(n_str + str(i), digit)
digit = 1
while ans == '':
	for i in range(1, 10):
		dfs(str(i), digit)
	digit += 1
print(ans)


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


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)