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):
K=int(input())
List=[1,2,3,4,5,6,7,8,9]
N=0
M=9
while len(List)<K:
    for i in range(N,M):
        last_number=List[i]%10
        times10=10*List[i]
        if last_number!=0:
            List.append(times10+last_number-1)
        List.append(times10+last_number)
        if last_number!=9:
            List.append(times10+last_number+1)
    N=M
    M=len(List)
   

print(List[K-1])

Solution (Python):
import queue
q = queue.Queue()
K = int(input())
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)

Solution (Python):

count = 1

def cal(k, num, digit):
  global count
  if digit == 0:
    if count == k:
      print(num)
      exit()

    count += 1

  else:
    base = int(str(num)[-digit - 1])
    bottom = base - 1 if base > 0 else base
    head = base + 2 if base < 9 else base + 1

    for i in range(bottom, head):
      i = i * 10**(digit - 1) if digit > 1 else i
      cal(k, num + i, digit - 1)


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

  digit = 0
  while True:
    for i in range(1, 10):
      cal(k, i * 10**digit, digit)

    digit += 1

main()

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

Solution (Python):
import sys

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

K = int(read())

pre_lis = []
for i in range(1,10):
    pre_lis.append(str(i))
    
ct = 9
if K <= 9:
    print(pre_lis[K-1])
else:
    new_lis = []
    flag = False
    while ct < K:
        for num in pre_lis:
            pre_num = int(num[-1])
            for i in range(10):
                if abs(pre_num-i) <= 1:
                    new_lis.append(num + str(i))
                    ct+=1
                    if ct == K:
                        print(new_lis[-1])
                        flag = True
                        break
            pre_lis = new_lis
            if flag:
                break
        if flag:
            break

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

for j in range(9):
    b = []
    for i in a[-1]:
        I = str(i)
        if I[-1] != '9':
            b.append(i*10 + int(I[-1])+1)
        b.append(i*10 + int(I[-1]))
        if I[-1] != '0':
            b.append(i*10 + int(I[-1])-1)
    a.append(b)
    A += b
ans = sorted(A)
print(ans[k-1])

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

for i in range(k):
  f = x.popleft()
  if(f % 10 != 0):	x.append(10 * f + f % 10 - 1)
  x.append(10 * f + f % 10)
  if(f % 10 != 9):	x.append(10 * f + f % 10 + 1)
print(f)

Solution (Python):
from collections import deque
k = int(input())
l = [int(x) for x in range(1,10)]
lnln = deque(l)
Lnln = []

n = 10**5
for i in range(n):
    x = lnln.popleft()
    Lnln.append(x)
    a = x % 10
    
    if a!=0:
        lnln.append(x*10 + (a-1))
        
    lnln.append(x*10 + a)
        
    if a!=9:
        lnln.append(x*10 + (a+1))
        
print(Lnln[k-1])

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

a = [str(i) for i in range(1,10)]

for i in range(40000):
    if a[i][-1] == '0':
        a.append(str(a[i])+'0')
        a.append(str(a[i])+'1')
    elif a[i][-1] == '9':
        a.append(str(a[i])+'8')
        a.append(str(a[i])+'9')
    elif a[i][-1] != '0' and a[i][-1] != '9':
        a.append(str(a[i]) + str(int(a[i][-1])-1))
        a.append(str(a[i]) + str(int(a[i][-1])))
        a.append(str(a[i]) + str(int(a[i][-1])+1))

print(a[k-1])

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

Solution (Python):
k = int(input())
if k <= 9:
    print(k)
    exit()
a = [i for i in range(1, 10)]
cnt = 9
idx = 0
while cnt < k:
    a_ = str(a[idx])
    t = a_[-1]
    if t == "0":
        l_ = [0, 1]
    elif t == "9":
        l_ = [8, 9]
    else:
        l_ = [int(t)-1, int(t), int(t)+1]
    for i in l_:
        a.append(int(a_ + str(i)))
    cnt += len(l_)
    idx += 1
print(a[-(cnt-k+1)])

Solution (Python):
import itertools
k = int(input())
lun = [[1,2,3,4,5,6,7,8,9]]
lun_flatten = [1,2,3,4,5,6,7,8,9]
def l(n):
    tmp = lun[n-2]
    ans = []
    for i in tmp:
        a = int(str(i)[-1])
        t = 10 * i + a
        if a != 0:
            ans.append(t - 1)
        ans.append(t)
        if a != 9:
            ans.append(t+1)
    lun.append(ans)

i = 2
while len(lun_flatten) < k:
    l(i)
    lun_flatten =  list(itertools.chain.from_iterable(lun))
    i += 1

print(lun_flatten[k-1])

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

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

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

from collections import deque

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

k=1
while True:
    a=d.popleft()
    if k==K:
        print(a)
        exit()
    else:
        k+=1
    r=a%10
    if 0<r<=9:
        temp = a * 10 + (r -1)
        d.append(temp)
    temp=a*10+r
    d.append(temp)
    if 0<=r<9:
        temp=a*10+(r+1)
        d.append(temp)

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

from collections import deque

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

k=1
while True:
    a=d.popleft()
    if k==K:
        print(a)
        exit()
    else:
        k+=1
    r=a%10
    if r==0:
        for i in [0,1]:
            temp=a*10+i
            d.append(temp)
    elif r==9:
        for i in [8,9]:
            temp=a*10+i
            d.append(temp)
    else:
        for i in [-1,0,1]:
            temp=a*10+(r+i)
            d.append(temp)

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

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

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

Solution (Python):

N = int(input())


c = [list(range(1, 10))]
for i in range(9):
    tmp = []
    append = tmp.append
    for val in c[-1]:
        if val % 10 != 0:
            append(val * 10 + (val % 10 - 1))
        append(val * 10 + (val % 10))
        if val % 10 != 9:
            append(val * 10 + (val % 10 + 1))
    c.append(tmp)

ans = []
set = ans.append
for i in range(len(c)):
    for val in c[i]:
        set(val)

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

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

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

from collections import deque

d=deque(["2","3","4","5","6","7","8","9","10","11","12"])
num=[1,2,3,4,5,6,7,8,9,10,11,12]

while True:
    s=d.popleft()
    x=int(s[-1])
    if x==0:
        for i in ["0","1"]:
            temp=s+i
            d.append(temp)
            num.append(int(temp))

    elif x==9:
        for i in ["8","9"]:
            temp=s+i
            d.append(temp)
            num.append(int(temp))
    else:
        for j in [-1,0,1]:
            temp=s+str(x+j)
            d.append(temp)
            num.append(int(temp))
    if len(num)>=K:
        print(num[K-1])
        exit()

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

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

k=12

from collections import deque

d=deque(["2","3","4","5","6","7","8","9","10","11","12"])

while True:
    s=d.popleft()
    x=int(s[-1])
    if x==0:
        for i in ["0","1"]:
            temp=s+i
            d.append(temp)
            k+=1
            if k==K:
                print(temp)
                exit()
    elif x==9:
        for i in ["8","9"]:
            temp=s+i
            d.append(temp)
            k+=1
            if k==K:
                print(temp)
                exit()
    else:
        for j in [-1,0,1]:
            temp=s+str(x+j)
            d.append(temp)
            k+=1
            if k==K:
                print(temp)
                exit()

Solution (Python):
import queue

k = int(input())

q = queue.Queue()

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

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

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

Solution (Python):
from collections import deque

k = int(input())

def lunlun(n):
  d = deque(range(1, 10))
  
  for i in range(n):
    x = d.popleft()
    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)
  
  return x

print(lunlun(k))

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

Q = deque([i for i in range(1, 10)])    
for i in range(k):
    inum = Q[0] 
    op = inum % 10  
    Q.popleft()
    for j in [-1, 0, 1]:
        if 0 <= op+j and op+j <= 9:
            Q.append(inum*10+(op+j))
        else:
            pass

ans = inum
print(ans)

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

B = [1, 2, 3, 4, 5, 6, 7, 8, 9] 
while len(B) < k:
    k -= len(B)
    
    def update_next_digit(B:list)->list:
        N = []  
        for i in range(len(B)):
            op = B[i] % 10  
            for j in [-1, 0, 1]:
                if 0 <= op+j and op+j <= 9:
                    N.append(B[i]*10+(op+j))
                else:
                    pass
        return N
    N = update_next_digit(B)
    B = N

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

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

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

    def dfs(depth, max_depth, num):
        if depth==max_depth:
            lunlun_temp.append(''.join([str(i) for i in num]))
        elif depth==0:
            for i in range(1, 10):
                dfs(depth+1, max_depth, num+[i])
        else:
            for i in range(3):
                if 0<=num[-1]-1+i<=9:
                    dfs(depth+1, max_depth, num+[num[-1]-1+i])

    lunlun = []

    i = 1
    while len(lunlun)<K:
        lunlun_temp = []
        dfs(0, i, [])
        lunlun += lunlun_temp
        i += 1

    print(lunlun[K-1])

if __name__ == '__main__':
    resolve()

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

if k < 10:
    print(k)
    exit()

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

def check():
    if cnt == k:
        print(memo[-1])
        exit()

while True:
    memo = []
    for i in l:
        if i[-1] == "0":
            memo.append(i+"0")
            cnt += 1
            check()

            memo.append(i+"1")
            cnt += 1
            check()

        elif i[-1] == "9":
            memo.append(i+"8")
            cnt += 1
            check()

            memo.append(i+"9")
            cnt += 1
            check()

        else:
            memo.append(i + str(int(i[-1])-1))
            cnt += 1
            check()

            memo.append(i + i[-1])
            cnt += 1
            check()

            memo.append(i + str(int(i[-1]) + 1))
            cnt += 1
            check()

    l = memo[:]

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

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

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

Solution (Python):



def solve():
    print(ll_no_dup[k-1])
    return











lunluns = [str(i) for i in range(1, 10)]

it = 0
count = 0
all_count = len(lunluns)
while count <= 10 ** 5:
    it = len(lunluns)
    last_count = all_count
    all_count = 0
    for i in range(it-last_count, it):
        last_val = int(lunluns[i][-1])
        if last_val > 0:
            lunluns.append(lunluns[i] + str(last_val - 1))
            count += 1
            all_count +=1
        lunluns.append(lunluns[i] + str(last_val))
        count += 1
        all_count +=1
        if last_val < 9:
            lunluns.append(lunluns[i] + str(last_val + 1))
            count += 1
            all_count +=1
        if count > 10 ** 5:
            break

ll_no_dup = [str(1)]
for i in range(1, len(lunluns)):
    if lunluns[i]!=lunluns[i-1]:
        ll_no_dup.append(lunluns[i])



k = int(input())
solve()

Solution (Python):
n=int(input())
ans=[0 for i in range(10**5+21)]
Q=[0,1,2,3]
def li(x):
  if x==0 : return [0,1]
  if x==9 : return [8,9]
  return [x-1,x,x+1]

now=0
for q in Q:
  W=[i for i in range(10)] if q==0 else li(q)
  for w in W:
    E=[i for i in range(10)] if [q,w]==[0,0] else li(w)
    for e in E:
      R=[i for i in range(10)] if [q,w,e]==[0,0,0] else li(e)
      for r in R:
        T=[i for i in range(10)] if [q,w,r,e]==[0,0,0,0] else li(r)
        for t in T:
          Y=[i for i in range(10)] if [q,w,e,r,t]==[0,0,0,0,0] else li(t)
          for y in Y:
            U=[i for i in range(10)] if [q,w,e,r,t,y]==[0,0,0,0,0,0] else li(y)
            for u in U:
              I=[i for i in range(10)] if [q,w,e,r,t,y,u]==[0,0,0,0,0,0,0] else li(u)
              for i in I:
                O=[i for i in range(10)] if [q,w,e,r,t,y,u,i]==[0,0,0,0,0,0,0,0] else li(i)
                for o in O:
                  P=[i for i in range(10)] if [q,w,e,r,t,y,u,i,o]==[0,0,0,0,0,0,0,0,0] else li(o)
                  for p in P:
                    
                    ans[now]= 10**9*q + 10**8*w + 10**7*e + 10**6*r + 10**5*t + 10**4*y + 1000*u + 100*i + 10*o + p
                    
                    if now>=10**5+2 : break
                    now+=1


print(ans[n])

Solution (Python):
n=int(input())
if n<=10 : 
  print(n)
  exit()
  
ans=[0 for i in range(10**5+21)]
Q=[0,1,2,3]
def li(x):
  if x==0 : return [0,1]
  if x==9 : return [8,9]
  return [x-1,x,x+1]

now=0
for q in Q:
  W=[i for i in range(10)] if q==0 else li(q)
  for w in W:
    E=[i for i in range(10)] if [q,w]==[0,0] else li(w)
    for e in E:
      R=[i for i in range(10)] if [q,w,e]==[0,0,0] else li(e)
      for r in R:
        T=[i for i in range(10)] if [q,w,r,e]==[0,0,0,0] else li(r)
        for t in T:
          Y=[i for i in range(10)] if [q,w,e,r,t]==[0,0,0,0,0] else li(t)
          for y in Y:
            U=[i for i in range(10)] if [q,w,e,r,t,y]==[0,0,0,0,0,0] else li(y)
            for u in U:
              I=[i for i in range(10)] if [q,w,e,r,t,y,u]==[0,0,0,0,0,0,0] else li(u)
              for i in I:
                O=[i for i in range(10)] if [q,w,e,r,t,y,u,i]==[0,0,0,0,0,0,0,0] else li(i)
                for o in O:
                  P=[i for i in range(10)] if [q,w,e,r,t,y,u,i,o]==[0,0,0,0,0,0,0,0,0,0] else li(o)
                  for p in P:
                    
                    ans[now]= 10**9*q + 10**8*w + 10**7*e + 10**6*r + 10**5*t + 10**4*y + 1000*u + 100*i + 10*o + p
                    
                    if now>=10**5+2 : break
                    now+=1

ans=list(set(ans))
n-=8
ans.sort()
print(ans[n])

Solution (Python):
k = int(input())
from queue import Queue

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

Solution (Python):
k = int(input())
dp = [[0 for _ in range(10)] for __ in range(50)]
wa = [[0 for _ in range(10)] for __ in range(50)]

if k < 10:
    print(k)
    exit()

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

isFinish =False
for i in range(1,15):
    for j in range(10):
        dp[i][j] = dp[i-1][j]
        if j > 0:
            dp[i][j] += dp[i-1][j-1]
        if j < 9:
            dp[i][j] += dp[i-1][j+1]
        if j == 0: continue
        if j == 1:
            wa[i][j] = wa[i-1][9] + dp[i][j]
        else:
            wa[i][j] = wa[i][j-1] + dp[i][j]
        if wa[i][j] >= k:
            keta = i
            num = j
            isFinish = True
            break
    if isFinish: break
ans = 0
k -= wa[keta][num-1] if num > 1 else wa[keta-1][9]
while keta+1:
    ans += num * pow(10,keta)
    if keta ==0:
        break

    for i  in range(3):
        nextnum = num + i-1
        if nextnum < 0 or nextnum > 9:
            continue
        k -= dp[keta-1][nextnum]
        if k <= 0:
            k += dp[keta-1][nextnum]
            num = nextnum
            break
    keta -= 1
print(ans)

Solution (Python):


from collections import deque

K = int(input())
cnt = 0
q = deque()

for i in range(1, 10):
    q.append((str(i), i))
    cnt += 1
    if cnt == K:
        print(str(i))
        exit()

while q:
    lun, num = q.popleft()
    
    for i in range(num - 1, num + 2):
        if  i < 0 or i > 9:
            continue
        temp = lun + str(i)
        q.append((temp, i))
        cnt += 1
        if cnt == K:
            print(temp)
            exit()

Solution (Python):
from collections import deque
k=int(input())
def bfs():
    q=deque([])
    for i in range(1,10):
        q.append(str(i))
    cnt=0
    while cnt<k:
        cnt+=1
        x=q.popleft()
        r=int(x[-1])
        if 1<=r:
            q.append(x+str(r-1))
        q.append(x+str(r))
        if r<=8:
            q.append(x+str(r+1))
    return x
print(bfs())

Solution (Python):
K = int(input())
counter = 0
level = 1
theList = []
PreLevelStart,PreLevelEnd = 0,0
while counter < K:
    levelStart = counter
    if level == 1:
        for i in range(1,10,1):
            theList.append(i)
            counter += 1
    else:
        for i in range(PreLevelStart,PreLevelEnd):
            if theList[i]%10 == 0:
                theList.append(theList[i]*10)
                counter+=1
                theList.append(theList[i]*10+1)
                counter+=1
            elif theList[i]%10 == 9:
                theList.append(theList[i]*10+8)
                counter+=1
                theList.append(theList[i]*10+9)
                counter+=1
            else:
                theList.append(theList[i]*10+theList[i]%10-1)
                counter+=1
                theList.append(theList[i]*10+theList[i]%10)
                counter+=1
                theList.append(theList[i]*10+theList[i]%10+1)
                counter+=1
    PreLevelStart = levelStart
    PreLevelEnd = counter
    level = level+1
print(theList[K-1])

Solution (Python):
from collections import deque
d = deque()

k = int(input())

for i in range(1,10):
    d.append(i)
    
for i in range(k):
    x = d.popleft()
    if not x%10 == 0:
        d.append(x*10+(x%10)-1)
    d.append(x*10+(x%10))
    if not x%10 == 9:
        d.append(x*10+(x%10)+1)

print(x)

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

q = deque()
for i in range(1, 10):
    q.append((str(i), i))
    cnt += 1
    if cnt == k:
        print(str(i))
        exit()

while q:
    lun, num = q.popleft()

    for i in range(num - 1, num + 2):
        if i < 0 or i >9:continue
        temp = lun + str(i)
        q.append((temp, i))
        cnt += 1
        if cnt == k:
            print(temp)
            exit()

Solution (Python):
from collections import deque

def solve(k):
    v = []
    que = deque([x for x in range(1, 10)])
    while len(v) <= k:
        x = que.popleft()
        v.append(x)
        i = x % 10
        for j in range(max(0,i-1), min(10,i+2)):
            nx = 10*x + j
            que.append(nx)
    return sorted(v)[k-1]

k = int(input())
print(solve(k))

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

a = list()
b = list()
a2 = list()
for i in range(10):
    a.append(i)
b.extend(a)
a2.extend(a)
for i in range(10):
    a = list()
    dig = 10 ** i
    for c in a2:
        tmpc = c//dig
        min = tmpc - 1
        if min < 0:
            min = 0
        max = tmpc + 1
        if max > 9:
            max = 9
        for j in range(min,max+1):
            a.append(j*10*dig+c)
    b.extend(a)
    a2 = a
    
b=list(set(b))
b.sort()
print(b[k])

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

Solution (Python):
K=int(input())
 
from collections import deque
query=deque()
 
for i in range(1,10):
    query.append(i)
cnt=0

while cnt<K:
    num=query.popleft()
    cnt +=1
    one=num%10
    if one == 0:
        query.append(num*10+one )
        query.append(num*10+(one+1))
    if one!=0 and one!=9:
        query.append(num*10+(one-1))
        query.append(num*10+one)
        query.append(num*10+(one+1))
    if one == 9:
        query.append(num*10+(one-1))
        query.append(num*10+one)

print(num)

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

Solution (Python):
from collections import deque

def solve(K):
    stack = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
    for _ in range(K):
        num = stack.popleft()
        one_digit = num % 10
        if one_digit % 10 == 0:
            nexts = [num * 10, num * 10 + 1]
        elif one_digit % 10 == 9:
            nexts = [num * 10 + 8, num * 10 + 9]
        else:
            nexts = [num * 10 + one_digit - 1, num * 10 + one_digit, num * 10 + one_digit + 1]

        for n in nexts:
            stack.append(n)
    return num

if __name__ == '__main__':
    K = int(input())
    print(solve(K))

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

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

Solution (Python):
import sys
from collections import deque
K = int(input())
if K <= 9:
	print(K)
	sys.exit()
q = deque(['1', '2','3','4','5','6','7','8','9'])
cnt = 0
while True:
	cp = q.popleft()
	cnt += 1
	if cnt == K:
		ans = int(cp)
		break
	r = int(cp[-1])
	for d in [-1,0,1]:
		dd = r + d
		if 0 <= dd < 10:
			q.append(cp + str(dd))

print(ans)

Solution (Python):
from collections import deque

k = int(input())

lun = deque([])
for i in range(1,10):
    lun.append(i)

for i in range(k):
    x = lun.popleft()
    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)
print(x)

Solution (Python):
import queue

K = int(input())
q = queue.Queue()
count=0

for i in range(1,10):
    q.put(i)
x=0
while True:
    count+=1
    x = q.get()

    if count==K:
        break

    xmod10 = x%10

    if xmod10 != 0 :
        q.put(10*x + xmod10 - 1)

    q.put(10*x + xmod10)

    if xmod10 != 9:
        q.put(10*x + xmod10 + 1)

print(x)

Solution (Python):
def main():
    k = int(input())
    if k <= 9:
        print(k)
        exit()
    count = 9
    l = [i for i in range(1,10)]
    while True:
        ins_l = []
        for x in l:
            y = x % 10
            if y != 0:
                z = x * 10 + y - 1
                ins_l.append(z)
                count += 1
                if count == k:
                    print(z)
                    exit()

            z = x * 10 + y
            ins_l.append(z)
            count += 1
            if count == k:
                print(z)
                exit()

            if y != 9:
                z = x * 10 + y + 1
                ins_l.append(z)
                count += 1
                if count == k:
                    print(z)
                    exit()
        l = ins_l

if __name__ == "__main__":
    main()

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

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):
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 not x%10 == 0:
        q.put(10*x+(x%10)-1)
    q.put(10*x+(x%10))
    if not x%10 == 9:
        q.put(10*x+(x%10)+1)

print(x)

Solution (Python):
K = int(input())
a = ["1","2","3","4","5","6","7","8","9"]
for i in range(K):
    if  a[i][-1] == "9":
        a.append(a[i]+str(int(a[i][-1])-1))
        a.append(a[i]+str(int(a[i][-1])))
    elif a[i][-1] == "0":
        a.append(a[i]+str(int(a[i][-1])))
        a.append(a[i]+str(int(a[i][-1])+1))
    else:
        a.append(a[i]+str(int(a[i][-1])-1))
        a.append(a[i]+str(int(a[i][-1])))
        a.append(a[i]+str(int(a[i][-1])+1))
print(a[K-1])

Solution (Python):
K = int(input())
a = ["1","2","3","4","5","6","7","8","9"]
for i in range(K):
    if  a[i][-1] == "9":
        a.append(a[i]+str(int(a[i][-1])-1))
        a.append(a[i]+str(int(a[i][-1])))
    elif a[i][-1] == "0":
            a.append(a[i]+str(int(a[i][-1])))
            a.append(a[i]+str(int(a[i][-1])+1))
    else:
            a.append(a[i]+str(int(a[i][-1])-1))
            a.append(a[i]+str(int(a[i][-1])))
            a.append(a[i]+str(int(a[i][-1])+1))
print(a[K-1])

Solution (Python):
def solve(K):
    ref = [[['0'], ['1'], ['2'], ['3'], ['4'], ['5'], ['6'], ['7'], ['8'], ['9']]]
    if K < 10:
        return ref[0][K][0]

    rest = K - 9
    i = 0
    while True:
        i += 1
        ref.append([[] for _ in range(10)])
        for j in range(10):
            if j == 0:
                for r in ref[i-1][j] + ref[i-1][j+1]:
                    ref[i][j].append(str(j) + r)
            elif j == 9:
                for r in ref[i-1][j-1] + ref[i-1][j]:
                    ref[i][j].append(str(j) + r)
                    rest -= 1
                    if rest == 0:
                        return str(j) + r
            else:
                for r in ref[i-1][j-1] + ref[i-1][j] + ref[i-1][j+1]:
                    ref[i][j].append(str(j) + r)
                    rest -= 1
                    if rest == 0:
                        return str(j) + r

if __name__ == '__main__':
    K = int(input())
    print(solve(K))

Solution (Python):
k = int(input())
lundex = [1,2,3,4,5,6,7,8,9]
count = 9
for i in lundex:
    for j in range(0,10):
        new = str(i)+str(j)
        l = len(new)
        if abs(int(new[l-2])-int(new[l-1]))<=1:
            lundex.append(int(new))
            count += 1
        if count >= k:
            break
    if count >= k:
        break
print(lundex[k-1])

Solution (Python):
K = int(input())
dic = {i+1:[] for i in range(11)}

dic[1] = [str(i+1) for i in range(9)]

if K < 10:
    print(dic[1][K-1])
else:
    cnt = 9
    ans = -1
    for i, nums in dic.items():
        for n in nums:
            ds = n[-1]
            dd = int(ds)
            if dd > 0:
                dic[i+1].append(n + str(int(ds)-1))
                cnt += 1
            dic[i+1].append(n + str(int(ds)))
            cnt += 1
            if dd < 9:
                dic[i+1].append(n + str(int(ds)+1))
                cnt += 1
        if cnt >= K:
            ans = dic[i+1][K-cnt-1]
            break
    print(ans)

Solution (Python):
def main():
  n=int(input())
  l=0
  runrun=[str(x) for x in range(1,10)]
  while len(runrun)<n:
    l+=1
    def addrunrun(s,n,l):
      if l==0:
        runrun.append(s)
      elif n==0:
        addrunrun(s+"0",0,l-1)
        addrunrun(s+"1",1,l-1)
      elif n==9:
        addrunrun(s+"8",8,l-1)
        addrunrun(s+"9",9,l-1)
      else:
        addrunrun(s+str(n-1),n-1,l-1)
        addrunrun(s+str(n),n,l-1)
        addrunrun(s+str(n+1),n+1,l-1)
    for i in range(1,10):
      addrunrun(str(i),i,l)
  print(runrun[n-1])
main()

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

def func(x):
    y = x%10
    if y == 0:
        return [x*10,x*10+1]
    elif y == 9:
        return [x*10+8,x*10+9]
    else:
        return [x*10+y-1,x*10+y,x*10+y+1]

li1 = l[:]
li2 = []
if K < 10:
    print(K)
else:
    while True:
        for i in li1:
            a = func(i)
            li2.extend(a)
        l.extend(li2)
        if len(l) >=K:
            break
        else:
            li1 = li2[:]
            li2 = []
    print(l[K-1])

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

if k<=12:
    print(k)
else:
    while 1:
        ans += 1
        a = dq.popleft()
        if ans == k:
            print(int(a))
            exit()
        for i in num[max(0,int(a[-1])-1):min(10,int(a[-1])+2)]:
            dq.append(a+i)