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

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

while K != k:
    n = numbers.popleft()
    if n % 10 == 0:
        numbers.append(n * 10)
        numbers.append(n * 10 + 1)
    elif n % 10 == 9:
        numbers.append(n * 10 + 8)
        numbers.append(n * 10 + 9)
    else:
        d = n % 10
        numbers.append(n * 10 + d - 1)
        numbers.append(n * 10 + d)
        numbers.append(n * 10 + d + 1)

    k += 1
    ans = n

print(ans)

Solution (Python):
from collections import deque

N = int(input())

D = deque(['1','2','3','4','5','6','7','8','9'])
if N < 10:
  print(list(D)[N-1])
else:
  cnt = 9
  while cnt < N:
    a = D.popleft()
    for k in range(-1, 2):
      _plus = int(a[-1]) + k
      if not(_plus >= 0 and _plus <= 9):
        continue
      u = a + str(_plus)
      D.append(u)
      cnt +=1
      
      if cnt == N:
        print(u)
        break
    else:
      continue
    break

Solution (Python):


import sys

sys.setrecursionlimit(100000)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7





K = int(input())

def f(A):
    R = []
    for a in A:
        d = a%10
        if d == 0:
            R.append(a*10)
            R.append(a*10+1)
        elif d == 9:
            R.append(a*10 + 8)
            R.append(a*10 + 9)
        else:
            R.append(a*10 + d - 1)
            R.append(a*10 + d)
            R.append(a*10 + d + 1)
    return R

A = list(range(1,10))
tab = list(A)

while len(tab) < K:
    ret = f(A)
    A = ret
    tab += ret
    

tab = sorted(tab)


print(tab[K-1])

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


def is_lunlun(i):
    result = -1
    n = [ord(c) - 48 for c in str(i)]
    for j in range(len(n) - 1):
        if abs(n[j] - n[j + 1]) <= 1:
            continue
        if n[j] < n[j + 1]:
            for k in range(j + 1, len(n)):
                n[k] = max(n[k - 1] - 1, 0)
            result = int(''.join(str(k) for k in n))
            result += 10 ** (len(n) - (j + 1))
        else:
            result = int(''.join(str(k) for k in n))
            result += 10 ** (len(n) - (j + 2))
        break
    return result


i = 1
while True:
    
    t = is_lunlun(i)
    if t == -1:
        K -= 1
        if K == 0:
            print(i)
            exit()
        i += 1
    else:
        i = t

Solution (Python):
import queue

K = int(input())

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

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

print(lunlun)

Solution (Python):

import math
import copy

K = int(input())

keta = 1
lunlun_numbers_list = [1,2,3,4,5,6,7,8,9]
lunlun_numbers_numer = 9

if K <=9:
    print(lunlun_numbers_list[K-1])
else:
    while 1:
        new_lunlun_numbers_list = list()
        for lower_keta in lunlun_numbers_list:
            ketasu = int(math.log10(lower_keta)//1 + 1)

            if lower_keta>=10:
                last_keta = lower_keta - ((lower_keta//10) * 10)
            else:
                last_keta = lower_keta

            

            if last_keta !=0: 
                new_lunlun_numbers_list.append(lower_keta*10 + last_keta - 1)
            
            new_lunlun_numbers_list.append(lower_keta*10 + last_keta)

            if last_keta !=9:
                new_lunlun_numbers_list.append(lower_keta*10 + last_keta + 1)

        if len(new_lunlun_numbers_list)+lunlun_numbers_numer >= K:
            new_lunlun_numbers_list.sort(reverse=False)
            print(new_lunlun_numbers_list[K-lunlun_numbers_numer-1])
            
            break
        else:
            lunlun_numbers_numer+=len(new_lunlun_numbers_list)

        lunlun_numbers_list = copy.copy(new_lunlun_numbers_list)

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

Solution (Python):
import queue

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

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

for i in range(k):
	output = q.get()
	if output % 10 == 0:
		q.put(output*10)
		q.put(output*10 + 1)
	elif output % 10 == 9:
		q.put(output*10 + 8)
		q.put(output*10 + 9)
	else:
		a = output % 10
		q.put(output*10 + a - 1)
		q.put(output*10 + a )
		q.put(output*10 + a + 1)

print(output)

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

Solution (Python):
from collections import deque

K = int(input())

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

for i in range(K-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(Q.popleft())

Solution (Python):
import heapq

K = int(input())

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

for i in range(K-1):
    x = heapq.heappop(Q)
    if x % 10 != 0:
        heapq.heappush(Q,10*x+x%10-1)
    heapq.heappush(Q,10*x+x%10)
    if x % 10 != 9:
        heapq.heappush(Q,10*x+x%10+1)

print(heapq.heappop(Q))

Solution (Python):

DATA = """
100000
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

def Calc():
	K = [int(i) for i in get_line().strip().split(" ")][0]
	ret = [str(_) for _ in range(1,10)]
	size = len(ret)
	start = 0
	count = len(ret)
	while(size < K):
		for i in range(start, size):
			v = int(ret[i][-1])
			ll = ret[i]
			if not v == 0:
				count += 1
				ret.append(ll + str(v - 1))
			ret.append(ll + str(v))
			count += 1
			if not v == 9:
				count += 1
				ret.append(ll + str(v+1))

			if count >= K:
				break
		if count >= K:
			break
		start = size
		size = len(ret)
	print (ret[K-1])
Calc()

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

from collections import deque
num=deque()
for i in range(1,10):
  num.append(i)

for j in range(K):
  l=num.popleft()
  if l%10 !=0:
    num.append(l*10+(l%10-1))
  num.append(l*10+(l %10))
  if l%10 != 9:
    num.append(l*10+(l%10+1))

print(l)

Solution (Python):


import queue
k = int(input())

q = queue.Queue()

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

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

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

from collections import deque
d = deque([])
for i in range(1,10):
    d.append(i)
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())

que = deque([])
for i in range(1,10):
    que.appendleft(i)


for i in range(k):
    x = que.pop()
    if x % 10 != 0:
        que.appendleft(10*x+(x%10)-1)
    
    que.appendleft(10*x+(x%10))
    
    if x % 10 != 9:
        que.appendleft(10*x+(x%10)+1)

print(x)

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

Solution (Python):
def main():
    from queue import Queue
    k = int(input())
    q = Queue()
    for i in range(1,10):
        q.put(i)
    cnt = 0
    while cnt!= k:
        x = q.get()
        cnt += 1
        if x%10!=0:
            q.put(x*10+x%10-1)
        q.put(x*10+x%10)
        if x%10!=9:
            q.put(x*10+x%10+1)
    print(x)

            
if __name__ == "__main__":
    main()

Solution (Python):
k=int(input())
index=0
chk_num=0
keta=0
str_num=""
while index<k:
  chk_num+=1
  str_num=str(chk_num)
  keta=len(str_num)
  index+=1
  if keta!=1:
    for nn_index in range(keta-1,-2,-1):
      if nn_index==-1:
        break
      if str_num[nn_index]!="9":
        break
    num_chr=0
    bk=str(chk_num+1)
    if nn_index==-1:
      bk=""
      for j in range(keta):
        if j==0:
          num_chr=10
        else:
          num_chr=0
        bk+=str(num_chr)
    elif int(str_num[keta-2])+1==int(str_num[keta-1]) or (str_num[keta-2]=="9" and str_num[keta-1]=="9"):
      for asc_index in range(nn_index-1,-2,-1):
        if asc_index==-1:
          break
        if int(str_num[asc_index])+1!=int(str_num[asc_index+1]):
          break
      bk=""
      for j in range(keta):
        if j<asc_index+1:
          num_chr=int(str_num[j])
        elif j==asc_index+1:
          num_chr=int(str_num[j])+1
        else:
          num_chr=num_chr-1 if num_chr-1>0 else 0
        bk+=str(num_chr)
    chk_num=int(bk)-1
print(str_num)

Solution (Python):

from collections import deque

K = int(input())

Q = deque()

for i in range(9):
    Q.append(i+1)
cnt = 0

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

    cnt += 1

print(q)

Solution (Python):
k=int(input())
b=[0]
c=1
c=1
for i in range(k):
    if  b[len(b)-c]+1-b[len(b)-c-1]<=1 and b[len(b)-c]!=9:
        b[len(b)-c]+=1
    elif b==[9]*len(b):
        b=[1]+[0]*len(b)
    else:
        while b[len(b)-c]+1-b[len(b)-c-1]>1 or b[len(b)-c]+1==10:
            c+=1
        b[len(b)-c]+=1
        
        for i in range(c-1):
            if b[len(b)-(c-i)]-1<0:
                b[len(b)-(c-i)+1]=0
            else:
                b[len(b)-(c-i)+1]=b[len(b)-(c-i)]-1
        c=1
    
print(int(''.join(map(str,b))))

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

if K<10: print(K); exit()

q=deque(list(range(1,10)))
anslist=list(range(1,10))
cnt=9

while cnt<=K:
    a=q.popleft()
    
    
    a_1=int(str(a)[-1])

    
    if a_1!=0:
        i=a*10+(a_1-1)
        q.append(i)
        anslist.append(i)
        cnt+=1

    
    i=a*10+a_1
    q.append(i)
    anslist.append(i)
    cnt+=1

    
    if a_1!=9:
        i=a*10+(a_1+1)
        q.append(i)
        anslist.append(i)
        cnt+=1

print(anslist[K-1])

Solution (Python):




def rec(d, val, all):
    
    all.append(val)
    
    if d == 10:
        return
    
    for i in range(-1, 2):
        add = val%10 + i
        if 0 <= add <= 9:
            rec(d+1, val*10+add, all)


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


for i in range(1, 10):
    rec(1, i, all)

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

Solution (Python):
from collections import deque

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

    q = deque()

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

    count = 0

    a = 0

    while(count < k):

        a = q.popleft()

        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)

        count += 1

    print(a)

main()

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

Solution (Python):



K = int(input())

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

cnt = 9

ind = [i for i in range(1,10)]
tmp = ind

while cnt <= K:
  l = []
  for i in range(len(tmp)):
    if tmp[i] % 10 == 0:
      
      l.append(tmp[i] * 10 + tmp[i] % 10)
      l.append(tmp[i] * 10 + tmp[i] % 10 + 1)
      cnt += 2
    elif tmp[i] % 10 == 9:
      
      l.append(tmp[i] * 10 + tmp[i] % 10 - 1)
      l.append(tmp[i] * 10 + tmp[i] % 10)
      cnt += 2
    else:
      
      l.append(tmp[i] * 10 + tmp[i] % 10 - 1)
      l.append(tmp[i] * 10 + tmp[i] % 10)
      l.append(tmp[i] * 10 + tmp[i] % 10 + 1)
      cnt += 3
  tmp = l
  ind += l


print(ind[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):
    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):
def is_lunlun(s):
    for i in range(len(s) - 1):
        if abs(int(s[i]) - int(s[i+1])) > 1:
            return (i)
    return -1

def minimize(s, j):
    init = int(s[j])
    for i in range(j + 1, len(s)):
        if init == 0:
            s[i] = str(0)
        else:
            init -= 1
            s[i] = str(init)
    return s

k = int(input())
if k <= 10:
    print(k)
else:
    counter = 10
    i = 10
    while counter < k:
        i += 1
        s = list(str(i))
        lunlun_dig = is_lunlun(s)
        while lunlun_dig != -1:
            if int(s[lunlun_dig]) < int(s[lunlun_dig + 1]):
                s[lunlun_dig] = str(int(s[lunlun_dig]) + 1)
            s = minimize(s, lunlun_dig)
            lunlun_dig = is_lunlun(s)
        i = int("".join(s))
        counter += 1
    print(i)

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

while True:
    
    if k<=len(a):
        print(a[k-1])
        break
    """
    1桁に成果がなければ、kから１桁のlen(るんるん数リスト)を引いて、
    ２桁のリストを作ります。作り方は、元のるんるんリストのそれぞれの数を１０倍して、
    その１０の位と同じか隣接する値を加えたものをappend.
    以下同様
    """
    k-=len(a)
    old=[]
    old, a=a, old
    for x in old:
        for i in range(-1,2):
            d=x%10+i
            if d<0 or d>9:
                continue
            new_x=x*10+d
            a.append(new_x)

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

while(1):
    if(k <= len(a)):
        print(a[k-1])
        break
    k -= len(a)
    old = []
    old, a = a, old
    for x in old:
        for i in range(-1, 2):
            d = x % 10+ i
            if(d < 0 or d > 9):
                continue
            nx = x*10 + d
            a.append(nx)

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


res = 0

def runrun(keta, flag, before, res) :
  if(flag) :
    if(keta == 0) :
      res += 1
      if(res == K) :
        print("".join(map(str, before)))
        exit()
      return res
    for i in range(before[-1]-1, before[-1]+2) :
      if((i < 0) or (i > 9)) :
        continue
      else :
        res = runrun(keta-1, flag, before+[i], res)
    return res
  else :
    if(keta <= 0) :
      return res

    res = runrun(keta-1, flag, before, res)
    for i in range(1, 10) :
      res = runrun(keta-1, True, before+[i], res)
    return res
      
      
runrun(10, False, [], res)

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

Solution (Python):
K=int(input())
S=[1]
while 1:
    
    flag=0
    idxflag=0
    for i in range(len(S)-1):
        if not S[i] in [S[i+1]+1,S[i+1],S[i+1]-1]:
            flag=1
            break
    if flag:
        S[i]+=1

        for m in range(i+1,len(S)):
            S[m]=max(S[m-1]-1,0)
    else:
        K-=1
        if K==0:
            break
        S[-1]+=1


    for i in range(1,len(S))[::-1]:
        if S[i]==10:
            idx=i
            idxflag=1
            S[i]=0
            S[i-1]+=1
            
    if idxflag:
        for i in range(idx,len(S)):
            S[i]=max(S[i-1]-1,0)


    if S[0]==10:
        S=[0 for i in range(len(S)+1)]
        S[0]=1
print(int("".join([str(i) for i in S])))

Solution (Python):
import collections
m = int(input())
n = 1000000000
ans = []
listnum = [
            [0, 1],
            [0, 1, 2],
            [1, 2, 3],
            [2, 3, 4],
            [3, 4, 5],
            [4, 5, 6],
            [5, 6, 7],
            [6, 7, 8],
            [7, 8, 9],
            [8, 9]
           ]
def dfs(s):
    if len(str(n)) + 1 > len(s):
        ans.append(int(s))
        lastnum = str(s)[-1]
        for i in listnum[int(lastnum)]:
            dfs(s + str(i))
for i in range(1, 10):
    dfs(str(i))
ans = sorted(ans)
print(ans[m - 1])

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

    que=deque(["0"])
    res=[]
    count=0
    while count<K:
        n=que.popleft()
        if n=="0":
            for i in range(1,10):
                i=str(i)
                que.append(i)
                res.append(i)
                count+=1
        else:
            if n[-1]=="0":
                nex=["0","1"]
            elif n[-1]=="9":
                nex=["8","9"]
            else:
                m=int(n[-1])
                nex=[str(m-1),n[-1],str(m+1)]
            for l in nex:
                k=n+l
                que.append(k)
                res.append(k)
                count+=1

    print(res[K-1])
if __name__=="__main__":
    main()

Solution (Python):
ll = set()

def search(s):
    ll.add(int(s))
    if len(s) == 10:
        return
    
    if int(s[-1]) == 0:
        search(s+"1")
    elif int(s[-1]) == 9:
        search(s+"8")
    else:
        search(s+str(int(s[-1])+1))
        search(s+str(int(s[-1])-1))
    search(s+s[-1])
    
for i in range(1, 10):
    search(str(i))

ll = list(sorted(ll))

print(ll[int(input())-1])

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

if K < 10:
  queue = range(1,K+1)
  count = K
else:
  count = 9
  queue = [1,2,3,4,5,6,7,8,9]

while count != K:
  for x in queue:
    if x%10 != 0:
      queue.append(10*x + (x%10) - 1)
      count += 1
      if count == K:
        break

    queue.append(10*x + (x%10))
    count += 1
    if count == K:
      break

    if x%10 != 9:
      queue.append(10*x + (x%10) + 1)
      count += 1
      if count == K:
        break

print(queue[-1])

Solution (Python):
from collections import deque


def solve():
    N = int(input())
    q = deque([1,2,3,4,5,6,7,8,9])
    cnt = 0
    l = []

    while cnt<N:
        p = q.popleft()
        l.append(p)
        cnt += 1
        for i in range(max((p%10)-1,0), min((p%10)+1, 9)+1):
            q.append(10*p+i)

    print(l[N-1])


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque


def solve():
    N = int(input())
    q = deque([1,2,3,4,5,6,7,8,9])
    cnt = 0
    l = []
    used = set()

    while cnt<N:
        p = q.popleft()
        if p in used:continue
        used.add(p)
        l.append(p)
        cnt += 1
        for i in range(max((p%10)-1,0), min((p%10)+1, 9)+1):
            q.append(10*p+i)

    print(l[N-1])


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque

q = deque([1,2,3,4,5,6,7,8,9])
cnt = 0
l = []
used = set()

while cnt<100000:
    p = q.popleft()
    if p in used:continue
    used.add(p)
    l.append(p)
    cnt += 1
    for i in range(max((p%10)-1,0), min((p%10)+1, 9)+1):
        q.append(10*p+i)

N = int(input())
print(l[N-1])

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

Solution (Python):
from collections import deque

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

n = int(input())

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

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

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

K=II()
for i in range(K-1):
    v = deq.popleft()
    last = v % 10
    if last == 0:
        deq.append(10*v)
        deq.append(10*v + 1)
    elif last == 9:
        deq.append(10*v + 8)
        deq.append(10*v + 9)
    else:
        deq.append(10*v + last-1)
        deq.append(10*v + last)
        deq.append(10*v + last+1)

print(deq.popleft())

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

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

K=II()
for i in range(K-1):
    v = deq.popleft()
    last = int(v[-1])
    if last == 0:
        deq.append(v + "0")
        deq.append(v + "1")
    elif last == 9:
        deq.append(v + "8")
        deq.append(v + "9")
    else:
        deq.append("{}{}".format(v, last-1))
        deq.append("{}{}".format(v, last))
        deq.append("{}{}".format(v, last+1))

print(deq.popleft())

Solution (Python):
from collections import deque

K = int(input())
count = 0

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

while True:
    num = deq.popleft()
    count += 1
    if num % 10 != 0:
        deq.append((10 * num) + (num % 10) - 1)
    deq.append((10 * num) + (num % 10))
    if num % 10 != 9:
        deq.append((10 * num) + (num % 10) + 1)
    
    if count == K:
        ans = num
        break

print(ans)

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

lunlun = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
for i in range(11):
    last = lunlun[-1]
    add = []
    for x in last:
        c = x % 10
        add.append(x*10+c)
        if c != 0:
            add.append(x*10+c-1)
        if c != 9:
            add.append(x*10+c+1)
    lunlun.append(add)

all = []
for i in range(11):
    for x in lunlun[i]:
        all.append(x)
all.sort()
print(all[k-1])

Solution (Python):
k = int(input())
n = list(map(str, range(10)))

i = 0
while len(n) < k+1:
    i += 1
    
    for j in range(-1, 2):
        
        m = n[i][-1]
        if j == -1 and m == "0":
            continue
        if j == 1 and m == "9":
            break
        p = n[i] + n[int(m)+j]
        n.append(p)


print(n[k])

Solution (Python):
k=int(input())
l=[1,2,3,4,5,6,7,8,9]
n=1 
s=0; e=8 
p=9
q=9
if k<10:
    print(l[k-1])
else:
    while k>p:
        for m in range(s,e+1):
            I=str(l[m])[n-1] 
            if I=="0":
                l.append(str(l[m])+"0")
                p+=1
                l.append(str(l[m])+"1")
                p+=1
            elif I != "9":
                l.append(str(l[m])+str(int(I)-1))
                p+=1
                l.append(str(l[m])+str(int(I)))
                p+=1
                l.append(str(l[m])+str(int(I)+1))
                p+=1
            else:
                l.append(str(l[m])+"8")
                p+=1
                l.append(str(l[m])+"9")
                p+=1
        q=p-q
        s=e+1
        e=s+q-1
        q=p
        n+=1

    print(l[k-1])

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

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

for i in range (0, 100000):
	if V[i]%10 == 0:
		V.append(10*V[i]+0)
		V.append(10*V[i]+1)
	elif V[i]%10 == 9:
		V.append(10*V[i]+8)
		V.append(10*V[i]+9)
	else:
		V.append(10*V[i]+V[i]%10-1)
		V.append(10*V[i]+V[i]%10)
		V.append(10*V[i]+V[i]%10+1)

print(V[K-1])

Solution (Python):
from queue import Queue

K = int(input())

q = Queue()

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

for _ in range(K):
    ans = q.get()
    if ans % 10 == 0:
        q.put(ans*10)
        q.put(ans*10+1)
    elif ans % 10 == 9:
        q.put(ans*10+8)
        q.put(ans*10+9)
    else:
        d = ans % 10
        q.put(ans*10+d-1)
        q.put(ans*10+d)
        q.put(ans*10+d+1)

print(ans)

Solution (Python):
from sys import stdin
from collections import deque

K = int(stdin.readline())

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

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

print(deque.popleft())

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

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

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

lun = [[0] * 12 for _ in range(10)]
for i in range(1, 11):
    lun[0][i] = 1
for i in range(1, 10):
    for j in range(1, 11):
        lun[i][j] = lun[i - 1][j - 1] + lun[i - 1][j] + lun[i - 1][j + 1]

res = []
i = 0
start = 1
while k > 0 and i < 10:
    for j in range(start, 11):
        if not res and j == 1:
            continue
        if k == lun[i][j] == 1:
            res.append(j - 1)
            k = 0
            break
        if k > lun[i][j]:
            k -= lun[i][j]
            continue
        res.append(j - 1)
        start = j - 1
        i -= 1
        break
    else:
        i += 1


print(*res, sep="")

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

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

Solution (Python):
K = int(input())
queue = [1,2,3,4,5,6,7,8,9]
i = 0
flag = 1
while(flag==1):
    if K<len(queue):
        flag = 0
        break
    else:
        x = queue[i]
        if x%10 != 0:
            queue.append(x*10+x%10-1)
        queue.append(10*x+x%10)

        if x%10 != 9:
            queue.append(10*x+x%10+1)

    i+=1

print(queue[K-1])

Solution (Python):
import queue
target = int(input())

q = queue.Queue()

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


for cnt in range(1, target):
  num = q.get()
  mod = int(num) % 10
  
  if mod == 0:
    q.put(num + "0")
    q.put(num + "1")
  elif mod == 9:
    q.put(num + "8")
    q.put(num + "9")
  else:
    q.put(num + str(mod - 1))
    q.put(num + str(mod))
    q.put(num + str(mod + 1))

print(q.get())

Solution (Python):


import sys

sys.setrecursionlimit(10 ** 6)

input_line = input()
inputs = input_line.split(' ')
K, = [int(s) for s in inputs]



if K<=9:
    print(K)
else:
    pre = list(range(1, 10))
    sp = [0]
    digit = 0
    num = 9
    while True:
        lunluns = []

        for pp in sp:
            num += 1
            lunlun = (10**(digit+1))+pp
            if K==num:
                print(lunlun)
                quit()
            lunluns.append(lunlun)

        for i in range(1, 10):

            for p in pre:
                s = p // (10**digit)
                if i==1 and s==1:
                    sp.append(p)
                if abs(i-s)<=1:
                    num += 1
                    lunlun = i*(10**(digit+1))+p
                    if K==num:
                        print(lunlun)
                        quit()
                    lunluns.append(lunlun)
        pre = lunluns
        digit += 1

Solution (Python):
K=int(input())
lunlun=[1,2,3,4,5,6,7,8,9]
flag=1
i=0
if K<10:
  pass
else:
  while flag==1 :
    if len(lunlun)>=K:
        flag=0
        break
    else:
      x=lunlun[i]
      if x % 10 != 0:
        lunlun.append(x*10+x%10-1)
    
      lunlun.append(x*10+x%10)
    
      if x % 10 != 9:
        lunlun.append(x*10+x%10+1) 
	
    i+=1
        
print(lunlun[K-1])

Solution (Python):
from collections import deque

K = int(input())

dq = deque([])

cnt = 0
for i in range(1, 10):
    dq.append(str(i))


while cnt < K:
    val = dq.popleft()
    cnt += 1

    if cnt == K:
        print(val)
        exit()

    if val[-1] == '0':
        dq.append(val + '0')
        dq.append(val + '1')
    elif val[-1] == '9':
        dq.append(val + '8')
        dq.append(val + '9')
    else:
        prev = int(val[-1]) - 1
        nex = int(val[-1]) + 1

        dq.append(val + str(prev))
        dq.append(val + val[-1])
        dq.append(val + str(nex))

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

Solution (Python):
K=int(input())
queue=[1,2,3,4,5,6,7,8,9]
i=0
flag=1
while(flag==1):
  if K<=len(queue):
    flag=0
    break
  else:

    x=queue[i]
    if x % 10!=0:
      queue.append(x*10+(x%10)-1)
    queue.append(10*x+(x%10))

    if x%10!=9:
      queue.append(10*x+(x%10)+1)
    
  
  i+=1



print(queue[K-1])

Solution (Python):
from collections import deque

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

K = int(input())

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

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

from collections import deque

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

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

print(d[0])