Problem:
 Score : 400 points    Problem Statement  A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:   In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1 .   For example, 1234 , 1 , and 334 are lunlun numbers, while none of 31415 , 119 , or 13579 is.  You are given a positive integer K . Find the K -th smallest lunlun number.      Constraints   1 \leq K \leq 10^5  All values in input are integers.         Input  Input is given from Standard Input in the following format:  K       Output  Print the answer.        Sample Input 1 15      Sample Output 1 23  We will list the 15 smallest lunlun numbers in ascending order:  1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 21 , 22 , 23 . Thus, the answer is 23 .       Sample Input 2 1      Sample Output 2 1       Sample Input 3 13      Sample Output 3 21       Sample Input 4 100000      Sample Output 4 3234566667  Note that the answer may not fit into the 32 -bit signed integer type.

Solution (Python):
import sys


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


def main():
    K = int(input())
    ans = list("123456789")
    tmp = ans.copy()
    while True:
        tmp2 = []
        for t in tmp:
            for i in range(int(t[-1]) - 1, int(t[-1]) + 2):
                if 0 <= i < 10:
                    tmp2.append(t + str(i))
        tmp = tmp2.copy()
        ans += tmp
        if len(ans) >= K:
            break

    print(ans[K - 1])


if __name__ == "__main__":
    main()

Solution (Python):
def examA():
    X, Y, Z = LI()
    X, Y = Y,X
    X,Z = Z, X
    print(X,Y,Z)
    return

def examB():
    N, M = LI()
    A = LI()
    need = (sum(A)-1)//(4*M) + 1
    ans = 0
    
    for a in A:
        if a>=need:
            ans += 1
    if ans>=M:
        print("Yes")
    else:
        print("No")
    return

def examC():
    N, K = LI()
    ans = N%K
    if K-ans<ans:
        ans = K-ans
    print(ans)
    return

def examD():
    def bfs(n):
        
        W = [""] * n
        
        que = deque()
        for i in range(1,10):
            que.append(str(i))
            W[i-1] = str(i)
        i = 9
        while(i<n):
            now = que.popleft()
            end = now[-1]
            for j in [-1,0,1]:
                ne = int(end)+j
                if 0<=ne<=9:
                    W[i] = now + str(ne)
                    que.append(W[i])
                    i += 1
                    if i==n:
                        break
        return W
    K = I()
    if K<=12:
        ans = K
        print(ans)
        return
    ans = bfs(K)[-1]
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""

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

    def runrun(n):
        n = list(map(int, list(str(n))))
        for i in range(len(n)-1):
            if abs(n[i] - n[i+1]) > 1:
                if n[i] > n[i+1]:
                    n[i+1] = n[i]-1
                    for j in range(i+2, len(n)):
                        n[j] = 0
                else:
                    n[i] = n[i+1]-1
                    for j in range(i+1, len(n)):
                        n[j] = 0
                return int("".join(list(map(str, n))))
        return False

    run = []
    i = 1
    cnt = 0
    while cnt < k:
        j = runrun(i)
        if j:
            i = j
        else:
            run.append(i)
            cnt += 1
            i += 1
    print(run[k-1])


main()

Solution (Python):
K = int(input())
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
cnt = 0
while len(A) < 100000:
  n = len(A)
  for i in range(cnt, cnt + n):
    x = A[i] % 10
    A.append(int(str(A[i])+str(x)))
    if x > 0:
      A.append(int(str(A[i])+str(x-1)))
    if x <= 8:
      A.append(int(str(A[i])+str(x+1)))
  cnt += n
A.sort()
print(A[K-1])

Solution (Python):
buf = [str(i) for i in range(1,10)]
next = []
ans = []
flag = False
k = int(input())

while True:
    next = []
    if flag:
        break
    for b in buf:
        ans.append(int(b))
        if b[0] == "4" and len(b) >= 10:
            flag = True
            break
        if b[-1] == "0":
            next.append(b+"0")
            next.append(b+"1")
        elif b[-1] == "9":
            next.append(b+"8")
            next.append(b+"9")
        else:
            base = int(b[-1])
            for i in range(3):
                next.append(b+str(base+i-1))
    buf = next

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

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

ans = []
r = [str(i) for i in range(1, 10)]
ans.extend(r)
for _ in range(9):
    rn = []
    for i in r:
        x = int(i[-1])
        if x == 0:
            rn.append(i+str(x+1))
            rn.append(i+str(x))
        elif x == 9:
            rn.append(i+str(x))
            rn.append(i+str(x-1))

        else:
            rn.append(i+str(x+1))
            rn.append(i+str(x))
            rn.append(i+str(x-1))
    ans.extend(rn)
    r = rn[:]

ans = [int(i) for i in ans]
ans.sort()

print(ans[k-1])

Solution (Python):
import sys
sys.setrecursionlimit(200000)

K = int(input())

lis = [0]

def pl(now,keta):
    now[keta] += 1

    if keta == len(now)-1:
        if now[keta] == 10:
            now.append(1)
            now[keta] = 0
            return
        else:
            return

    else:
        if now[keta] == 10 or now[keta] > now[keta+1] + 1:
            pl(now,keta+1)
            now[keta] = max(0,now[keta+1] - 1)
            return
        else:
            return

for loop in range(K):

    pl(lis,0)

lis.reverse()
print ("".join(map(str,lis)))

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


K = int(readline())

q = deque()

for i in range(1, 10):
    q.append([i])

count = 0
while True:
    a = q.popleft()
    count += 1
    if count == K:
        ans = a
        break
    tail = a[-1]
    if tail >= 1:
        q.append(a + [tail - 1])
    q.append(a + [tail])
    if tail <= 8:
        q.append(a + [tail + 1])

print(''.join(map(str, ans)))

Solution (Python):
k = int(input())
dp = [[] for i in range(1000)]
dp[0] = list(range(1,10))
D = [-1,0,1]

count = 0
for i in range(10**5):
  count = len(dp[i])
  if count > k:
    ans = dp[i]
    ans.sort()
    print(ans[k-1])
    exit()
  else:
    k -= count
    for j in dp[i]:
      str_j = str(j)
      for d in D:
        nxt = int(str_j[-1])+d
        if 0<=nxt<=9:
          dp[i+1].append(j * 10 + nxt)

Solution (Python):
import sys
sys.setrecursionlimit(2 * 10 ** 5)
k = int(input())

r = []

MAX = 3234566667

def dfs(x):
    s = str(x)
    r.append(x)
    last = int(s[-1])
    for i in range(last-1, last+2):
        if 0 <= i <= 9:
            next = int(s + str(i))
            if next <= MAX:
                dfs(next)

dfs(1)
dfs(2)
dfs(3)
dfs(4)
dfs(5)
dfs(6)
dfs(7)
dfs(8)
dfs(9)

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

Solution (Python):
import heapq

k = int(input())
ln = [i for i in range(1, 10)]
heapq.heapify(ln)
i = 0
while True:
    i += 1
    x = heapq.heappop(ln)
    if i == k:
        break
    msd = x % 10
    if msd != 0:
        heapq.heappush(ln, x * 10 + msd - 1)
    heapq.heappush(ln, x * 10 + msd)
    if msd != 9:
        heapq.heappush(ln, x * 10 + msd + 1)
print(x)

Solution (Python):
k=int(input())
ans=set([1,2,3,4,5,6,7,8,9])
for _ in range(11):
  c=set()
  for b in ans:
    x=int(str(b)[-1])
    if x==0:
      c.add(int(str(b)+'0'))
      c.add(int(str(b)+'1'))
    elif x==9:
      c.add(int(str(b)+'9'))
      c.add(int(str(b)+'8'))
    else:
      c.add(int(str(b)+str(x+1)))
      c.add(int(str(b)+str(x)))
      c.add(int(str(b)+str(x-1)))
  ans=ans|c
ans=list(ans)
ans.sort()
print(ans[k-1])

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

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

p = 0

def generate_lunlun(p):
    last = p % 10
    if last - 1 >= 0:
        yield p * 10 + last - 1
    yield p * 10 + last
    if last + 1 <= 9:
        yield p * 10 + last + 1

while len(lunlun) < k:
    for new_lunlun in generate_lunlun(lunlun[p]):
        lunlun.append(new_lunlun)
    p += 1

print(lunlun[k-1])

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

ans = [[] for _ in range(12)]
ans2 = [1,2,3,4,5,6,7,8,9]
ans[0] = [1,2,3,4,5,6,7,8,9]
count = 9

for i in range(12):
    if i == 0:
        pass
    else:
        for j in ans[i-1]:
            k = int(str(j)[-1])
            if k == 0:
                ans[i].append(j * 10 + k)
                ans[i].append(j * 10 + k + 1)
                ans2.append(j * 10 + k)
                ans2.append(j * 10 + k + 1)
                count += 2
            elif k == 9:
                ans[i].append(j * 10 + k - 1)
                ans[i].append(j * 10 + k)
                ans2.append(j * 10 + k - 1)
                ans2.append(j * 10 + k)
                count += 2
            else:
                ans[i].append(j * 10 + k - 1)
                ans[i].append(j * 10 + k)
                ans[i].append(j * 10 + k + 1)
                ans2.append(j * 10 + k - 1)
                ans2.append(j * 10 + k)
                ans2.append(j * 10 + k + 1)
                count += 3

            if count >= K:
                print(ans2[K-count-1])
                exit()

Solution (Python):
from collections import deque
k=int(input())
l=deque([i+1 for i in range(9)])
cnt=9
if k<=cnt:print(l[k-1])
else:
    while cnt<k:
        v=l.popleft()
        if v%10==0:l.append(v*10);l.append(v*10+1);cnt+=2
        elif v%10==9:l.append(v*10+8);l.append(v*10+9);cnt+=2
        else:
            rem=v%10
            l.append(v*10+rem-1)
            l.append(v*10+rem)
            l.append(v*10+rem+1)
            cnt+=3
    print(l[k-cnt-1])

Solution (Python):
k=int(input())
ans=[]
p=[i for i in range(1,10)]
for _ in range(9):
    q=[]
    for x in p:
        y=x%10
        q.append(x*10+y)
        if y<9: q.append(x*10+y+1)
        if y>0: q.append(x*10+y-1)
    for x in p:
        ans.append(x)
    p=[q[i] for i in range(len(q))]

for x in q:
    ans.append(x)

ans=sorted(ans)
print(ans[k-1])

Solution (Python):
k = int(input())
ans = [1,2,3,4,5,6,7,8,9]
cnt = 0
def lunlun(a,cnt):
  if cnt == 10:
    return a
  else:
    cnt += 1
    x = a%10
    for i in x-1,x,x+1:
      if 0 <= i <= 9:
        ans.append(a*10+i)
        lunlun(a*10+i,cnt)
for i in range(1,10):
  lunlun(i,0)
ans.sort()
print(ans[k-1])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
k = int(input())

ansl = []

def dfs(s):
    if len(s) >= 11:
        return
    ansl.append(s)
    if s[-1] != "0":
        dfs(s+str(int(s[-1])-1))
    dfs(s + str(int(s[-1])))
    if s[-1] != "9":
        dfs(s + str(int(s[-1]) + 1))

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

Solution (Python):

from collections import deque
K=int(input())
lunlun=[str(i) for i in range(1,10)]
Q=deque([str(i) for i in range(1,10)])
while len(lunlun)<=2*(10**5):
    q=Q.popleft()
    i=int(q[-1])
    lunlun.append(q+str(i))
    Q.append(q+str(i))
    if i+1<10:
        lunlun.append(q+str(i+1))
        Q.append(q+str(i+1))
    if i-1>=0:
        lunlun.append(q+str(i-1))
        Q.append(q+str(i-1))
lunlun=list(int(i) for i in set(lunlun))
lunlun.sort()
print(lunlun[K-1])

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

i = 0

for i in range(k):
    now = ans[i]
    if str(now)[-1] == '0':
        ans.append(now*10)
        ans.append(now*10+1)
    elif str(now)[-1] == '9':
        ans.append(now*10+8)
        ans.append(now*10+9)
    else:
        ans.append(now*10+now%10-1)
        ans.append(now*10+now%10)
        ans.append(now*10+now%10+1)
    if len(ans) > k:
        break

print(ans[k-1])

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

K = int(input())

def dfs(le, L, ret):
    if len(L) == le:
        ret.append(L)
        return ret
    l = L[-1]
    for num in range(max(0, l-1), min(l+1, 9)+1):
        ret = dfs(le, L+[num], ret)
    return ret

le = 0
ans = []
while True:
    le += 1
    for n in range(1, 10):
        ret = dfs(le, [n], [])
        if len(ret) < K:
            K -= len(ret)
        else:
            ans = ret[K-1]
            break
    if ans: break

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

K = int(input())

cnt = 0
def dfs(keta, cur) :
  if keta == 0 :
    global cnt
    cnt += 1
    if cnt == K :
      print(cur)
      exit()
    return 
      
  i = cur % 10
  if i - 1 >= 0 :
    dfs(keta - 1, cur * 10 + i - 1)
  dfs(keta - 1, cur * 10 + i)
  if i + 1 <= 9 :
    dfs(keta - 1, cur * 10 + i + 1)

for keta in range(100) :
  for i in range(1, 10) :
    dfs(keta, i)

Solution (Python):
from collections import deque
k = int(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)

Solution (Python):
from collections import deque

k = int(input())

todo = deque(list(map(str, range(1, 10))))
count = 0
while todo:
    num = todo.popleft()
    count += 1
    if count == k:
        print(num)
        exit()

    base = int(num[-1])
    n1 = base - 1
    if n1 != -1:
        todo.append(num + str(n1))
    n2 = base
    todo.append(num + str(n2))

    n3 = base + 1
    if n3 != 10:
        todo.append(num + str(n3))

Solution (Python):
X = [[i for i in range(1, 10)]]
for i in range(9):
    Y = []
    for x in X[-1]:
        s = x % 10
        if s == 0:
            Y.append(x * 10 + s)
            Y.append(x * 10 + s + 1)
        elif s == 9:
            Y.append(x * 10 + s - 1)
            Y.append(x * 10 + s)
        else:
            Y.append(x * 10 + s- 1)
            Y.append(x * 10 + s)
            Y.append(x * 10 + s + 1)
    X.append(Y)
XX = []
for x in X:
    XX += x[:]
XX = sorted(XX)
print(XX[int(input()) - 1])

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    K=I()
    L=[]
    import queue
    
    
    q=queue.Queue()
    for i in range(1,10):
        q.put(i)
        
    dx=[-1,0,1]
        
        
    while len(L)!=K:
        a=q.get()
        L.append(a)
        res=a%10
        for i in range(3):
            c=dx[i]
            res2=res+c
            if res2!=-1 and res2!=10:
                new=a*10+res2
                q.put(new)
                
    print(L[-1])
                

main()

Solution (Python):
n = int(input())
now = [i+1 for i in range(9)]
ans = now[:]
for k in range(11):
  last = now
  now = []
  for x in last:
    y = x % 10
    if y == 0:
      now.append(x*10+y)
      now.append(x*10+y+1)
      ans.append(x*10+y)
      ans.append(x*10+y+1)
    elif y == 9:
      now.append(x*10+y-1)
      now.append(x*10+y)
      ans.append(x*10+y-1)
      ans.append(x*10+y)
    else:
      now.append(x*10+y-1)
      now.append(x*10+y)
      now.append(x*10+y+1)
      ans.append(x*10+y-1)
      ans.append(x*10+y)
      ans.append(x*10+y+1)
print(ans[n-1])

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

LIST=[]

def next(L):
    if len(L)==10:
        return
    t=int(L[-1])
    for x in [t-1,t,t+1]:
        if 0<=x<=9:
            y=L+(x,)
            LIST.append(y)
            next(y)

for i in range(1,10):
    x=(i,)
    LIST.append(x)
    next(x)

        
L2=[]

for l in LIST:
    L2.append(int("".join(map(str,l))))

L2.sort()
print(L2[int(input())-1])

Solution (Python):
K = int(input())
if K < 10:
	print(K)
	exit()
L = [1,2,3,4,5,6,7,8,9]
k = 9
i = 0
while k < K:
	l = L[i]
	a = l % 10
	if a > 0:
		L.append(l*10 + a - 1)
		k += 1
	L.append(l*10 + a)
	k += 1
	if a < 9:
		L.append(l*10 + a + 1)
		k += 1
	i += 1
print(L[K-1])

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

    K = int(input())
    ans = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    que = deque(ans)
    for _ in range(9):
        que_new = deque()
        while que:
            i = que.popleft()
            i_ = i%10
            i_new = i*10+i_
            if i_ != 0:
                ans.append(i_new-1)
                que_new.append(i_new-1)
            ans.append(i_new)
            que_new.append(i_new)
            if i_ != 9:
                ans.append(i_new + 1)
                que_new.append(i_new + 1)
        que = que_new
    print(ans[K-1])


if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

runrun = [None for _ in range(100)]
runrun[1] = (1, 2, 3, 4, 5, 6, 7, 8, 9)


def gen_runrun_keta(k):
    for x in runrun[k - 1]:
        r = x % 10
        if r > 0:
            yield 10 * x + (r - 1)
        yield 10 * x + r
        if r < 9:
            yield 10 * x + (r + 1)


for keta in range(2, 11):
    runrun[keta] = tuple(gen_runrun_keta(keta))


rest = int(read())

answer = 0
for n in range(1, 11):
    if rest <= len(runrun[n]):
        answer = runrun[n][rest - 1]
        break
    rest -= len(runrun[n])
print(answer)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15


def main():
    n = getN()
    ans = 0
    runruns = [[str(i) for i in range(10)]]
    for digit in range(9):
        tmp = []
        for i in range(10):
            stri = str(i)
            for run in runruns[-1]:
                if abs(i - int(run[0])) <= 1:
                    tmp.append(stri + run)

        tmp.sort()
        runruns.append(tmp)
    runruns = [[r for r in run if r[0] != "0"] for run in runruns]
    
    
    ans = []
    for run in runruns:
        ans = ans + run

    print(ans[n-1])
    
if __name__ == '__main__':
    main()

Solution (Python):
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)
k = int(input())
print(a[k-1])

Solution (Python):
import sys
import itertools

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

K = ni() - 1

for le in range(1, 11):
    for h in range(1, 10):
        for a in itertools.product((-1, 0, 1), repeat=le-1):
            cur = h
            ok = True
            for u in a:
                cur += u
                if cur > 9 or cur < 0:
                    ok = False
                    break
            if ok:
                if K == 0:
                    ret = [h] + [_ + h for _ in itertools.accumulate(a)]
                    print("".join(map(str, ret)))
                    sys.exit(0)
                K -= 1

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def li(i):
        if i == 0:
            return [0,1]
        if i < 9:
            return [i-1,i,i+1]
        else:
            return [8,9]

    f = [(i,i) for i in range(1,10)]
    s = 10
    while len(f) < 10**5:
        nf = [(i*10+k,k) for (i,j) in f[-s:] for k in li(j)]
        f += nf
        s = len(nf)
    k = I()
    print(f[k-1][0])
    return


if __name__ == "__main__":
    solve()

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