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())
count = 9
runrunnumber  = [[]for _ in range(10)]


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


if K > 10:
  for i in range(9):
    for j in runrunnumber[i]:

      if j%10 == 0:
        for p in range(2):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break
      
      if j%10 == 1:
        for p in range(3):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 2:
        for p in range(1,4):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 3:
        for p in range(2,5):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 4:
        for p in range(3,6):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break
      if j%10 == 5:
        for p in range(4,7):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 6:
        for p in range(5,8):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 7:
        for p in range(6,9):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 8:
        for p in range(7,10):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

      if j%10 == 9:
        for p in range(8,10):
          count += 1
          tmp = j*10+p
          runrunnumber[i + 1].append(tmp)
          if count == K:
            print(tmp)
            break

        if count >= K:
          break
    if count >= K:
      break

else:
  print(runrunnumber[0][K-1])

Solution (Python):

from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]


def main():
	k=nextIntList()[0]
	if k<=9:
		print(k)
		sys.exit(0)
	num=[0,1]
	for i in range(10, k):

		if all([n==9 for n in num]):
			num=[0 for d in range(len(num))]
			num.append(1)
			continue
		
		for di in range(len(num)):
			if di==0:
				if num[di]<=num[di+1] and num[di]<9:
					num[di]+=1
					break
			elif di<len(num)-1:
				if num[di]<=num[di+1] and num[di]<9 and num[di]<=num[di-1]:
					num[di]+=1
					break
			else: 
				num[di]+=1
	
		for dii in range(di-1, -1,-1):
			if num[dii+1]==0:
				num[dii]=0
			else:
				num[dii]=num[dii+1]-1 
	
	print("".join(str(n) for n in reversed(num)))

if __name__=="__main__":
	main()

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

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

k = n_in()

h = {
    0: [0,1],
    1: [0,1,2],
    2: [1,2,3],
    3: [2,3,4],
    4: [3,4,5],
    5: [4,5,6],
    6: [5,6,7],
    7: [6,7,8],
    8: [7,8,9],
    9: [8,9],
}


from collections import deque

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

i = 0
current = '0'

while True:
    current = q.popleft()
    i += 1
    for j in h[int(current[-1])]:
        q.append(current + str(j))

    if i == k:
        break

print(current)

Solution (Python):
def gen(l):
    _runs = []
    for r in l:
        r = str(r)
        if r[-1] == '0':
            _runs.append(r+'1')
            _runs.append(r+'0')
        elif r[-1] == '9':
            _runs.append(r+'9')
            _runs.append(r+'8')
        else:
            _runs.append(r+str(int(r[-1])+1))
            _runs.append(r+str(int(r[-1])-1))
            _runs.append(r+r[-1])
    return _runs

def runrun(n):
    runs = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    _runs = gen(runs)
    while len(runs) < n:
        runs.extend(_runs)
        _runs = gen(_runs)
    return sorted(map(lambda i: int(i),runs))

k = int(input())

print(runrun(k)[k-1])

Solution (Python):


K = int(input())
runrun_num = 0

def bfs(s_list):
    global K,runrun_num
    new_s_list = []
    for s in s_list:
        new_int_min = int(s[-1])-1
        if s[-1]=='0':
            new_int_min = 0
        new_int_max = int(s[-1])+1
        if s[-1]=='9':
            new_int_max = 9
        for i in range(new_int_min,new_int_max+1):
            new_s = s+str(i)
            runrun_num+=1
            if K == runrun_num+9:
                print(new_s)
                return None
            else:
                new_s_list.append(new_s)
    bfs(new_s_list)

inp = [str(i) for i in range(1,10)]
if 1<=K and K<=9:
    print(K)
else:
    bfs(inp)

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

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

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

while c<K:
    lb=[]
    for i in la:
        if i[-1]=="0":
            l.append(i+"0")
            l.append(i+"1")
            lb.append(i+"0")
            lb.append(i+"1")
            c+=2
        elif i[-1]=="9":
            l.append(i+"8")
            l.append(i+"9")
            lb.append(i+"8")
            lb.append(i+"9")
            c+=2
        else:
            j=int(i[-1])
            l.append(i+str(j-1))
            l.append(i+str(j))
            l.append(i+str(j+1))
            lb.append(i+str(j-1))
            lb.append(i+str(j))
            lb.append(i+str(j+1))
            c+=3
    la=lb

print(l[K-1])

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



def ln():
    q = deque()
    m = 1
    nd = 1

    while True:
        for i in range(9):
            q.append(([i+1], 1))

            while q:
                n, d = q.popleft()
                if d == nd:
                    if m == K:
                        return n
                    m += 1
                    continue

                if n[-1] == 0:
                    q.append((n+[0], d+1))
                    q.append((n+[1], d+1))
                elif n[-1] == 9:
                    q.append((n+[8], d+1))
                    q.append((n+[9], d+1))
                else:
                    q.append((n+[n[-1]-1], d+1))
                    q.append((n+[n[-1]], d+1))
                    q.append((n+[n[-1]+1], d+1))

        nd+=1

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

Solution (Python):
def rec(N):
    tmp = str(N)
    if tmp[-1] == "0":
        tmp__ = int(tmp[-1])
        tmp___ = int(tmp[-1]) + 1
        yield tmp + str(tmp__)
        yield tmp + str(tmp___)
    elif tmp[-1] == "9":
        tmp_ = int(tmp[-1]) - 1
        tmp__ = int(tmp[-1])
        yield tmp + str(tmp_)
        yield tmp + str(tmp__)
    else:
        tmp_ = int(tmp[-1]) - 1
        tmp__ = int(tmp[-1])
        tmp___ = int(tmp[-1]) + 1
        yield tmp + str(tmp_)
        yield tmp + str(tmp__)
        yield tmp + str(tmp___)
        
K = int(input())
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 0
while(True):
    if len(A) > K:
        break
    for i in rec(A[count]):
        A.append(i)
    count += 1
print(A[K - 1])

Solution (Python):
k = int(input())
if k < 10:
    print(k)
else:
    d = [[str(i)] for i in range(10)]
    n = 9
    while True:
        dd = [None for _ in range(10)]
        dd[0] = ['0' + j for j in d[0]] + ['0' + j for j in d[1]]
        for i in range(1, 9):
            si = str(i)
            dd[i] = [si + j for j in d[i - 1]] + [si + j for j in d[i]] + [si + j for j in d[i + 1]]
            n += len(dd[i])
            if n >= k:
                break
        else:
            i += 1
            dd[9] = ['9' + j for j in d[8]] + ['9' + j for j in d[9]]
            n += len(dd[i])
        if n >= k:
            print(dd[i][k - n - 1])
            break
        d = dd

Solution (Python):
K = int(input())
a = []
dp = [[[] for i in range(10)] for j in range(100)]
for i in range(10):
  dp[0][i] = [i]
  if i != 0:
    a.append(i)
for i in range(1, 10):
  for j in range(10):
    if j != 0:
      for k in dp[i-1][j-1]:
        dp[i][j].append(k + 10 ** i * j)
        a.append(k + 10 ** i * j)
    for k in dp[i-1][j]:
      dp[i][j].append(k + 10 ** i * j)
      if j != 0:
        a.append(k + 10 ** i * j)
    if j != 9:
      for k in dp[i-1][j+1]:
        dp[i][j].append(k + 10 ** i * j)
        if j != 0:
          a.append(k + 10 ** i * j)
print(a[K-1])

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

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

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

Solution (Python):
def add():
    for i in ans[cnt-1]:
        i=str(i)
        last=i[-1]
        last=int(last)
        for j in range(last-1,last+2):
            if j==10 or j==-1:
                continue
            tmp=i
            tmp+=str(j)
            ans[cnt].append(int(tmp))

n=int(input())
ans=[[]for i in range(10)]
cnt=1
for i in range(1,10):
    ans[0].append(i)

for i in range(9):
    add()
    cnt+=1
merged=[]
for i in ans:
    merged+=i
merged=sorted(merged)
print(merged[n-1])

Solution (Python):
def MI():return map(int,input().split())
def LI():return list(MI())
K=int(input())










Ls=[1,2,3,4,5,6,7,8,9]
Ls2=[];Ls3=[];Ls4=[];Ls5=[];Ls6=[];Ls7=[];Ls8=[];Ls9=[];Ls10=[];

for i in Ls:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls2+=(i*10+8),
        Ls2+=(i*10+9),
    elif migihaji=="0":
        Ls2+=(i*10+1),
        Ls2+=(i*10+0),
    else:
        Ls2+=(i*10+int(migihaji)+1),
        Ls2+=(i*10+int(migihaji)+0),
        Ls2+=(i*10+int(migihaji)-1),


for i in Ls2:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls3+=(i*10+8),
        Ls3+=(i*10+9),
    elif migihaji=="0":
        Ls3+=(i*10+1),
        Ls3+=(i*10+0),
    else:
        Ls3+=(i*10+int(migihaji)+1),
        Ls3+=(i*10+int(migihaji)+0),
        Ls3+=(i*10+int(migihaji)-1),



for i in Ls3:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls4+=(i*10+8),
        Ls4+=(i*10+9),
    elif migihaji=="0":
        Ls4+=(i*10+1),
        Ls4+=(i*10+0),
    else:
        Ls4+=(i*10+int(migihaji)+1),
        Ls4+=(i*10+int(migihaji)+0),
        Ls4+=(i*10+int(migihaji)-1),





for i in Ls4:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls5+=(i*10+8),
        Ls5+=(i*10+9),
    elif migihaji=="0":
        Ls5+=(i*10+1),
        Ls5+=(i*10+0),
    else:
        Ls5+=(i*10+int(migihaji)+1),
        Ls5+=(i*10+int(migihaji)+0),
        Ls5+=(i*10+int(migihaji)-1),





for i in Ls5:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls6+=(i*10+8),
        Ls6+=(i*10+9),
    elif migihaji=="0":
        Ls6+=(i*10+1),
        Ls6+=(i*10+0),
    else:
        Ls6+=(i*10+int(migihaji)+1),
        Ls6+=(i*10+int(migihaji)+0),
        Ls6+=(i*10+int(migihaji)-1),





for i in Ls6:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls7+=(i*10+8),
        Ls7+=(i*10+9),
    elif migihaji=="0":
        Ls7+=(i*10+1),
        Ls7+=(i*10+0),
    else:
        Ls7+=(i*10+int(migihaji)+1),
        Ls7+=(i*10+int(migihaji)+0),
        Ls7+=(i*10+int(migihaji)-1),





for i in Ls7:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls8+=(i*10+8),
        Ls8+=(i*10+9),
    elif migihaji=="0":
        Ls8+=(i*10+1),
        Ls8+=(i*10+0),
    else:
        Ls8+=(i*10+int(migihaji)+1),
        Ls8+=(i*10+int(migihaji)+0),
        Ls8+=(i*10+int(migihaji)-1),





for i in Ls8:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls9+=(i*10+8),
        Ls9+=(i*10+9),
    elif migihaji=="0":
        Ls9+=(i*10+1),
        Ls9+=(i*10+0),
    else:
        Ls9+=(i*10+int(migihaji)+1),
        Ls9+=(i*10+int(migihaji)+0),
        Ls9+=(i*10+int(migihaji)-1),





for i in Ls9:
    migihaji=str(i)[-1]
    if migihaji=="9":
        Ls10+=(i*10+8),
        Ls10+=(i*10+9),
    elif migihaji=="0":
        Ls10+=(i*10+1),
        Ls10+=(i*10+0),
    else:
        Ls10+=(i*10+int(migihaji)+1),
        Ls10+=(i*10+int(migihaji)+0),
        Ls10+=(i*10+int(migihaji)-1),




Lunluns=Ls+Ls2+Ls3+Ls4+Ls5+Ls6+Ls7+Ls8+Ls9+Ls10
Lunluns.sort()

print(Lunluns[K-1])

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

lst = []
def dfs(N, n, s):
    if n == N:
        lst.append(s)
        return
    s_ = s*10
    s0 = s%10
    if s0 == 0:
        for i in range(0, 2):
            dfs(N, n+1, s_+i)
    elif s0 == 9:
        for i in range(8, 10):
            dfs(N, n+1, s_+i)
    else:
        for i in range(s0-1, s0+2):
            dfs(N, n+1, s*10+i)

K = int(input())
for i in range(1, 11):
    for j in range(1, 10):
        dfs(i, 1, j)
print(lst[K-1])

Solution (Python):
import sys
k = int(input())
if k < 10:
    print(k)
    sys.exit()

total = 9
lunluns = []
for i in range(10, 100):
    if abs(i // 10 - i % 10) <= 1:
        lunluns.append('{:02d}'.format(i))
if k < 10 + len(lunluns):
    print(lunluns[k - 10])
    sys.exit()
total = 9 + len(lunluns)

while True:
    new = []
    for lunlun in lunluns:
        if lunlun[-1] == '0':
            new.append(lunlun + '0')
            new.append(lunlun + '1')
        elif lunlun[-1] == '9':
            new.append(lunlun + '8')
            new.append(lunlun + '9')
        else:
            new.append(lunlun + str(int(lunlun[-1])-1))
            new.append(lunlun + lunlun[-1])
            new.append(lunlun + str(int(lunlun[-1])+1))

    lunluns = new
    if total + len(lunluns) >= k:
        print(lunluns[k - total - 1])
        break
    total += len(lunluns)

Solution (Python):
k = int(input())
if k <= 9:
    print(k)
    exit()
lunlun = [[1,2,3,4,5,6,7,8,9]]
count = 9
digit = 1
while True:
    lunlun.append([])
    for i in lunlun[digit-1]:
        if i % 10 == 0:
            x = i*10
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
            x = i*10+1
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
        elif i % 10 == 9:
            x = i*10+8
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
            x = i*10+9
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
        else:
            y = i % 10
            x = i*10+y-1
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
            x = i*10+y
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
            x = i*10+y+1
            lunlun[digit].append(x)
            count += 1
            if count == k:
                print(x)
                exit()
    digit += 1

Solution (Python):
from sys import exit
from collections import deque
K = int(input())
if K < 13:
    print(K)
    exit()

que = deque([i for i in range(1, 10)])
counter = 0

while True:
    counter += 1
    if counter == K:
        print(que.popleft())
        exit()
    val = que.popleft()
    before = val % 10
    if before - 1 >= 0:
        que.append(val*10+(before-1))
    que.append(val*10+before)
    if before + 1 <= 9:
        que.append(val*10+(before+1))

Solution (Python):
def plus(x):
    X = str(x)
    p = int(X[len(X)-1])
    if p == 0:
        return(int(X+str(p)), int(X+str(p+1)))
    elif p == 9:
        return(int(X+str(p-1)), int(X+str(p)))
    else:
        return(int(X+str(p-1)), int(X+str(p)), int(X+str(p+1)))
    
A,B,C,D,E,F,G,H,I,J=[],[],[],[],[],[],[],[],[],[]
for i in range(1,10):
    A.append(i)
for i in A:
    B.extend(plus(i))
for i in B:
    C.extend(plus(i))
for i in C:
    D.extend(plus(i))    
for i in D:
    E.extend(plus(i))    
for i in E:
    F.extend(plus(i))
for i in F:
    G.extend(plus(i))
for i in G:
    H.extend(plus(i))
for i in H:
    I.extend(plus(i))
for i in I:
    J.extend(plus(i))

ans = A+B+C+D+E+F+G+H+I+J
print(ans[int(input())-1])

Solution (Python):
k = int(input())
dp = [[0]*10 for i in range(12)]  

for i in range(10):
    dp[1][i] = 1

for i in range(1,10):
    for j in range(10):
        dp[i+1][j] += dp[i][j]
        if j<9:
            dp[i+1][j] += dp[i][j+1]
        if j>0:
            dp[i+1][j] += dp[i][j-1]

ans = 0
for i in range(11):
    for j in range(1,10):
        if k > dp[i][j]:
            k -= dp[i][j]
        else:
            ni = i-1
            nj = j
            ans = j
            break
    if ans > 0:
        break


while ni > 0:
    for j in range(nj-1,nj+2):
        if j<0 or j>9:
            continue
        if k > dp[ni][j]:
            k -= dp[ni][j]
        else:
            ans = ans*10+j
            nj = j
            break
    ni -= 1
print(ans)

Solution (Python):
from functools import reduce
from fractions import gcd
import queue
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")

def cnt(n, k):

    return k

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

    Q = queue.Queue()
    for i in range(1, 10):
        Q.put(str(i))
    
    cnt = 1
    while cnt < K:
        q = Q.get()
        cnt += 1
        n = int(q[-1])
        if n != 0:
            Q.put(q + str(n-1))
        Q.put(q + str(n))
        if n != 9:
            Q.put(q + str(n+1))
    
    print(Q.get())
            


if __name__ == '__main__':
    main()

Solution (Python):
def ith(N,i):
    
    return (N % (10 ** (i+1))) // 10 ** i
def next(N):
    if N < 10:
        return N+1
    if ith(N,0) == 9:
        up = next(N//10)
        
        if ith(up,0) == 0:
            return up * 10 + ith(up,0)
        else:
            return up * 10 + ith(up,0) - 1
    if ith(N,0) == ith(N,1) + 1:
        up = next(N//10)
        if ith(up,0) == 0:
            return up * 10 + ith(up,0)
        else:
            return up * 10 + ith(up,0) - 1
    return N + 1


def main():
    K = int(input())
    ans = 1
    for i in range(K-1):
        ans = next(ans)
    print(ans)
main()

Solution (Python):
input = raw_input

k = int(input())

suf_dict = {}
for d in range(10):
    if d == 0:
        suf_dict[str(d)] = ["0", "1"]
    elif d == 1:
        suf_dict[str(d)] = ["0", "1", "2"]
    elif d == 9:
        suf_dict[str(d)] = ["8", "9"]
    else:
        suf_dict[str(d)] = [str(d-1), str(d), str(d+1)]


def find(x):
    sufs = suf_dict[x[-1]]
    ret = [x+suf for suf in sufs]
    return ret

def main():
    xs = list("123456789")
    last_count = 9
    if k <= 9:
        out = k
        return out
    else:
        while True:
            next_xs = []
            for x in xs:
                first_count = last_count + 1
                elms = find(x)
                cur_num = len(elms)
                last_count = first_count + cur_num - 1
                
                if first_count <= k <= last_count:
                    out = elms[k-first_count]
                    return out
                next_xs += elms
            xs = next_xs

out = main()
print(out)

Solution (Python):
hoge=[1,2,3,4,5,6,7,8,9]
n=100001
new=[1,2,3,4,5,6,7,8,9]
while len(hoge)<n:
  huga=[]
  for i in range(len(new)):
    aaa=new[i]*10+new[i]%10
    huga.append(aaa)
    if(new[i]%10!=9):
      aaa=new[i]*10+new[i]%10+1
      if(1>=abs(int(str(aaa)[-1])-int(str(aaa)[-2]))):
        huga.append(aaa)
    if(new[i]%10!=0):
      aaa=new[i]*10+new[i]%10-1
      if(1>=abs(int(str(aaa)[-1])-int(str(aaa)[-2]))):
        huga.append(aaa)
  new=huga
  hoge=hoge+huga
hoge.sort()
print(hoge[int(input())-1])

Solution (Python):
K = int(input())
cnt = 9
li = [list(range(1,10))]
if(K<=cnt):
    print(li[0][K-1])
else:
    while(cnt<K):
        li.append([])
        for num in li[-2]:
            s_num = str(num)
            if(s_num[-1]=='0'):
                li[-1].append(num*10)
                li[-1].append(num*10+1)
                cnt += 2
            elif(s_num[-1]=='9'):
                li[-1].append(num*10+8)
                li[-1].append(num*10+9)
                cnt += 2
            else:
                last = int(s_num[-1])
                li[-1].append(num*10+last-1)
                li[-1].append(num*10+last)
                li[-1].append(num*10+last+1)
                cnt += 3
            if(cnt>=K):
                print(li[-1][-(cnt-K+1)])
                break

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

lists = [1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 0
while len(lists) <= k:
    num = lists[i]
    lastnum = num % 10
    if lastnum == 0:
        lists.append(num * 10 + 0)
        lists.append(num * 10 + 1)
    elif lastnum == 9:
        lists.append(num * 10 + 8)
        lists.append(num * 10 + 9)
    else:
        lists.append(num * 10 + lastnum-1)
        lists.append(num * 10 + lastnum)
        lists.append(num * 10 + lastnum+1)
    i+=1

print(lists[k-1])

Solution (Python):
k = int(input())
l = []

def lunlun(i):
    b = i[-1:]
    if int(i) <= 3234566667:
        if int(b)-1 >= 0 and int(b)-1 <= 9:
            l.append(int(i)*10+int(b)-1)
            lunlun(str(int(i)*10+int(b)-1))
        l.append(int(i)*10+int(b))
        lunlun(str(int(i)*10+int(b)))
        if int(b)+1 >= 0 and int(b)+1 <= 9:
            l.append(int(i)*10+int(b)+1)
            lunlun(str(int(i)*10+int(b)+1))
    

for i in range(1,10):
    l.append(i)
    lunlun(str(i))

l.sort()

print(l[k-1])

Solution (Python):
K = int(input())
seq = list(map(str, range(1, 10)))
answer = seq[:]
while True:
    tmp = []
    for i in seq:
        if i[-1] == '0':
            tmp.append(i + '0')
            tmp.append(i + '1')
        elif i[-1] == '9':
            tmp.append(i + '8')
            tmp.append(i + '9')
        else:
            t = ord(i[-1])
            tmp.append(i + chr(t - 1))
            tmp.append(i + i[-1])
            tmp.append(i + chr(t + 1))
    seq = tmp[:]
    answer.extend(seq[:])
    if len(seq) > K:
        break

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

Solution (Python):
def main():
    K = int(input())
    ans = set()

    def rec(S):
        if 3234566667 < int(S):
            return
        c = S[-1]
        d = int(c)
        for plus in range(d-1, d+2):
            if plus < 0:
                continue
            ans.add(int(S+str(plus)))
            rec(S+str(plus))

    for i in range(1, 10):
        ans.add(i)
        rec(str(i))

    ansc = ans.copy()
    for a in ansc:
        S = str(a)
        pre = ""
        for i, s in enumerate(S):
            if i == 0:
                pre = s
                continue
            if abs(int(pre) - int(s)) > 1:
                ans.discard(a)
                break
            pre = s
    answer = sorted(ans)
    print(answer[K-1])


if __name__ == '__main__':
    main()

Solution (Python):
K = int(input())
arr = list(range(1, 10))
i = 0
while len(arr) < K:
    num = arr[i]
    last = list(filter(lambda x: 0 <= x <= 9, [num%10-1, num%10, num%10+1]))
    arr.extend(num*10 + t for t in last)
    i += 1

print(arr[K-1])

Solution (Python):
k=int(input())
ans=[1,2,3,4,5,6,7,8,9]
p=[1,2,3,4,5,6,7,8,9]
c=9
while c<k:
    t=[]
    for i in p:
        j=i%10
        if j==0:
            t.append(i*10)
            t.append(i*10+1)
            c+=2
        elif j==9:
            t.append(i*10+8)
            t.append(i*10+9)
            c+=2
        else:
            t.append(i*10+j-1)
            t.append(i*10+j)
            t.append(i*10+j+1)
            c+=3
    ans.extend(t)
    p=t[::]
print(ans[k-1])

Solution (Python):
lunlun=[]

def find_lunlun(n,curr):
    global lunlun
    if curr>n:
        return

    lunlun.append(curr)
    el= curr%10
    find_lunlun(n,curr * 10 + el)
    if el==9:
        find_lunlun(n,curr*10+el-1)
    elif el==0:
        find_lunlun(n,curr*10+el+1)
    else:
        find_lunlun(n,curr*10+el-1)
        find_lunlun(n,curr*10+el+1)

for i in range(1,10):
    find_lunlun(10**10,i)
lunlun.sort()

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

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

result = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
prev = result
while True:
    new_prev = []
    for i in range(len(prev)):
        a = int(prev[i][-1]) - 1
        b = int(prev[i][-1])
        c = int(prev[i][-1]) + 1

        if a >= 0:
            a2 = prev[i]+str(a)
            new_prev.append(a2)
            result.append(a2)
        b2 = prev[i]+str(b)
        new_prev.append(prev[i]+str(b))
        result.append(b2)
        if c <= 9:
            c2 = prev[i]+str(c)
            new_prev.append(c2)
            result.append(c2)
    if len(result) >= k:
        break
    prev = new_prev
print(result[k-1])

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

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

K-=9

def append_ll(array, t, ll):
    global k
    
    array[t].append(ll)
    k += 1
    if k==K:
        print(ll)
        exit()

k = 0
N = 2
lunlun = [None, [None, [1],[2],[3],[4],[5],[6],[7],[8],[9]]]

while True:
    lunlun_N = [[] for _ in range(10)]

    p = 10**(N-1)
    append_ll(lunlun_N, 1, p)
    
    for d in range(1, N):
        for ll in lunlun[d][1]:
            append_ll(lunlun_N, 1, p+ll)

    for ll in lunlun[N-1][2]:
        append_ll(lunlun_N, 1, p+ll)
    
    for x in range(2, 10):
        for ll in lunlun[N-1][x-1]:
            append_ll(lunlun_N, x, x*p+ll)
            
        for ll in lunlun[N-1][x  ]:
            append_ll(lunlun_N, x, x*p+ll)

        if x==9: continue
        for ll in lunlun[N-1][x+1]:
            append_ll(lunlun_N, x, x*p+ll)

    N+=1
    lunlun.append(lunlun_N)

Solution (Python):
k=int(input())
num=[]

def d(n):
  num.append(n)
  if n > 3234570000:
    return
  a=n%10
  if a==0:
    l=[0,1]
  elif a==9:
    l=[8,9]
  else:
    l=[a-1,a,a+1]
  for i in l:
    s=int(str(n)+str(i))
    d(s)

for i in range(1,10):
  d(i)

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

Solution (Python):
import sys

k = int(input())

dp = [ [ [] for _ in range(10)]  for _ in range(10)]
num = 0

for i in range(0,10):
    for j in range(0,10):
        if i==0:
            candi = [""]
        else:
            candi = []
            if j>0: candi += dp[i-1][j-1]
            candi += dp[i-1][j]
            if j<9: candi += dp[i-1][j+1]
        for x in candi:
            x = str(j)+str(x)
            dp[i][j].append(x)
            if j>0:
                num += 1
                if num == k:
                    print(x)
                    sys.exit()

Solution (Python):
K = int(input())
if K <= 10:
    print(K)
    exit()

arr = [0] * K
for i in range(1, 10):
    arr[i - 1] = i

cur = 9
s = 0
while True:
    tmp = arr[s]
    num = tmp % 10
    
    if num > 0:
        arr[cur] = tmp * 10 + (num - 1)
        cur += 1
        if cur  == K:
            break
        
        
    arr[cur] = tmp * 10 + num
    cur += 1
    if cur == K:
        break

    if num < 9:
        arr[cur] = tmp * 10 + (num + 1)
        cur += 1
        if cur == K:
            break
    s += 1

print(arr[-1])

Solution (Python):
import sys
from collections import defaultdict
k=int(sys.stdin.readline())
arr=[1,2,3,4,5,6,7,8,9]
n=len(arr)
if k<=n:
    print(arr[k-1])
    sys.exit()
k-=n
next=[]
i=0
while k>=0 and i<n:
    x=arr[i]%10
    a,b,c=x-1,x,x+1
    if a!=-1:
        next.append(arr[i]*10+a)
        k-=1
        if k==0:
            print(next[-1])
    next.append(arr[i]*10+b)
    k-=1
    if k==0:
        print(next[-1])
    if c!=10:
        next.append(arr[i]*10+c)
        k-=1
        if k==0:
            print(next[-1])
    i+=1
    if i==n:
        arr=[j for j in next]
        i=0
        n=len(arr)
        next=[]

Solution (Python):
from sys import stdin
from collections import deque
 
input = stdin.readline
 
k = int(input())
q = deque(list(range(1, 10)))
res = deque(list(range(1, 10)))
cnt = 9

while True:
    t = q.popleft()
    r = t % 10
    
    if r == 0:
        q.append(t * 10)
        q.append(t * 10 + 1)
        res.append(t * 10)
        res.append(t * 10 + 1)
        cnt += 2
    elif r == 9:
        q.append(t * 10 + 8)
        q.append(t * 10 + 9)
        res.append(t * 10 + 8)
        res.append(t * 10 + 9)
        cnt += 2
    else:
        q.append(t * 10 + r - 1)
        q.append(t * 10 + r)
        q.append(t * 10 + r + 1)
        res.append(t * 10 + r - 1)
        res.append(t * 10 + r)
        res.append(t * 10 + r + 1)
        cnt += 3

    if cnt >= k:
        break

print(res[k - 1])

Solution (Python):
cands = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def add_v(v):
  global cands
  global K
  v = str(v)
  v0 = int(v[-1])
  if v0 == 0:
    cands += [int(v+'0'), int(v+'1')]
    K -=2
  elif v0 == 9:
    cands += [int(v+'8'), int(v+'9')]
    K -= 2
  else:
    cands += [int(v+str(v0-1)), int(v+str(v0)), int(v+str(v0+1))]
    K -= 3

K = int(input())
idk = K
K -= 9
idx = 0
while K >= 0:
  add_v(cands[idx])
  idx += 1

print(cands[idk-1])