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

lun=list(range(1,10))
i=0
while 1:
    ichi=lun[i]%10
    if ichi!=0:
        lun.append(lun[i]*10+ichi-1)
    lun.append(lun[i]*10+ichi)
    if ichi!=9:
        lun.append(lun[i]*10+ichi+1)
    i+=1
    if i==K:
        break
print(lun[i-1])

Solution (Python):
n = int(input())
ans = [[0 for i in range(10)] for i in range(12)]  
anscount = [[0 for i in range(10)] for i in range(12)]
ansnum = []

count = 9

import bisect

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


j = 0

while count < n:
    for i in range(10):
        if i == 0:
            ans[j + 2][i] = ans[j + 1][i] + ans[j + 1][i + 1]
        elif i == 9:
            ans[j + 2][i] = ans[j + 1][i - 1] + ans[j + 1][i]
            count += ans[j + 2][i]
        else:
            ans[j + 2][i] = ans[j + 1][i - 1] + ans[j + 1][i + 1] + ans[j + 1][i]
            count += ans[j + 2][i]
        anscount[j + 2][i] = count
    
    
    j += 1



keta = j + 1
hajime = bisect.bisect_left(anscount[keta], n)



num = anscount[keta][hajime - 1]
sa = n - num

ansnum.append(hajime)

count = 0

for i in reversed(range(1, keta)):
    if hajime != 0:
        if sa <= ans[i][hajime - 1]:
            hajime -= 1
        elif sa <= ans[i][hajime - 1] + ans[i][hajime]:
            hajime += 0
            sa -= ans[i][hajime - 1]
        else:
            sa -= (ans[i][hajime - 1] + ans[i][hajime])
            hajime += 1
    else:
        if sa <= ans[i][hajime]:
            hajime += 0
        else:
            sa -= ans[i][hajime]
            hajime += 1
    ansnum.append(hajime)
    
    

count = 0
sa = 1
for i in reversed(ansnum):
    count += i * sa
    sa *= 10
print(count)

Solution (Python):

q=[]
for i in range(1,10):
    q.append(i)
n=int(input())
ans=0
for i in range(n):
    size=len(q)
    a=q[size-(size-i)]
    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)
print(q[n-1])

Solution (Python):
if __name__ == '__main__':
	K = int(input())

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

	ans = 0
	count = 9
	check = 0

	if K < 10:
		ans = L[K][0]
		check = 1

	while check == 0:
		newL = [['']] * 10
		for i in range(10):
			newls = []
			if i == 0:
				for s in L[0]:
					newls.append(str(i)+s)
				for s in L[1]:
					newls.append(str(i)+s)
			elif i == 9:
				for s in L[8]:
					newls.append(str(i)+s)
					count += 1
					if count == K:
						ans = newls[-1]
						check = 1
				for s in L[9]:
					newls.append(str(i)+s)
					count += 1
					if count == K:
						ans = newls[-1]
						check = 1
			else:
				for j in range(-1,2):
					for s in L[i+j]:
						newls.append(str(i)+s)
						count += 1
						if count == K:
							ans = newls[-1]
							check = 1

			newL[i] = newls[:]

		L = newL[:]


	print(int(ans))

Solution (Python):
from collections import deque

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

Solution (Python):
from collections import deque

k = int(input())

d = deque(range(1, 10))

cnt = 0
lc = 0
while cnt<=max(0, k-9):
	x = d[lc]
	xdr10 = x%10
	if xdr10 != 0:
		d.append(10*x+xdr10-1)
		cnt += 1
	
	d.append(10*x+xdr10)
	cnt += 1
	
	if xdr10 != 9:
		d.append(10*x+xdr10+1)
		cnt += 1
	lc += 1

print(d[k-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):
    x = q.popleft()
    a = 10*x+(x % 10)
    if x % 10 != 0:
        q.append(a-1)
    q.append(a)
    if x % 10 != 9:
        q.append(a+1)

print(x)

Solution (Python):
def digits_to_number(digits):
    res = 0
    for d in reversed(digits):
        res *= 10
        res += d
    return res


def next_lunlun(n):
    digits = []
    x = n
    while x > 0:
        digits.append(x % 10)
        x //= 10
    for i in range(0, len(digits)-1):
        if digits[i] <= digits[i+1] and digits[i] != 9:
            digits[i] += 1
            for j in range(i-1, -1, -1):
                digits[j] = max(digits[j+1] - 1, 0)
            return digits_to_number(digits)
    if digits[-1] == 9:
        digits = [0] * len(digits)
        digits.append(1)
        return digits_to_number(digits)
    digits[-1] += 1
    for j in range(len(digits)-2, -1, -1):
        digits[j] = max(digits[j+1] - 1, 0)
    return digits_to_number(digits)


def kth_lunlun(k):
    lunlun = 1
    for i in range(0, k-1):
        lunlun = next_lunlun(lunlun)
    return lunlun

if __name__ == '__main__':
    k = int(input())
    print(kth_lunlun(k))

Solution (Python):
from collections import deque

K = int(input())
que = deque([i for i in range(1, 10)])
lunlun = []

while que:
    num = que.pop()
    lunlun.append(num)
    for i in range(10):
        if abs(int(str(num)[-1]) - i) <= 1:
            cand = int(str(num) + str(i))
            if cand < 10000000000:
                que.append(cand)

lunlun.sort()
print(sorted(lunlun)[K - 1])

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

Solution (Python):
k=int(input())
from collections import deque
q=deque(list(range(1,10)))
for i in range(k):
    p=q.popleft()
    if i==k-1:
        print(p)
        exit()
    a=p%10
    if 0<a<9:
        q.append(p*10+a-1)
        q.append(p*10+a)
        q.append(p*10+a+1)
    elif a==0:
        q.append(p*10)
        q.append(p*10+1)
    else:
        q.append(p*10+a-1)
        q.append(p*10+a)

Solution (Python):
def main():
    import sys
    from collections import deque

    input = sys.stdin.readline
    k = int(input())
    q = deque(range(1, 10))

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

if __name__ == "__main__":
    main()

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

Solution (Python):
ONE_KETA = 10

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

	
	if(K < ONE_KETA):
		print(K)
		return

	
	
	queue_list = [i for i in range(1, ONE_KETA)]
	K -= len(queue_list)

	
	while(K > 0):
		
		val = queue_list.pop(0)

		
		tmp_s_num = val % ONE_KETA

		for i in range(-1, 2):
			
			if(tmp_s_num == 9 and i == 1):
				continue
			elif(tmp_s_num == 0 and i == -1):
				continue
			else:
				
				tmp_val = val * 10 + tmp_s_num + i
				if(K > 0):
					queue_list.append(tmp_val)
					K -= 1

	
	print(queue_list.pop())
	return

if __name__ == "__main__":
	main()

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





K = inputI()


l = [[0,0,0,0,0,0,0,0,0,0]]
a = [0]

s = 0
for N in range(1,11):
  if N == 1:
    l.append([1,1,1,1,1,1,1,1,1,1])
  else:
    l.append([
      l[N-1][0]+l[N-1][1],
      l[N-1][0]+l[N-1][1]+l[N-1][2],
      l[N-1][1]+l[N-1][2]+l[N-1][3],
      l[N-1][2]+l[N-1][3]+l[N-1][4],
      l[N-1][3]+l[N-1][4]+l[N-1][5],
      l[N-1][4]+l[N-1][5]+l[N-1][6],
      l[N-1][5]+l[N-1][6]+l[N-1][7],
      l[N-1][6]+l[N-1][7]+l[N-1][8],
      l[N-1][7]+l[N-1][8]+l[N-1][9],
      l[N-1][8]+l[N-1][9]
    ])
  s += sum(l[N][1:])
  a.append(s)
  

N = 1
while K>a[N]:
  N += 1

ans = []

def first_highest(k):
  n = 1
  while k>a[n]:
    n += 1
  k -= a[n-1]
  i = 1
  while k>l[n][i]:
    k -= l[n][i]
    i+=1
  return(n,int(i),k)

N = first_highest(K)[0]
ans.append(first_highest(K)[1])

def later_highest(n,k):
  global ans
  if n > 1:
    i = max(0,ans[-1]-1)
    while k>l[n][i]:
      k -= l[n][i]
      i+=1
    return(n,int(i),k)
  else:
    if ans[-1] == 0:
      return(1,ans[-1]+k-1,0)
    else:
      return(1,ans[-1]+k-2,0)
  
N -= 1
K = first_highest(K)[2]

while N:
  piropiro = later_highest(N,K)
  ans.append(piropiro[1])
  K = piropiro[2]
  N -= 1

ans = map(str,ans)
print("".join(ans))