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

Solution (Python):
from collections import deque

K = int(input())

q = deque(range(1,10))

for _ in range(K):
    x = q.popleft()
    r = x%10
    if r == 0:
        q.append(x*10)
        q.append(x*10+1)
    elif r == 9:
        q.append(x*10+8)
        q.append(x*10+9)

    else:
        q.append(x*10+r-1)
        q.append(x*10+r)
        q.append(x*10+r+1)
print(x)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

k = int(readline())
q = [(i + 1) for i in range(9)]
if k < 10:
    print(k)
    exit()
cnt = 9
while q:
    x = q.pop(0)
    y = int(str(x)[-1])
    if y != 0:
        cnt += 1
        if cnt == k:
            print(10 * x + y - 1)
            exit()
        q.append(10 * x + y - 1)
    cnt += 1
    if cnt == k:
        print(10 * x + y)
        exit()
    q.append(10 * x + y)
    if y != 9:
        cnt += 1
        if cnt == k:
            print(10 * x + y + 1)
            exit()
        q.append(10 * x + y + 1)

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


def bfs():
  
  q=[""]
  count=0
  while count<K:
    now=q.pop(0)
    if now=="":
      for n in range(1,10):
        new=now+str(n)
        q.append(new)
        count+=1
        if count==K:
          return new
    elif now[-1]=="0":
      for n in ["0","1"]:
        new=now+n
        q.append(new)
        count+=1
        if count==K:
          return new
    elif now[-1]=="9":
      for n in ["8","9"]:
        new=now+n
        q.append(new)
        count+=1
        if count==K:
          return new
    else:
      s=int(now[-1])
      for n in [s-1,s,s+1]:
        new=now+str(n)
        q.append(new)
        count+=1
        if count==K:
          return new
      
print(bfs())

Solution (Python):
def dfs(n):
    if int(n) >= 3234566668:
        return None
    else:
        li.append(int(n))
        if n[-1] == "0":
            dfs(n + n[-1])
            dfs(n + str(int(n[-1]) + 1))
        elif n[-1] == "9":
            dfs(n + str(int(n[-1]) - 1))
            dfs(n + n[-1])
        else:
            dfs(n + str(int(n[-1]) - 1))
            dfs(n + n[-1])
            dfs(n + str(int(n[-1]) + 1))
k = int(input())
l = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
li = []
for i in l:
    dfs(i)
li.sort()
print(li[k - 1])

Solution (Python):
def resolve():
    from collections import deque
    k = int(input())
    a = [1,2,3,4,5,6,7,8,9]
    a = deque(a)
    c = 0
    if k < 10:
        print(k)
    else:
        while c != k:
            c += 1
            t = a.popleft()
            if t % 10 == 0:
                a.append(t*10)
                a.append(t*10+1)
            elif t % 10 == 9:
                a.append(t * 10 + 8)
                a.append(t * 10 + 9)
            else:
                a.append(t * 10 + (t%10)-1)
                a.append(t * 10 + (t%10))
                a.append(t * 10 + (t%10)+1)
        print(t)
resolve()

Solution (Python):
from collections import deque

que=deque([1,2,3,4,5,6,7,8,9])
lunlun=deque([])
while len(lunlun)<10**5:
    p=que.popleft()
    lunlun.append(p)
    if p%10!=0:
        que.append(p*10+(p%10-1))
    que.append(p*10+(p%10))
    if p%10!=9:
        que.append(p*10+(p%10+1))

k=int(input())
print(lunlun[k-1])

Solution (Python):
def resolve():
    k = int(input())
    from collections import deque
    a = [1,2,3,4,5,6,7,8,9]
    b = [1,2,3,4,5,6,7,8,9]
    if k < 10:
        print(a[k-1])
    else:
        a = deque(a)
        b = deque(b)
        while len(b) <= k:
            test = a.popleft()
            mtest = test % 10
            if mtest == 0:
                a.append (test*10)
                a.append (test*10+mtest+1)
                b.append (test*10)
                b.append (test*10+mtest+1)
            elif mtest == 9:
                a.append (test*10 + mtest-1)
                a.append (test*10 + mtest)
                b.append (test*10 + mtest-1)
                b.append (test*10 + mtest)
            else:
                a.append (test*10 + mtest-1)
                a.append (test*10 + mtest)
                a.append (test*10 + mtest+1)
                b.append (test*10 + mtest-1)
                b.append (test*10 + mtest)
                b.append (test*10 + mtest+1)
        print(b[k-1])
resolve()

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

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

while stack:
    n = stack.pop()
    count += 1
    if count == K:
        print(n)
        break
    if n%10 != 0:
        stack.appendleft(n*10+n%10-1)
    
    stack.appendleft(n*10+n%10)

    if n%10 != 9:
        stack.appendleft(n*10+n%10+1)

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

q = collections.deque([i for i in range(1, 10)])
count = 0
while(q):
    count += 1
    x = q.popleft()
    if count == K:
        print(x)
        break
    if x % 10 != 0:
        q.append(x*10 + (x % 10 - 1))
    q.append(x*10 + (x % 10))
    if x % 10 != 9:
        q.append(x*10 + (x % 10 + 1))

Solution (Python):
from collections import deque

K = int(input())

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

cnt  = 0


while q:
    x = q.popleft()

    cnt += 1
    if cnt == K:
        print(x)
        break

    y = x % 10
    z = 10*x+y
    if y != 0:
        q.append(z-1)
    q.append(z)
    if y != 9:
        q.append(z+1)

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

Solution (Python):


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

Solution (Python):



import queue 










mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

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

def main():
    k = int(input())
    q = queue.Queue()
    for i in range(1,10):
        q.put(i)
    while not q.empty():
        x = q.get()
        k -= 1
        if k==0:
            print(x)
            return
        if x%10==0:
            q.put(x*10+(x%10))
            q.put(x*10+(x%10+1))
        elif x%10==9:
            q.put(x*10+(x%10-1))
            q.put(x*10+(x%10))
        else:
            q.put(x*10+(x%10-1))
            q.put(x*10+(x%10))
            q.put(x*10+(x%10+1))
    return

if __name__=='__main__':
    main()

Solution (Python):


from collections import deque
k=int(input())
ans=[]
d=deque([1,2,3,4,5,6,7,8,9])
c=0
while c<11:
    q=d.popleft()
    ans.append(q)
    c=len(str(q))
    b=q%10
    if b!=0:
        d.append(q*10+b-1)
    d.append(q*10+b)
    if b!=9:
        d.append(q*10+b+1)
    
print(ans[k-1])

Solution (Python):
import sys
from collections import deque
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

K = I()
d = deque([i for i in range(1,10)])

cnt = 0
while True:
  num = d.popleft()
  cnt += 1
  if cnt == K:
    print(num)
    break
  tmp = int(str(num)[-1])
  for i in range(tmp-1,tmp+2):
    if i == -1 or i == 10:
      continue
    else:
      d.append(str(num) + str(i))

Solution (Python):
import sys
from collections import deque
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

lunlun=deque()

def dfs(now):
    if len(now)>10:return
    lunlun.append(int(now))
    l=now[-1]
    
    if l!="0":
        dfs(now+str(int(l)-1))
    if l!="9":
        dfs(now+str(int(l)+1))
    dfs(now+l)

k=int(input().rstrip())
for i in range(1,10):
    dfs(str(i))


print(sorted(lunlun)[k-1])

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

num_list = [1,2,3,4,5,6,7,8,9]
num_a = ['0', '1']
num_b = ['8', '9']

for i in num_list:
    if str(i)[-1] == '0':
        for j in num_a:
            num_list.append(int(str(i)+j))
    elif str(i)[-1] == '9':
        for j in num_b:
            num_list.append(int(str(i)+j))
    else:
        num = int(str(i)[-1])
        for j in range(num-1, num+2):
            num_list.append(int(str(i)+str(j)))
    if len(num_list) > k:
        break

print(num_list[k-1])

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

import queue
q = queue.Queue()

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

cnt = 0

while True:
    n = q.get()
    cnt += 1
    if cnt == K:
        break
    if n % 10 != 0:
        q.put(n * 10 + n % 10 - 1)
    q.put(n * 10 + n % 10)
    if n % 10 != 9:
        q.put(n * 10 + n % 10 + 1)
print(n)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

k = int(input())
ans = []
def dfs(string):
  if int(string) > 3234566667: return
  ans.append(int(string))
  botom = string[-1]
  intbotom = int(botom)
  if 0 <= intbotom -1 :
    dfs(string + str(intbotom-1))
  dfs(string+botom)
  if intbotom + 1 <= 9:
    dfs(string + str(intbotom+1))
for i in range(1,10):
  dfs(str(i))
ans .sort()

print(ans[k-1])

Solution (Python):
from collections import deque


def main():
    k = int(input())
    q = deque([i for i in range(1, 10)])
    answer = 0
    for i in range(k):
        now = q.popleft()
        answer = now
        if now % 10 != 0:
            q.append(10 * now + now % 10 - 1)
        q.append(10 * now + now % 10)
        if now % 10 != 9:
            q.append(10 * now + now % 10 + 1)
    print(answer)


if __name__ == '__main__':
    main()

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


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

for i in range(1,10):
    dfs(str(i))

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

Solution (Python):
k=int(input())
a,b,c=['1','2','3','4','5','6','7','8','9'],[],[]
for i in range(10):
    c.extend(a)
    for j in range(len(a)):
        if int(a[j])>323456666:
            continue
        if a[j][-1]!='0':
            b.append(a[j]+str(int(a[j][-1])-1))
        b.append(a[j]+a[j][-1])
        if a[j][-1]!='9':
            b.append(a[j]+str(int(a[j][-1])+1))
    a=b
    b=[]
c.extend(a)
print(sorted(list(map(int,c)))[k-1])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())

res = set()
def dfs(x, s):
  global res
  res.add(int("".join(s)))
  if x == 10: return
  for i in range(3):
    if (int(s[-1]) + i - 1) in range(10):
      y = s + [str(int(s[-1]) + i - 1)]
      dfs(x + 1, y)
for i in range(1, 10): dfs(1, [str(i)])
res = sorted(res)
print(res[N - 1])

Solution (Python):
from heapq import heapify, heappush, heappop

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


K = int(input())

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

for _ in range(K-1):
    now = heappop(lunlun)
    for i in next_num(int(str(now)[-1])):
        heappush(lunlun, now*10+i)

print(lunlun[0])

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

k = ni()

def bfs():
    q = deque()
    for i in range(1, 10):
        q.append(i)
    cnt = 1
    while len(q):
        p = q.popleft()
        if cnt == k:
            return p
        if p % 10 != 0:
            q.append(p * 10 + (p % 10 - 1))
        q.append(p * 10 + p % 10)
        if p % 10 != 9:
            q.append(p * 10 + (p % 10 + 1))
        cnt += 1

print(bfs())

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    K = int(input())
    q = deque()
    for i in range(9): q.append((i + 1, i + 1))
    lunlun = 1
    while lunlun < K:
        nowNum, lastNum = q.popleft()
        if lastNum > 0: q.append((nowNum * 10 + lastNum - 1, lastNum - 1))
        q.append((nowNum * 10 + lastNum, lastNum))
        if lastNum < 9: q.append((nowNum * 10 + lastNum + 1, lastNum + 1))
        lunlun += 1
    ans, lastNum = q.popleft()
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque

K = int(input())

que = deque([i for i in range(1, 10)])
ans = []
while len(ans) <= K + 10:
    now = que.popleft()
    ans.append(now)

    b = now % 10
    for i in range(max(0, b - 1), min(10, b + 2)):
        que.append(now * 10 + i)

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

Solution (Python):
k = int(input())
que = []
for i in range(1,10):
  que.append(i)
ct = 0
while(len(que) < k):
  ct += 1
  value = que[0]
  que.remove(value)
  for i in [-1,0,1]:
    if 0 <= (value%10) + i and (value%10) + i <= 9:
      tmp = 10*value + (value%10) + i
      que.append(tmp)  
print(que[k-1-ct])

Solution (Python):
import queue
def main():
    q = queue.Queue()
    for i in range(1,10):
        q.put(i)
    
    k = int(input())
    q_list = []
    while(len(q_list) <= k):
        value = q.get()
        for i in [-1,0,1]:
            if 0 <= (value%10) + i and (value%10) + i <= 9:
                tmp = 10*value + (value%10) + i
                q.put(tmp)
        q_list.append(value)
    print(q_list[k-1])
    return 

if __name__ == "__main__":
    main()

Solution (Python):
K = int(input())
ans = []
def func(s):
    x = int(s)
    if x <= 3234566667:
        ans.append(x)
        tail = int(s[-1])
        for i in [-1, 0, 1]:
            p = i+tail
            if p not in list(range(10)):
                continue
            func(s+str(p))

for i in range(1, 10):
    func(str(i))

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

Solution (Python):


K = int(input())

N = [1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 0

while len(N) < K:
    n = int(str(N[i]) + str(N[i])[-1:])
    if str(n)[-1:] == '0':
        N += [n, n + 1]
    elif str(n)[-1:] == '9':
        N += [n - 1, n]
    else:
        N += [n - 1, n, n + 1]
    i += 1

print(N[K - 1])

Solution (Python):


K = int(input())
stack = [1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 0
while len(stack) < K:
    first = int(str(stack[i])[-1:])
    if first == 0:
        stack.append(int(str(stack[i]) + str(first)))
        stack.append(int(str(stack[i]) + str(first + 1)))
    elif first == 9:
        stack.append(int(str(stack[i]) + str(first - 1)))
        stack.append(int(str(stack[i]) + str(first)))
    else:
        stack.append(int(str(stack[i]) + str(first - 1)))
        stack.append(int(str(stack[i]) + str(first)))
        stack.append(int(str(stack[i]) + str(first + 1)))        
    i += 1

print(stack[K - 1])

Solution (Python):
from collections import deque
k=int(input())
cnt=0
ans=0
q=deque()
q.extend([1,2,3,4,5,6,7,8,9])

while(cnt<k):
    ans=q.popleft()
    cnt+=1

    one_digit=ans%10
    if(one_digit==0):
        q.append(int(str(ans) + '0'))
        q.append(int(str(ans) + '1'))
    elif(one_digit==9):
        q.append(int(str(ans) + '8'))
        q.append(int(str(ans) + '9'))
    else:
        q.append(int(str(ans) + str(one_digit-1)))
        q.append(int(str(ans) + str(one_digit)))
        q.append(int(str(ans) + str(one_digit+1)))
print(ans)

Solution (Python):
from collections import deque
K = int(input())
if K <= 9: ans = K
cnt = 9
dq = deque(list(range(1, 10)))

while cnt <= K:
    d = dq.popleft()
    for i in [-1, 0, 1]:
        if d % 10 == 0 and i == -1:continue
        if d % 10 == 9 and i == 1:continue
        dq.append(d * 10 + d % 10 + i)
        cnt += 1
        if cnt == K:
            ans = d * 10 + d % 10 + i
            break
        
print(ans)

Solution (Python):
n = int(input())
a = list(map(str, (range(1, 10))))
total = a[:]
cnt = 9
while cnt < n:
    new = []
    for i in a:
        if i[-1] == "0":
            new.append(i + "0")
            new.append(i + "1")
            cnt += 2
            if cnt >= n:
                break
        elif i[-1] == "9":
            new.append(i + "8")
            new.append(i + "9")
            cnt += 2
            if cnt >= n:
                break
        else:
            new.append(i + str(int(i[-1]) -1))
            new.append(i + str(int(i[-1])))
            new.append(i + str(int(i[-1]) + 1))
            cnt += 3
            if cnt >= n:
                break
    total += new[:]
    a = new[:]
                
print(total[n-1])

Solution (Python):
n = int(input())
a = list(map(str, (range(1, 10))))
total = a[:]
cnt = 9
while cnt < n:
    new = []
    for i in a:
        if i[-1] == "0":
            new.append(i + "0")
            new.append(i + "1")
            cnt += 2
            if cnt >= n:
                break
        elif i[-1] == "9":
            new.append(i + "8")
            new.append(i + "9")
            cnt += 2
            if cnt >= n:
                break
        else:
            new.append(i + str(int(i[-1]) -1))
            new.append(i + str(int(i[-1])))
            new.append(i + str(int(i[-1]) + 1))
            cnt += 3
            if cnt >= n:
                break
    total += new[:]
    a = new[:]
                
print(total[n-1])

Solution (Python):



import sys
input = sys.stdin.readline
from collections import deque

def main():
    K = int(input())
    q = deque([])               
    for i in range(1,10):
        q.append(i) 
    ret = []
    while len(ret)<K:
        p = q.popleft()         
        ret.append(p)
        pl = p%10
        if pl >= 1:
            q.append(p*10 + pl-1)
        q.append(p*10 + pl)
        if pl <= 8:
            q.append(p*10 + pl+1)
    print(ret[-1])

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
import queue
import sys

k=int(input())
q=queue.Queue()
for i in range(1,10):
    q.put(i)
if k<10:
    print(k)
    sys.exit()
i=0
while i!=k:
    i+=1
    now=q.get()
    nowm=now%10
    if nowm!=0 and nowm!=9:
        q.put(now*10+nowm-1)
        q.put(now * 10 + nowm)
        q.put(now * 10 + nowm +1)
    elif nowm==0:
        q.put(now * 10 + nowm)
        q.put(now * 10 + nowm + 1)
    elif nowm==9:
        q.put(now * 10 + nowm - 1)
        q.put(now * 10 + nowm)
print(now)

Solution (Python):
k = int(input())
li =[i+1 for i in range(9)]

c = 0
while len(li) < k:
    if li[c]%10 != 0:
        li.append(li[c]*10+li[c]%10-1)
    li.append(li[c]*10+li[c]%10)
    if li[c]%10 != 9:
        li.append(li[c]*10+li[c]%10+1)
    c +=1
    
print(li[k-1])

Solution (Python):
def solver(d,num,A):
    A.append(num)
    if d == 10:
        return
    
    for x in range(-1,2):
        add = num%10 + x
        if add >=0 and add <=9:
            solver(d+1,(num*10+add),A)
A =[]
K = int(input())
if K <=9:
    print(K)
else:
    for t in range(1,10):
        solver(1,t,A)
    A.sort()
    print(A[K-1])

Solution (Python):
def solve(n):
    Mrepeat = 10
    seedlist = [[str(i+j-1) for i in range(3)] for j in range(10)]
    seedlist[0] = ['0', '1']
    seedlist[9] = ['8', '9']
    numbers = [[] for i in range(Mrepeat + 1)]
    numbers[0] = [i for i in range(1,10)]
    for i in range(Mrepeat):
        for num in numbers[i]:
            for tmp in seedlist[num % 10]:
                numbers[i+1].append(int(str(num) + tmp))
    ans = []
    for i in numbers:
        ans += i
    return ans[n-1]

def main():
    n = int(input())
    print(solve(n))

if __name__ == '__main__':
    main()

Solution (Python):
def solve(n):
    Mrepeat = 10
    seedlist = [[str(i+j-1) for i in range(3)] for j in range(10)]
    seedlist[0] = ['0', '1']
    seedlist[9] = ['8', '9']
    numbers = [[] for i in range(Mrepeat + 1)]
    numbers[0] = [i for i in range(1,10)]
    for i in range(Mrepeat):
        for num in numbers[i]:
            for tmp in seedlist[num % 10]:
                numbers[i+1].append(int(str(num) + tmp))
    ans = []
    for i in numbers:
        ans += i
    return ans[n-1]

def main():
    n = int(input())
    print(solve(n))

if __name__ == '__main__':
    main()

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

Solution (Python):
from queue import Queue

K = int(input())
Q = Queue()

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

lun = -1
for i in range(K):
    x = Q.get()
    
    lun = x

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

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

q=Queue()

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

for k in range(K):
    a=q.get()
    
    if k!=K-1:
        b=a%10
        for j in range(max(0,b-1),min(9,b+1)+1):
            q.put(int(str(a)+str(j)))
    else:
        print(a)

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):
import queue

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

k = int(input())
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):
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())

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

    lunlun = [i for i in range(1,10)]
    m = 0

    while len(lunlun) < K:
        x = lunlun[m]
        btm = x % 10

        if btm - 1 >= 0:
            lunlun.append(10*x+btm-1)

        lunlun.append(10*x+btm)

        if btm + 1 < 10:
            lunlun.append(10*x+btm+1)

        m += 1

    print(lunlun[::-1][len(lunlun)-K])

if __name__ == "__main__":
  main()

Solution (Python):
import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def get_lcm(num):
    return reduce(lambda x,y:(x * y) // fractions.gcd(x, y), num, 1)

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

    lunlun = [i for i in range(1,10)]
    m = 0

    while len(lunlun) < K:
        x = lunlun[m]
        btm = x % 10

        if btm - 1 >= 0:
            lunlun.append(10*x+btm-1)

        lunlun.append(10*x+btm)

        if btm + 1 < 10:
            lunlun.append(10*x+btm+1)

        m += 1

    print(lunlun[::-1][len(lunlun)-K])

if __name__ == "__main__":
  main()

Solution (Python):
import queue

k = int(input())

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

Solution (Python):
from sys import stdin
import math

lun_list = []

data = stdin.readline().rstrip().split()
K = int(data[0])

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

n_f_idx, n_l_idx = 0, 8

while(1):
    f_idx, l_idx = n_f_idx, n_l_idx
    for idx in range(f_idx, l_idx+1):
        for j in range(10):
            if abs(int(str(lun_list[idx])[-1]) - j) > 1:
                continue
            else:
                num = int(str(lun_list[idx]) + str(j))
                lun_list.append(num)
                n_l_idx += 1
    
    n_f_idx = l_idx + 1

    if len(lun_list) > K:
        print(lun_list[K-1])
        break

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

Solution (Python):

import sys

sys.setrecursionlimit(10**9)

from functools import lru_cache
@lru_cache(maxsize=None)

def runrun(n):
    if n == 1:
        return [['1','2','3','4','5','6','7','8','9']]
    else:
        li = runrun(n-1)
        li2 = []
        for i in range(len(li[n-2])):
            p = int(li[n-2][i][-1])
            if p == 0:
                li2.append(li[n-2][i]+'0')
                li2.append(li[n-2][i]+'1')
            elif p == 9:
                li2.append(li[n-2][i]+str(8))
                li2.append(li[n-2][i]+'9')
            else:
                li2.append(li[n-2][i]+str(p-1))
                li2.append(li[n-2][i]+str(p))
                li2.append(li[n-2][i]+str(p+1))
        li2 =[li2]
        li.extend(li2)
        return li
    


x = int(input())
t = True
k=1
b = 0
while t:
    a = runrun(k)
    b = 0
    
    for i in range(len(a)):
        b+=(len(a[i]))
        
    if x <= b:
        t = False
        if k == 1:
            print(x)
        else:
            tmp = runrun(k-1)
            c = 0

            for i in range(len(tmp)):
                c += (len(tmp[i]))
            s = a[k-1][x-c-1]
            print(int(s))
    else:
        k += 1

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

























def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007




def main():
	K = inputInt()
	counts = 0
	DP = []
	tmp = ["1","2","3","4","5","6","7","8","9"]
	DP.append(tmp)
	ans = [1,2,3,4,5,6,7,8,9]

	for i in range(10):
		tmp = []
		for j_str in DP[i]:
			sita = ""
			ue = ""
			namaka = j_str[-1]

			if j_str[-1] == "0":
				ue = str(int(j_str[-1]) + 1)
			elif j_str[-1] == "9":
				sita = str(int(j_str[-1]) - 1)
			else:
				ue = str(int(j_str[-1]) + 1)
				sita = str(int(j_str[-1]) - 1)

			tmp.append(j_str + namaka)
			ans.append(int(j_str + namaka))

			if sita == "":
				tmp.append(j_str + ue)
				ans.append(int(j_str + ue))
			elif ue == "":
				tmp.append(j_str + sita)
				ans.append(int(j_str + sita))
			else:
				tmp.append(j_str + ue)
				ans.append(int(j_str + ue))
				tmp.append(j_str + sita)
				ans.append(int(j_str + sita))

		DP.append(tmp)

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







def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

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

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

Solution (Python):
k = int(input())
lunlun = [0] * 100
lunlun[1] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 1

for _ in range(9):
    n = len(lunlun[i])
    lunlun[i+1] = []
    for x in lunlun[i]:
        r = x%10
        if r > 0:
            lunlun[i+1].append(10*x + r-1)
        lunlun[i+1].append(10*x + r)
        if r < 9:
            lunlun[i+1].append(10*x + r+1)
    i += 1

for i in range(1, 11):
    for j in range(len(lunlun[i])):
        k -= 1
        if k == 0:
            print(lunlun[i][j])
            exit()

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

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

for j in range(0,k):
  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(t)