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.



Sample input:
15


Sample output:
23

Submission status: Accepted

Solution code:
k = int(input())
if k <= 10:
    print(k)
    exit()


def f(c, l):
    ret = ''
    for i in range(l):
        a = max(0, int(c) - i)
        ret += str(a)
    return ret


k -= 11
s = '11'
while k > 0:
    if s[-2] >= s[-1] and s[-1] < '9':
        s = s[:-1] + str(int(s[-1]) + 1)
        k -= 1
        continue
    c = False
    for j in range(len(s) - 2, 0, -1):
        if s[j] <= s[j+1] and s[j] <= s[j-1] and s[j] < '9':
            s = s[:j] + str(int(s[j])+1) + f(s[j],len(s)-j-1)
            k -= 1
            c = True
            break
    if c:
        continue

    if s[0] < s[1]:
        s = str(int(s[0]) + 1) + f(s[0], len(s) - 1)
        k -= 1
        continue

    s = '1' + '0' * len(s)
    k -= 1

print(s)

Submission status: Accepted

Solution code:
import sys
#K=100000
K=int(input())

if K<=9:
    print(K)
    sys.exit(0)

LS=[0]*11
LS[1]=[1,1,1,1,1,1,1,1,1,1]
LS2=[]
for i in range(2,11):
    LS[i]=[0]*10
    for j in range(0,10):
        for k in range(max(j-1,0),min(j+2,10)):
            LS[i][j]+=LS[i-1][k]
for i in range(1,11):
    for j in range(1,10):
        LS2+=[LS[i][j]]
#print(LS)
#print(LS2)
ans=""
total=0
keta=0
first=0
bktotal=0
for i in range(90):
    bktotal=total
    total+=LS2[i]
    if K<=total:
        ans+=str((i%9)+1)
        keta=(i//9)+1
        first=(i%9)+1
        K-=bktotal
        break
#print(keta)
#print(first)
#print(K)
while keta>1:
    backtotal=0
    total=0
    for i in range(max(0,first-1),min(10,first+2)):
        backtotal=total
        total+=LS[keta-1][i]
        if total>=K:
            ans+=str(i)
            first=i
            K-=backtotal
            break
    keta-=1
print(ans)

# lun=[]
# for i in range(1,10000):
#     s=str(i)
#     L=len(s)
#     islun=True
#     for j in range(L-1):
#         if abs(int(s[j])-int(s[j+1]))>1:
#             islun=False
#             break
#     if islun:
#         lun+=[i]
# print(lun)
# print(len(lun))

Submission status: Accepted

Solution code:
k = int(input())

if k <= 9:
    print(k)
    exit()
    
l = list(map(str, list(range(1,10))))
x = 0
for i in range(k):
    for j in (-1, 0, 1):
        if int(l[x][-1]) + j in (-1, 10):
            continue
        l.append(l[x] + str(int(l[x][-1]) + j))
    x += 1

print(l[k-1])

Submission status: Accepted

Solution code:
k = int(input())

lunlun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for li in lunlun:
     if 10**10 < li:
         break
     lunlun.append(li * 10 + li % 10)
     if 0 <= li % 10 < 9:
         lunlun.append(li * 10 + li % 10 + 1)
     if 0 < li % 10 <= 9:
         lunlun.append(li * 10 + li % 10 - 1)
lunlun.sort()
print(lunlun[k - 1])

Submission status: Accepted

Solution code:
k = int(input())
st = [[0 for _ in range(10)] for _ in range(11)]
for j in range(1, 10):
	st[1][j] = 1
for i in range(2, 11):
	st[i][1] = sum(st[j][1] for j in range(1, i)) + 1 + st[i-1][2]
	for j in range(2, 9):
		st[i][j] = st[i-1][j-1] + st[i-1][j] + st[i-1][j+1]
	st[i][9] = st[i-1][8] + st[i-1][9]

zero = [0 for _ in range(11)]
zero[1] = 1
for i in range(2, 11):
	zero[i] = sum(st[j][1] for j in range(1, i)) + 1
#print(zero)

cum = [0 for _ in range(11)]
cum[1] = 9
for i in range(2, 11):
	cum[i] = cum[i-1] + sum(st[i])


cnt = 0
ans = ""

flg = False
for i in range(1, 11):
	for j in range(1, 10):
		if cnt < k <= cnt+st[i][j]:
			x, y = i, j
			ans += str(y)
			k -= cnt
			flg = True
			break
		else:
			cnt += st[i][j]
	if flg:
		break
x -= 1

#print(x, y, k)
while x > 0:
	if 2 <= y:
		cnt = 0
		for j in range(y-1, min(y+2, 10)):
			if cnt < k <= cnt + st[x][j]:
				y = j
				x -= 1
				ans += str(y)
				k -= cnt
				break
			else:
				cnt += st[x][j]
	else:
		if k <= zero[x]:
			y = 0
			x -= 1
			ans += str(y)
		else:
			cnt = zero[x]
			for j in range(1, y+2):
				if cnt < k <= cnt + st[x][j]:
					y = j
					x -= 1
					ans += str(y)
					k -= cnt
					break
				else:
					cnt += st[x][j]

print(ans)

Submission status: Accepted

Solution code:
def f(t,i,j,ans):
  #print(t,i,j,ans)
  ft=0
  #print("f1")
  if j>0:
    ft+=a[i-1][j-1]
    #print(ft)
    if ft>=t:
      ans+=str(j-1)
      if i-1==0:
        return ans
      return f(t-(ft-a[i-1][j-1]),i-1,j-1,ans)
    
  ft+=a[i-1][j]
  #print(ft)
  if ft>=t:
    ans+=str(j)
    if i-1==0:
      return ans
    return f(t-(ft-a[i-1][j]),i-1,j,ans)
  
  if j<9:
    ft+=a[i-1][j+1]
    #print(ft)
    if ft>=t:
      ans+=str(j+1)
      if i-1==0:
        return ans
      return f(t-(ft-a[i-1][j+1]),i-1,j+1,ans)
  
      


k=int(input())

a=[[1,1,1,1,1,1,1,1,1,1]]
t=9
i=0
while 1:
  i+=1
  a+=[[0,0,0,0,0,0,0,0,0,0]]
  for j in range(10):
    if j==0:
      a[i][0]=a[i-1][0]+a[i-1][1]
    elif j==9:
      a[i][9]=a[i-1][8]+a[i-1][9]
      t+=a[i][9]
    else:
      a[i][j]=a[i-1][j-1]+a[i-1][j]+a[i-1][j+1]
      t+=a[i][j]
    if t>=k:
      ai=i
      aj=j
      break
  if t>=k:
    break
if k>9:
  ans=""
  ans+=str(j)
    
  ans=f(k-(t-a[ai][aj]),ai,aj,ans)
  print(ans)
else:
  print(k)

Submission status: Accepted

Solution code:
k = int(input())

dp = [[[] for j in range(11)] for i in range(11)]


for i in range(10):
    dp[1][i].append(i)
    dp[0][i].append(0)


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

k-=9

for i in range(2, 11):
    for j in range(1, 10):
        if j==1:
            for z in range(i):
                for x in dp[z][j]:
                    dp[i][j].append(j*10**(i-1)+x)
                    k-=1
                    if k==0:
                        print(dp[i][j][-1])
                        exit()
            for x in dp[i - 1][j + 1]:
                dp[i][j].append(j * 10 ** (i-1) + x)
                k-=1
                if k==0:
                    print(dp[i][j][-1])
                    exit()
        else:
            for x in dp[i-1][j-1]:
                dp[i][j].append(j*10**(i-1)+x)
                k-=1
                if k==0:
                    print(dp[i][j][-1])
                    exit()
            for x in dp[i - 1][j]:
                dp[i][j].append(j * 10 ** (i-1) + x)
                k-=1
                if k==0:
                    print(dp[i][j][-1])
                    exit()
            for x in dp[i - 1][j + 1]:
                dp[i][j].append(j * 10 ** (i-1) + x)
                k-=1
                if k==0:
                    print(dp[i][j][-1])
                    exit()

Submission status: Accepted

Solution code:
def main():
    k = int(input())
    l = []
    for i in range(1,10):
        l.extend(dfs(i))
    l.sort()
    print(l[k-1])
    
def dfs(n,limit = 10**9):
    l = [n]
    if n>limit:
        return l
    i = n%10
    n *=10

    if i==0:
        l.extend(dfs(n+i))
        l.extend(dfs(n+i+1))
        return l
    elif i==9:
        l.extend(dfs(n+i-1))
        l.extend(dfs(n+i))
        return l
    
    else:
        l.extend(dfs(n+i-1))
        l.extend(dfs(n+i))
        l.extend(dfs(n+i+1))
        return l

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
ii = lambda : int(input())
from collections import deque

k = ii()
l = deque()
run = [1,2,3,4,5,6,7,8,9]
ans = [1,2,3,4,5,6,7,8,9]

for i in range(2,100):
    ll=deque(run)
    keta = 10**(i-1)
    while len(ll)>0:
        v = ll.popleft()
        if(v>=keta):
            ans.append(v)
        else:
            p = v%10
            if p == 0:
                ll.append(v*10+0)
                ll.append(v*10+1)
            elif p==9:
                ll.append(v*10+8)
                ll.append(v*10+9)
            else:
                ll.append(v*10+p-1)
                ll.append(v*10+p)
                ll.append(v*10+p+1)
    if len(ans)>10**5:
        break
ans.sort()

print(ans[k-1])

Submission status: Accepted

Solution code:
K = int(input())

total_n = 9
n = K
A = list(range(1,10))

for i in range(1000):
    if total_n >= K:
        break

    else:
        n -= len(A)
        temp = []
        for num in A:
            amari = int(str(num)[-1])
            moto = num * 10
            if amari !=0 and amari % 10 != 9:
                temp.extend([moto + amari - 1, moto+amari, moto + amari + 1]) 
                total_n += 3
            elif amari == 0:
                temp.extend([moto+amari, moto + amari + 1])
                total_n += 2
            else:
                temp.extend([moto + amari - 1, moto+amari])
                total_n += 2
        A = temp

print(A[n-1])

Submission status: Accepted

Solution code:
K = int(input())
if K < 9:
  print(K)
else:
  K -= 9
  i = 0
  L = [1,2,3,4,5,6,7,8,9]
  M = []
  while K > 0:
    x = L[i]
    if  0 < x%10 < 9:
      if K > 3:
        L.append(x*10+ x%10 - 1)
        L.append(x*10 + x%10)
        L.append(x*10 + x%10 + 1)
        K -= 3
      elif K == 3:
        ans = x*10 + x%10 + 1
        K = 0
      elif K == 2:
        ans = x*10 + x%10
        K = 0
      elif K == 1:
        ans = x*10 + x%10 - 1
        K = 0
    elif x%10 == 0:
      if K > 2:
        L.append(x*10 + x%10)
        L.append(x*10 + x%10 + 1)
        K -= 2
      elif K == 2:
        ans = x*10 + x%10 + 1
        K = 0
      elif K == 1:
        ans = x*10 + x%10
        K = 0
    else:
      if K > 2:
        L.append(x*10+ x%10 - 1)
        L.append(x*10 + x%10)
        K -= 2
      elif K == 2:
        ans = x*10 + x%10
        K = 0
      elif K == 1:
        ans = x*10 + x%10 - 1
        K = 0
    i += 1
  print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

K = int(input())

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

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

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

Submission status: Accepted

Solution code:
def saiki(s):
  if len(s) > 10:
    return
  
  if s[-1] == '0':
    tmp1 = s+'1'
    tmp2 = s+'0'
    ans.append(int(tmp1))
    ans.append(int(tmp2))
    saiki(tmp1)
    saiki(tmp2)
    
  elif s[-1] == '9':
    tmp1 = s+'8'
    tmp2 = s+'9'
    ans.append(int(tmp1))
    ans.append(int(tmp2))
    saiki(tmp1)
    saiki(tmp2)
    
  else:
    last = int(s[-1])
    tmp1 = s + str(last+1)
    tmp2 = s + str(last-1)
    tmp3 = s + str(last)
    ans.append(int(tmp1))
    ans.append(int(tmp2))
    ans.append(int(tmp3))
    saiki(tmp1)
    saiki(tmp2)
    saiki(tmp3)

k = int(input())

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

for i in range(1,10):
  saiki(str(i))
  
ans = sorted(ans)

print(ans[k-1])

Submission status: Accepted

Solution code:

from collections import deque
a=[1,2,3,4,5,6,7,8,9]
q=deque(a)
while(1):
    x=q.popleft()
    s=str(x)
    n=len(s)
    n1=int(s[n-1])
    c1=str(int(s[n-1])-1)
    c2=str(int(s[n-1])+1)
    a.append(int(s+s[n-1]))
    q.append(int(s+s[n-1]))
    if(n1>0):
        a.append(int(s+c1))
        q.append(int(s+c1))
    if(n1<9):
        a.append(int(s+c2))
        q.append(int(s+c2))
    if(len(a)>200005):
        break
a.sort()
k=int(input())
print(a[k-1])

Submission status: Accepted

Solution code:
k = int(input()) - 1
def onesearch(last):
    if last < 0:
        return [9, 1]
    elif last == 0:
        return [2, 0]
    elif last == 9:
        return [2, 8]
    else:
        return [3, last - 1]
memo = {}
def search(i, last, rest):
    # print('search', (i, last, rest))
    if i == 0:
        n, base = onesearch(last)
        if rest < n:
            return (n, base + rest)
        else:
            return (n, -1)
    if (i, last) in memo:
        n, ret = memo[(i, last)]
        if ret >= 0:
            return (n, ret)
    n = 0
    if last < 0:
        for j in range(1, 10):
            n1, ret = search(i - 1, j, rest)
            if ret >= 0:
                return (n1, j * 10 ** i + ret)
            n += n1
            rest -= n1
        memo[(i, last)] = (n, -1)
        return (n, -1)
    for j in range(max(0, last - 1), min(10, last + 2)):
        n1, ret = search(i - 1, j, rest)
        if ret >= 0:
            return (n1, j * 10 ** i + ret)
        n += n1
        rest -= n1
    memo[(i, last)] = (n, -1)
    return (n, -1)
def sub(k):
    for i in range(20):
        n, ret = search(i, -1, k)
        if ret >= 0:
            return ret
        k -= n

print(sub(k))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K = INT()

def calc_next(n):  # nの次のルンルン数を求める
	l = len(n)
	n = n[::-1]
	i = 0
	for i in range(l-1):
		if n[i] != 9 and abs(n[i+1]-(n[i]+1))<=1:  # 指定の桁を1増やしてもOK
			n[i] += 1
			break
	else:  # 最後を変更
		if n[-1] == 9:  # 次の桁へ
			n = list(map(int, list("1"+"0"*l)))
			return n
		else:  # 先頭 +1
			i = l-1
			n[-1] += 1
	for j in range(i-1, -1, -1):  # i 桁以下を減らす
		n[j] = max(0, n[j+1]-1)
	return n[::-1]

N = [1]
cnt = 1
while cnt != K:
	N = calc_next(N)
	cnt += 1
print("".join(list(map(str, N))))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

k = int(input())
ten = [[0,1]] + [[i-1, i, i+1] for i in range(1,9)] + [[8,9]]

cnt = 0
heap = []
for i in range(1, 10):
    heappush(heap, [i, i])

memo = set()
while heap or cnt < 20:
    num,pre = heappop(heap)
    if num in memo or num < 1:
        continue
    else:
        memo.add(num)
    cnt += 1
    # print(num,pre)
    if cnt >= k:
        print(num)
        break
    for i in ten[pre]:
        heappush(heap, [num*10+i, i])

Submission status: Accepted

Solution code:
from sys import stdin
K = int(stdin.readline().rstrip())
ans = list(range(1,11))
def f(n):
    if int(n) > 3234566667:
        return
    #elif len(n) > 10:
    #    return
    elif n[0] == "0":
        return

    for i in range(10):
        if abs(int(n[-1])-i) <= 1:
            if int(n+str(i)) > 3234566667:
                return
            ans.append(int(n+str(i)))
            
            f(n+str(i))
    
for i in range(1,10):
    f(str(i))
    
print(sorted(set(ans))[K-1])

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from itertools import product
from collections import defaultdict
from collections import deque
def resolve():
    K = ir()
    s = deque([[i+1, 1, i+1] for i in range(9)])
    cnt = 0
    while cnt < K:
        v, keta, tmp = s.popleft()
        cnt += 1
        min_d = max(0, v-1)
        max_d = min(9, v+1)
        for i in range(min_d, max_d+1):
            s.append([i, keta+1, int(str(tmp)+str(i))])
    print(tmp)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 桁DPで範囲を絞る、0と9が例外
# 10桁からやってみる
K = ir()
dp = [[0] * 10 for _ in range(11)]
dp[0] = [1] * 10 # 0, 1-8, 9 1桁目
for i in range(1, 11):
    dp[i] = dp[i-1].copy()
    for j in range(10):
        if j > 0:
            dp[i][j] += dp[i-1][j-1]
        if j < 9:
            dp[i][j] += dp[i-1][j+1]

count = 0
for i in range(11):
    bl = False
    for j in range(1, 10):
        prev = count
        count += dp[i][j]
        if count >= K:
            start = (j, i, K-prev)
            bl = True
            break
    if bl:
        break

def dfs(i, last, num):
    global count, answer
    if i == 1:
        count -= 1
        if count == 0:
            print(num); exit()
    else:
        num *= 10
        if last == 0:
            dfs(i-1, 0, num + 0)
            dfs(i-1, 1, num + 1)
        elif last < 9:
            dfs(i-1, last-1, num + last - 1)
            dfs(i-1, last, num + last)
            dfs(i-1, last+1, num + last + 1)
        else:
            dfs(i-1, 8, num + 8)
            dfs(i-1, 9, num + 9)

answer = 0
head, digit, c = start
count = c
dfs(digit+1, head, head)

Submission status: Accepted

Solution code:
k = int(input())
if k < 10:
    print(k)
else:
    cnt = 9
    prev_lun = [[i] for i in range(10)]
    new_lun = [[] for _ in range(10)]
    size = 1  # digitnum-1
    continflag = True
    while True:
        new_lun[0] = prev_lun[0] + prev_lun[1]
        for i in range(1, 9):
            new_lun[i] = [i*10**size+x for x in (prev_lun[i - 1] + prev_lun[i] + prev_lun[i + 1])]
            cnt += len(new_lun[i])
            if cnt >= k:
                print(new_lun[i][k-cnt-1])
                continflag = False
                break
        if not continflag:
            break
        new_lun[9] = [9*10**size+x for x in (prev_lun[8] + prev_lun[9])]
        cnt += len(new_lun[9])
        if cnt >= k:
            print(new_lun[9][k-cnt-1])
            break
        size += 1
        prev_lun = new_lun
        new_lun = [[] for _ in range(10)]

Submission status: Accepted

Solution code:
k=int(input())
num=[]
for i in range(k):
    if (len(num)==0):
        num=[1]
    elif (len(num)==1):
        num[0]+=1
        if num[0]==10:
            num=[1, 0]
    else:
        saved=False
        ind=0
        j=len(num)-1
        while(not saved and j>0):
            if (num[j]-num[j-1])<=0:
                if not saved and num[j]!=9:
                    ind=j
                    saved=True
                
            j-=1
        if num[ind]!=9:
            num[ind]+=1
            for j in range(ind+1, len(num)):
                num[j]=max(num[j-1]-1, 0)
        else:
            l=len(num)
            num=[1]+[0]*l

            
for i in num:
    print(i, end='')
print()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    k = II()
    d = defaultdict(list)
    d[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    i = 0
    l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    while len(l) < k:
        tmp = d[i]
        tt = []
        for t in tmp:
            st = str(t)
            for i in range(-1, 2):
                x = int(st[-1]) + i
                if 10 > x >= 0:
                    ss = st + str(x)
                    tt.append(int(ss))
        i += 1
        d[i] = tt
        for ttt in tt:
            l.append(ttt)
    l.sort()
    print(l[k - 1])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

def is_luun(i):
    last_digit = i % 10
    i //= 10
    while i > 0:
        if abs((i % 10) - last_digit) > 1:
            return False
        last_digit = i % 10
        i //= 10
    return True

next_luun_memo = {}

def next_luun(n):
    if n in next_luun_memo:
        dprint("memoed: %d -> %d" % (n, next_luun_memo[n]))
        return next_luun_memo[n]
    if n < 10:
        dprint("here")
        next_luun_memo[n] = n + 1
        return n + 1
    first = n % 10
    tenth = (n // 10) % 10
    if first < 9 and abs(first + 1 - tenth) <= 1:
        next_luun_memo[n] = n + 1
        return n + 1

    ans_tenth = next_luun(n // 10)
    dprint("ans_tenth: %d" % ans_tenth)
    ans_first = min(abs(ans_tenth % 10 - 1), ans_tenth % 10)
    dprint("ans_first: %d" % ans_first)
    ans = ans_tenth * 10 + ans_first
    next_luun_memo[n] = ans
    return ans


def main():
    k = read(int)

    i = 1
    luun = 1
    while i < k:
        dprint("%dth luun: %d" % (i, luun))
        luun = next_luun(luun)
        i += 1
    dprint("%dth luun: %d" % (i, luun))
    print(luun)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

if __name__ == "__main__":
    K = int(input())
    runruns = []

    queue = deque()
    for i in range(1, 10):
        queue.appendleft(str(i))
        runruns.append(str(i))

    while len(runruns) < K:
        cur = queue.pop()
        for diff in [-1, 0, 1]:
            right = cur[-1]
            if (right == '0' and diff == -1) or (right == '9' and diff == 1):
                continue
            next_right = str(int(right) + diff)
            next_cur = cur + next_right
            runruns.append(next_cur)
            queue.appendleft(next_cur)

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

Submission status: Accepted

Solution code:
k = int(input())

ans = []


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

while len(ans) <= 110000:
    n = []
    cnt = 0
    for x in l:
        y = x * 10
        b = x % 10
        if b == 0:
            n.append(y)
            n.append(y+1)
        elif b == 9:
            n.append(y+b-1)
            n.append(y+b)
        else:
            n.append(y+b-1)
            n.append(y+b)
            n.append(y+b+1)
    l = n[:]
    ans.extend(l)

print(ans[k-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr  4 20:49:45 2020

@author: naoki
"""

K = int(input())

count = K
for keta_num in range(1,100):
    op = list(map(str,[i for i in range(1,10)]))
    for keta in range(1,keta_num):
        op = [j + i for j in op for i in [str(int(j[-1])-1),str(int(j[-1])),str(int(j[-1])+1)]  \
                         if int(i) >= 0 and int(i) <=9]
    if count > len(op):
        count -= len(op)
    else:
        print(int(op[count-1]))
        break

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    k=int(input())
    dp=[[0]*10 for _ in range(1000)]
    for i in range(10):
        dp[0][i]=1
    for i in range(999):
        dp[i+1][0]=dp[i][0]+dp[i][1]
        for j in range(1,9):
            dp[i+1][j]=dp[i][j-1]+dp[i][j]+dp[i][j+1]
        dp[i+1][9]=dp[i][8]+dp[i][9]
    flag=0
    for i in range(1000):
        for j in range(1,10):
            if k>dp[i][j]:
                k-=dp[i][j]
            else:
                flag=1
                break
        if flag==1:
            break
    ans=j*10**i
    while i>0:
        if j!=0:
            if k>dp[i-1][j-1]:
                k-=dp[i-1][j-1]
            else:
                i-=1
                ans+=(j-1)*10**i
                j-=1
                continue
        if k>dp[i-1][j]:
            k-=dp[i-1][j]
        else:
            i-=1
            ans+=j*10**i
            continue
        if j!=9:
            if k>dp[i-1][j+1]:
                k-=dp[i-1][j+1]
            else:
                i-=1
                ans+=(j+1)*10**i
                j+=1
                continue 
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k=int(input())
cnt=9
lst=[1,2,3,4,5,6,7,8,9]
if k<=9:
	print(lst[k-1])
else:
	tmp=[]
	while True:
		for i in lst:
			if i%10-1>=0:
				tmp.append(i*10+i%10-1)
			tmp.append(i*10+i%10)
			if i%10+1<=9:
				tmp.append(i*10+i%10+1)
		if cnt+len(tmp)>=k:
			break
		cnt+=len(tmp)
		lst=tmp
		tmp=[]
	print(tmp[k-cnt-1])

Submission status: Accepted

Solution code:
import sys

K = int(input())

if K < 10:
    print(K)
    sys.exit(0)

runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 9
while True:
    new_runrun = []
    for run in runrun:
        run_str = str(run)
        last_num = int(run_str[-1])
        for i in range(3):
            diff = i - 1
            if (last_num == 9 and diff == 1) or (last_num == 0 and diff == -1):
                continue
            ans = int(run_str + str(last_num + diff))
            new_runrun.append(ans)
            count += 1
            if count == K:
                print(ans)
                sys.exit(0)
    runrun = new_runrun

Submission status: Accepted

Solution code:
K = int(input())

X = [0] * 20
l = 0

for _ in range(K):
  for i in range(l + 2):
    if X[i] < 9 and (i >= l or X[i] < X[i + 1] + 1):
      if i > l:
        l = i
      X[i] += 1
      for j in range(i - 1, -1, -1):
        X[j] = max(X[j + 1] - 1, 0)
      break

print(''.join(str(x) for x in X[l::-1]))

Submission status: Accepted

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

for i in l:
    p=str(i)
    if 0<=int(p[-1])-1<10:
        l.append(int(str(i)+str(int(p[-1])-1)))
    l.append(int(str(i)+p[-1]))
    if 0<=int(p[-1])+1<10:
        l.append(int(str(i)+str(int(p[-1])+1)))
    if len(l)>10**5:
        break
print(l[k-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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


def Get(i):
    ans[i] = []
    for v in ans[i - 1]:
        if v[-1] == '0':
            ans[i].append(v + '0')
            ans[i].append(v + '1')
        elif v[-1] == '9':
            ans[i].append(v + '8')
            ans[i].append(v + '9')
        else:
            t = v[-1]
            ans[i].append(v + str(int(t) - 1))
            ans[i].append(v + str(int(t)))
            ans[i].append(v + str(int(t) + 1))


def GetValueIndex(K):
    i = 1
    while True:
        if len(ans[i]) < K:
            K -= len(ans[i])
            i += 1
        else:
            ans[i].sort()
            return ans[i][K - 1]


K = int(input())

ans = {1: [str(i) for i in range(1, 10)]}
i = 2
while sum(len(v) for v in ans.values()) < K:
    Get(i)
    i += 1

print(GetValueIndex(K))

Submission status: Accepted

Solution code:
k = int(input())
c = 0
ans = [[]]
ans[0] = [1,2,3,4,5,6,7,8,9]
for i in range(1,10):
  s = []
  for j in range(10):
    for a in ans[i-1]:
      if j == a%10 or j-1 == a%10 or j+1 == a%10:
        s.append(int(str(a)+str(j)))
  ans.append(s)
        
ans = list(sum(ans,[]))
ans.sort()
print(ans[k-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
count = 0


def solve(K: int):

    def cDfs(prev, prevDigit, remainDigit):
        global count
        if remainDigit == 0:
            count += 1
            if count == K:
                print(prev)
                exit()
            # print(prev)
            return
        else:
            if prevDigit == 0:
                cDfs(prev*10, prevDigit, remainDigit-1)
                cDfs(prev*10+1, 1, remainDigit-1)
            elif prevDigit == 9:
                cDfs(prev*10+8, 8, remainDigit-1)
                cDfs(prev*10+9, prevDigit, remainDigit-1)
            else:
                a = (prevDigit+1) % 10
                b = (prevDigit-1) % 10
                MIN = min(a, b)
                MAX = max(a, b)
                cDfs(prev*10+MIN, MIN, remainDigit-1)
                cDfs(prev*10+prevDigit, prevDigit, remainDigit-1)
                cDfs(prev*10+MAX, MAX, remainDigit-1)
    for i in range(0, 100):
        for j in range(1, 10):
            cDfs(j, j, i)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)


if __name__ == '__main__':
    main()