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())
l = ['1','2','3','4','5','6','7','8','9']
lf = ['1','2','3','4','5','6','7','8','9']
sum = 9
while sum < k:
    lff = []
    for i in lf:
        if i[-1] == '0':
            lff.append(i+'0')
            lff.append(i+'1')
        elif i[-1] == '9':
            lff.append(i+'8')
            lff.append(i+'9')
        else:
            lff.append(i+str(int(i[-1])-1))
            lff.append(i+str(int(i[-1])))
            lff.append(i+str(int(i[-1])+1))
    lf = lff
    l += lff
    sum += len(lff)
print(int(l[k-1]))

Solution (Python):
from collections import deque

k = int(input())

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

num = 0

while True:
    x = q.popleft()
    num += 1
    if num == k:
        break
    y = x % 10
    if y != 0:
        q.append(10 * x + y - 1)
    q.append(10 * x + y)
    if y != 9:
        q.append(10 * x + y + 1)

print(x)

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

def suc(s):
    return s + str(int(s[-1]) + 1)

def prev(s):
    return s + str(int(s[-1]) - 1)

def f(k):
    pq = list(range(1, 10))
    heapq.heapify(pq)
    i = 0
    while i < k:
        a = heapq.heappop(pq)
        yield a

        i += 1
        a_ = str(a)
        if a_[-1] < "9":
            down = int(suc(a_))
            heapq.heappush(pq, down)

        if a_[-1] > "0":
            up = int(prev(a_))
            heapq.heappush(pq, up)

        flat = int(a_ + a_[-1])
        heapq.heappush(pq, flat)

def main():
    k = int(input())
    ans = list(f(k))
    print(ans[-1])




main()

Solution (Python):

import sys

sys.setrecursionlimit(10**9)

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

Solution (Python):
K = int(input())
l = [0]*(10**5+10)
l[1:10] = list(range(1,10))
def res(now):
    if int(now[-1])==0:
      for a in range(0,2):
        ret=str(now)+str(a)
        yield ret
    elif int(now[-1])==9:
      for a in range(8,10):
        ret=str(now)+str(a)
        yield ret
    else:
      for a in range(int(now[-1])-1,int(now[-1])+2):
        ret=str(now)+str(a)
        yield ret
        
start = 1
end = 9
while True:
  tmp = []
  for a in l[start:end+1]:
    tmp += list(res(str(a)))
  b = len(tmp)
  start = end+1
  end = start+b-1
  if end<=10**5+5:
    l[start:end+1]=tmp
  else:
    l[start:10**5+5]=tmp[:10**5+5-start]
    break
print(int(l[K]))

Solution (Python):
from collections import deque

K = int(input())

que = deque(list(range(1,10)))

for _ in range(K-1):
    x = que.popleft()
    p = x % 10
    if p == 0:
        que.extend([10*x, 10*x+1])
    elif p == 9:
        que.extend([10*x+8, 10*x+9])
    else:
        que.extend([10*x + p - 1, 10*x + p, 10*x + p + 1])
print(que.popleft())

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

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

    S = [str(i) for i in range(1, 10)]
    Sa = [str(i) for i in range(1, 10)]
    while True:
        Ad = []
        for sa in Sa:
            if sa[-1] == '0':
                Ad.append(sa + '0')
                Ad.append(sa + '1')
            elif sa[-1] == '9':
                Ad.append(sa + '8')
                Ad.append(sa + '9')
            else:
                for i in [-1, 0, 1]:
                    Ad.append(sa + str(int(sa[-1]) + i))

        Sa = Ad
        S.extend(Ad)
        if k <= len(S):
            print(S[k - 1])
            exit()

if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque
K = int(input())
queue = [str(i) for i in range(1, 10)]

queue = deque(queue)
L = []
cnt = 0
while cnt < K:
    v = queue.popleft()
    
    L.append(int(v))
    if v[-1] == "0":
        
        queue.append(v + v[-1])
        queue.append(v+"1")
        
    elif v[-1] == "9":
        
        queue.append(v + "8")
        queue.append(v + v[-1])
    else:
        
        t = int(v[-1])
        queue.append(v+str(t-1))
        queue.append(v + v[-1])
        queue.append(v+str(t+1))
    cnt += 1
print(v)

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

dp = [[0]*10 for _ in range(17)]
for i in range(10):
    dp[0][i] = 1

for keta in range(1, 17):
    for i in range(10):
        if 1 <= i and i <= 8:
            dp[keta][i] += dp[keta-1][i-1]+dp[keta-1][i]+dp[keta-1][i+1]
        if i == 0:
            dp[keta][i] += dp[keta-1][0]+dp[keta-1][1]
        if i == 9:
            dp[keta][i] += dp[keta-1][9]+dp[keta-1][8]
SUM = 0
for keta in range(17):
    SUM += sum(dp[keta][1:])
    if SUM >= K:
        break
SUM = 0
for i in range(keta):
    SUM += sum(dp[i][1:])

r = K-SUM
tmp_r = 0
for i in range(1, 10):
    tmp_r += dp[keta][i]
    if tmp_r >= r:
        tmp_r -= dp[keta][i]
        r -= tmp_r
        break
keta += 1
if keta == 1:
    print(i)
else:
    l=[i]
    rr = 0
    for k in range(keta-1, 0, -1):
        q = deque()
        if i == 0:
            q.append(0)
            q.append(1)
        elif i == 9:
            q.append(8)
            q.append(9)
        else:
            q.append(i-1)
            q.append(i)
            q.append(i+1)
        while q:
            num = q.popleft()
            rr += dp[k-1][num]
            if rr >= r:
                rr -= dp[k-1][num]
                l.append(num)
                i = num
                break
    keta = len(l)
    ans = 0
    for i in range(keta):
        ans += l[keta-i-1]*10**i
    print(ans)

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

Solution (Python):
n = int(input())
f = list()
def dfs(k, a):
  if not k:
    f.append(a)
    return
  if not a:
    for i in range(10):
      dfs(k-1, i)
    return 
  t = a % 10
  dfs(k-1, a*10 + t)
  if t: dfs(k-1, a*10 + t - 1)
  if t < 9: dfs(k-1, a*10 + t + 1)
  return

dfs(11, 0)
f.sort()
print(f[n])

Solution (Python):
def countup(nums):
  flag = [False for _ in range(len(nums))]
  
  nums[0] += 1
  
  for i in range(len(nums)-1):
    if nums[i] == 10 or nums[i] - nums[i+1] >= 2:
      flag[i] = True
      nums[i+1] += 1
  
  if nums[-1] == 10:
    nums[-1] = 0
    nums.append(1)
    
  for i in range(len(nums)-2, -1, -1):
    if flag[i]:
      if nums[i+1] == 0:
        nums[i] = 0
      else:
        nums[i] = nums[i+1] - 1
  return nums

N = int(input())

nums = [0]

for i in range(N):
  nums = countup(nums)
  
for i in range(len(nums)-1, -1, -1):
  print(nums[i], end='')
  
print('')

Solution (Python):

import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    K = II()
    if K <= 10:
            print(K)
            return
    x = [0]
    x = [0,1]
    for _ in range(K-10):
        
        c = 1
        for j in range(len(x)):
            if c == 0:
                break
            x[j] += 1
            c = x[j] // 10
            x[j] %= 10
        if c == 1:
            x.append(1)


        for i in range(1,len(x)):
            d = x[i] - x[i-1]
            if d < -1:
                c = 1
                for j in range(i,len(x)):
                    if c == 0:
                        break
                    x[j] += 1
                    c = x[j] // 10
                    x[j] %= 10
                if c == 1:
                    x.append(1)
                for j in range(i,0,-1):
                    x[j-1] = max(x[j] - 1,0)
            elif d > 1:
                x[i-1] = x[i] - 1
        for i in range(len(x)-1,0,-1):
            if x[i] - x[i-1] > 1:
                x[i-1] = x[i] -1

    
    ans = 0
    
    for i in x[::-1]:
        ans *= 10
        ans += i
    print(ans)
    

    
    

if __name__ == '__main__':

    main()

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

count = 0
x = 0

runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
def dfs(current, next, max_len):
    if next < 0 or next > 9:
        return
    current.append(str(next))
    if len(current) == max_len:
        tmp = ''.join(current)
        runrun.append(int(tmp))
        return
    dfs(copy.deepcopy(current), next - 1, max_len)
    dfs(copy.deepcopy(current), next, max_len)
    dfs(copy.deepcopy(current), next + 1, max_len)

for i in range(1, 10):
    dfs([], i, 2)
for i in range(1, 10):
    dfs([], i, 3)
for i in range(1, 10):
    dfs([], i, 4)
for i in range(1, 10):
    dfs([], i, 5)
for i in range(1, 10):
    dfs([], i, 6)
for i in range(1, 10):
    dfs([], i, 7)
for i in range(1, 10):
    dfs([], i, 8)
for i in range(1, 10):
    dfs([], i, 9)
for i in range(1, 5):
    dfs([], i, 10)

print(runrun[k - 1])

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

str_runrun = "1"

for i in range(K-1):
    str_next_runrun = str_runrun
    
    for j in range(1, len(str_runrun)+1):
        if j < len(str_runrun):
            if abs(int(str_runrun[-(j+1)]) - (int(str_runrun[-j])+1)%10) <= 1:
                str_next_runrun = str_runrun[:-j] + str(int(str_runrun[-j])+1) + "x"*max((j-1),0)
                break
            else:
                pass
        elif str_runrun[0] != "9":
            str_next_runrun = str(int(str_runrun[0])+1) + "x"*(len(str_runrun)-1)
        else:
            str_next_runrun = "1" + "x"*len(str_runrun)
    
    str_next_runrun_no_x_list = []
    for l in str_next_runrun:
        if l != "x":
            str_next_runrun_no_x_list.append(l)
        else:
            str_next_runrun_no_x_list.append(str(max(int(str_next_runrun_no_x_list[-1])-1, 0)))
    str_runrun = "".join(str_next_runrun_no_x_list)

print(str_runrun)

Solution (Python):
n = int(input())
t = [1,2,3,4,5,6,7,8,9]
if n < 10:
    print(n)
else:
  i = 0
  while len(t) < n:
    a = t[i]
    b = a % 10
    if b == 0:
        c = a*10
        t.append(c)
        c += 1
        t.append(c)
    elif b == 9:
        c = a*10+8
        t.append(c)
        c += 1
        t.append(c)
    else:
        c = a*10 + b -1
        t.append(c)
        c += 1
        t.append(c)
        c += 1
        t.append(c)
    i += 1
  print(t[n-1])

Solution (Python):


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

     runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     count = 0
     while(len(runrun) < k):
          target = runrun[count]
          num = target % 10
          if num != 0:
               runrun.append(target * 10 + num - 1)
          runrun.append(target * 10 + num)
          if num != 9:
               runrun.append(target * 10 + num + 1)

          count += 1
          

     print(runrun[k-1])

if __name__ == "__main__":
    main()

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

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


K = I()

ans = []
def fn(n):
    ns = str(n)
    tail = int(ns[-1])
    if tail > 0:
        yield int(ns + str(tail - 1))
    yield int(ns + ns[-1])
    if tail < 9:
        yield int(ns + str(tail + 1))


for i1 in range(1, 10):
    ans.append(i1)
    for i2 in fn(i1):
        ans.append(i2)
        for i3 in fn(i2):
            ans.append(i3)
            for i4 in fn(i3):
                ans.append(i4)
                for i5 in fn(i4):
                    ans.append(i5)
                    for i6 in fn(i5):
                        ans.append(i6)
                        for i7 in fn(i6):
                            ans.append(i7)
                            for i8 in fn(i7):
                                ans.append(i8)
                                for i9 in fn(i8):
                                    ans.append(i9)
                                    for i10 in fn(i9):
                                        ans.append(i10)


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

Solution (Python):
k = int(input())
from collections import deque
q = deque()
a = list(map(str, list(range(1, 10))))
ans = a + []
illist = []
for i in range(10):
    if i == 0:
        illist.append(["0","1"])
    elif i == 9:
        illist.append(["8","9"])
    else:
        illist.append([str(i-1),str(i),str(i+1)])
for i in range(1,10):
    q.append(str(i))

node = "0"
while node != "323456667":
    node = q.popleft()
    for j in illist[int(node[-1])]:
        nodej = node+j
        q.append(nodej)
        a.append(nodej)

print(a[k - 1])

Solution (Python):
K = int(input())
A = [1,2,3,4,5,6,7,8,9]
for i in range(len(A)):
    if A[i] != 9:
        for j in range(-1,2):
            a = int(str(A[i]) + str(A[i]+j))
            A.append(a)
    else:
        A.append(98)
        A.append(99)
A.append(100)
A.append(101)
L1 = len(A.copy())
for i in range(10,L1):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L2 = len(A.copy())
for i in range(L1,L2):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B%10) + j))
            A.append(a)
L3 = len(A.copy())
for i in range(L2,L3):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L4 = len(A.copy())
for i in range(L3,L4):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L5 = len(A.copy())
for i in range(L4,L5):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L6 = len(A.copy())
for i in range(L5,L6):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L7 = len(A.copy())
for i in range(L6,L7):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L8 = len(A.copy())
for i in range(L7,L8):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
print(A[K-1])

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

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



K = int(sys.stdin.buffer.readline())
que = deque(list(map(str, range(1, 10))))
for _ in range(K - 1):
    
    s = que.popleft()
    d = int(s[-1])
    if d > 0:
        que.append(s + str(d - 1))
    que.append(s + str(d))
    if d < 9:
        que.append(s + str(d + 1))
print(int(que[0]))

Solution (Python):

import sys
from collections import deque
from copy import copy

def get_digits(i):
    last_digit = int(str(i)[-1])
    if last_digit in list(range(1,9)):
        return [last_digit-1, last_digit, last_digit+1]
    elif last_digit == 0:
        return [last_digit, last_digit+1]
    elif last_digit == 9:
        return [last_digit-1, last_digit]

def solve(K: int):
    deq1 = deque()
    deq2 = deque()
    lunlun_list = []

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

    while  len(lunlun_list) <= 10 ** 5:
        num = deq1.popleft()
        digits = get_digits(num)
        for new_digit in digits:
            new_num = int(str(num)+str(new_digit))
            lunlun_list.append(new_num)
            deq2.append(new_num)

        if len(deq1) == 0:
            deq1 = copy(deq2)
            deq2 = deque()

    print(lunlun_list[K-1])



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  
    solve(K)

if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect

k = int(input())
A = list(range(10))

if k <= 9:
    print(A[k])
    exit()


def is_1_keta(i):
    return len(str(i)) == 1


kouho = list(map(str, range(1, 10)))
kouho2 = list(map(str, range(1, 10)))
while True:
    ll = []
    for i in kouho:
        su = list(filter(is_1_keta, [int(i[-1]) - 1, int(i[-1]), int(i[-1]) + 1]))
        l = [str(i) + str(x) for x in su]
        A.extend(l)
        ll.extend(l)
    kouho = ll
    kouho2.extend(ll)
    if len(kouho2) > k:
        break

print(sorted(list(map(int, kouho2)))[k - 1])

Solution (Python):
import sys

def lunlun(n0, n,m):
    ans = list()

    if (n<n0 and m-1>=0) :    
        ans.append(m-1)
    ans.append(m)
    if n<n0 and m+1<=9:
        ans.append(m+1)

    if (n==1):
        return ans
    else:
        ans2=list()
        for i in ans:
            ans1=lunlun(n0, n-1, i)
            for j in ans1:
                ans2.append(str(i)+str(j))
        return ans2

K=int(input())

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

for j in range(2,11):
    for i in range(1,10):
        add=lunlun(j, j, i)
        ans=ans+add


print(ans[K-1])

Solution (Python):

from collections import deque
K = int(input())
D = [str(i) for i in range(1, 10)]
D = deque(D)
cnt = 0
while cnt < K:
    v = D.popleft()
    if v[-1] == "0":
        D.append(v + "0")
        D.append(v + "1")
    elif v[-1] == "9":
        D.append(v+"8")
        D.append(v+"9")
    else:
        D.append(v + str(int(v[-1]) - 1))
        D.append(v + v[-1])
        D.append(v + str(int(v[-1]) + 1))
    cnt += 1
print(v)

Solution (Python):
K=int(input())
x=[[0] for _ in range(11)]
y=[ 0 for _ in range(11)]

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

for i in range(2,11):
  x[i].pop()
  for num in x[i-1]:
    last = num%10
    if last==0:
      x[i].append(10*num)
      x[i].append(10*num+1)
      y[i] +=2
    elif last==9:
      x[i].append(10*num+8)
      x[i].append(10*num+9)
      y[i] +=2
    else:
      x[i].append(10*num+(last-1))
      x[i].append(10*num+last)
      x[i].append(10*num+(last+1))
      y[i] +=3
      



z=[0,y[1]]
for i in range(2,11):
 z.append(z[-1]+y[i])


keta=0
for i,num in enumerate(z):
  if num<=K:
    keta=i+1

s= K-z[keta-1]

print(x[keta][s-1])

Solution (Python):
K = int(input())
lis = []

lis = []
def search(s):
  lis.append(s)
  
  if int(s) > 3234566667:
    return
  
  it = int(s[-1])
  if it == 0:
    search(s + '0')
    search(s + '1')
  elif it == 9:
    search(s + '8')
    search(s + '9')
  else:
    search(s + str(it - 1))
    search(s + str(it))
    search(s + str(it + 1))
  

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

x = list(map(int, lis))
x.sort()
print(x[K-1])

Solution (Python):


import sys
import math

debug = False

def log(text):
    if debug:
        print(text)


def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        
        
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
    
    k = int(lines[0])

    return (k, )


def solve(k):

    nums = [str(e) for e in range(1, 10)]

    def find(found):
        new_found = []
        for f in found:
            last_num = int(f[-1])

            if last_num == 0:
                new_found.append(f + str(last_num ))
                new_found.append(f + str(last_num + 1))
            elif 1 <= last_num and last_num <= 8:
                new_found.append(f + str(last_num - 1))
                new_found.append(f + str(last_num ))
                new_found.append(f + str(last_num + 1))
            elif last_num == 9:
                new_found.append(f + str(last_num - 1))
                new_found.append(f + str(last_num ))
        
        
        cnt = len(found) + len(new_found)
        if cnt < k:
            total_found = found + find(new_found)
        else:
            total_found = found + new_found
            
        return total_found

    total_found = find(nums)
    total_found_as_int = [int(e) for e in total_found]
    total_found_as_int.sort()

    result = total_found_as_int[k-1]
    
    return result

def main():
    
    new_found = solve(*parse_input())
    if isinstance(new_found, list):
        for r in new_found:
            print("%s" % r, sep='')
    else:
        print("%s" % new_found, sep='')

if __name__ == '__main__':

    main()

Solution (Python):
from functools import lru_cache



k = int(input())

@lru_cache(maxsize=None)
def check(num, keta):
  if keta == 1:
    return 1
  l = [i for i in range(10) if abs(num-i) <= 1]
  result = 0
  for i in l:
    result += check(i, keta-1)
  return result

s = ''
n = 10
keta = 2
f = True

if k <= 9:
  print(k)
else:
  checker = 9
  while f:
    for i in range(1, 10):
      pre_checker = checker
      checker += check(i, keta)
      if checker >= k:
        n = i
        s += str(i)
        keta -= 2
        checker = pre_checker
        f = False
        break
    keta += 1
    
  while keta != 0:
    l = [i for i in range(10) if abs(n-i) <= 1 ]
    for i in l:
      pre_checker = checker
      checker += check(i, keta)
      if checker >= k:
        keta -= 1
        s += str(i)
        n = i
        checker = pre_checker
        break
  
print(s)

Solution (Python):
import numpy as np

k=int(input())
a=np.array([i+1 for i in range(9)])
ans=a
temp=a
for i in range(10):
    for j in range(3):
        b=temp*10+temp%10
        c=temp*10+np.minimum(temp%10+1,9)
        d=temp*10+np.maximum(temp%10-1,0)
    ans=np.append(np.append(np.append(ans,b),c),d)
    temp=np.append(np.append(b,c),d)

ans=np.sort(np.unique(ans))
print(ans[k-1])

Solution (Python):
import sys
sys.setrecursionlimit(3000)
k = int(input())

ans = []

def solve(x, l):
    if int(x) > 3234566667:
        return l

    l.append(int(x))
    if x[-1] == '0':
        solve(x + '0', l)
        solve(x + '1', l)
    elif x[-1] == '9':
        solve(x + '9', l)
        solve(x + '8', l)
    else:
        last_digit = int(x[-1])
        for i in range(-1, 2):
            new_digit = last_digit + i
            solve(x + str(new_digit), l)

for i in range(1, 10):
    solve(str(i), ans)
ans.sort()
print(ans[k - 1])

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

numset = {i for i in range(1,10)}
flag = False
count = len(numset)
if count >= k:
    flag = True
arr = [numset]
index = 0

while not flag:
    beforeset = arr[index]
    tmpset = set()
    for i in beforeset:
        tail = str(i)[-1]
        if tail == "0":
            tmpset.add(int(str(i)+str(0)))
            tmpset.add(int(str(i)+str(1)))
        elif tail == "9":
            tmpset.add(int(str(i)+str(8)))
            tmpset.add(int(str(i)+str(9)))
        else:
            tmpset.add(int(str(i)+str(int(tail))))
            tmpset.add(int(str(i)+str(int(tail)+1)))
            tmpset.add(int(str(i)+str(int(tail)-1)))
    count += len(tmpset)
    if count >= k:
        flag = True
    arr.append(tmpset)
    index += 1
    
totalarr = []
for tmpset in arr:
    totalarr += list(tmpset)
    
totalarr.sort()
print(totalarr[k-1])

Solution (Python):
import heapq

K = int(input())
count = 0
ans = []
heapq_list = []



heapq.heapify(heapq_list)
for i in range(1,10):
    heapq.heappush(heapq_list, i)
    count += 1

while heapq_list != []:
    current_number = heapq.heappop(heapq_list)
    ans.append(current_number)
    if count <= 10**5:
        if str(current_number)[len(str(current_number))-1] == "0":
            heapq.heappush(heapq_list, int(str(current_number) + "0"))
            heapq.heappush(heapq_list, int(str(current_number) + "1"))
            count += 2
        elif str(current_number)[len(str(current_number))-1] == "9":
            heapq.heappush(heapq_list, int(str(current_number) + "8"))
            heapq.heappush(heapq_list, int(str(current_number) + "9"))
            count += 2
        else:
            heapq.heappush(heapq_list, int(str(current_number) + str(int(str(current_number)[len(str(current_number))-1])-1)))
            heapq.heappush(heapq_list, int(str(current_number) + str(int(str(current_number)[len(str(current_number))-1]))))
            heapq.heappush(heapq_list, int(str(current_number) + str(int(str(current_number)[len(str(current_number))-1])+1)))
            count += 3
print(ans[K-1])

Solution (Python):
def lun(s):
    ch = 1
    temp = int(s[0])
    for i in s[1: ]:
        i = int(i)
        if abs(i - temp) > 1:
            ch = 0
            break
        temp = i
    return ch
k = int(input())
d = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
l = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
while 1:
    for i in l:
        for j in d:
            
            s = i + str(j)
            if lun(s): l.append(s)
        if len(l) >= 100002: break
    if len(l) >= 100002: break
print(l[k - 1])

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

lunlun = [[] for i in range(11)]

def main():
    n = int(input())
    for i in range(100):
        flag = True
        l = len(str(i))
        if l == 1:
            lunlun[l - 1].append(i)
        else:
            for a in range(1, len(str(i))):
                if abs(int(str(i)[a - 1]) - int(str(i)[a])) >= 2:
                    flag = False
                    break
            if flag:
                lunlun[l - 1].append(i)
            else:
                continue
    for j in range(1, 9):
        for a in lunlun[j]:
            for b in range(10):
                if abs(int(str(a)[-1]) - b) < 2:
                    lunlun[j+1].append(int(str(a)+str(b)))
    lunlun2 = list(itertools.chain.from_iterable(lunlun))
    print(lunlun2[n])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

k = int(input())

dq = deque(range(1, 10))
cnt = 9
li = []
while cnt < 10 ** 5 + 10:
    num = dq.popleft()
    li.append(num)
    lst = num % 10
    if lst == 0:
        dq.append(num * 10)
        dq.append(num * 10 + 1)

    elif lst == 9:
        dq.append(num * 10 + 8)
        dq.append(num * 10 + 9)

    else:
        for i in range(lst - 1, lst + 2):
            dq.append(num * 10 + i)

    cnt += 1

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

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)  
n = int(input())
count = 0
ans = []
if n <= 9:
    print(n)
    exit()


def dfs(pre_str, keta):
    global count, ans
    
    if len(pre_str) == keta:
        count += 1
        ans = pre_str
        if count+9 == n:
            print(ans)
            exit()
        return

    start = int(pre_str[-1])-1
    for i in range(start, start+3):
        if 0 <= i <= 9:
            dfs(pre_str+str(i), keta)
    return


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

Solution (Python):
def lunlundfs(num, digs):
    if digs == 0:
        return [num]
    if num > 0:
        a = lunlundfs(num-1, digs-1)
    else:
        a = []
    b = lunlundfs(num, digs-1)
    if num < 9:
        c = lunlundfs(num+1, digs-1)
    else:
        c = []
    res = []
    for x in a:
        res.append(num*10**digs + x)
    for x in b:
        res.append(num*10**digs + x)
    for x in c:
        res.append(num*10**digs + x)
    return res

def genlunlun(dig):
    lunlunlist = []
    for front in xrange(1,10):
        for d in xrange(dig):
            lunlunlist.extend(lunlundfs(front,d))
    lunlunlist = sorted(lunlunlist)
    return lunlunlist

ll = genlunlun(10)
k = int(raw_input())
print ll[k-1]