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

base_runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
test_num = max(base_runrun) + 1

def check_runrun(num):
    runrun_flg = True
    str_num = str(num)
    for i in range(len(str_num)-1):
        if abs(int(str_num[i]) - int(str_num[i+1]))>1:
            runrun_flg = False
            break
    return runrun_flg

def check_ceil(num):
    str_num = str(num)
    ceil_digit = None
    for i in range(len(str_num)-1):
        tmp = int(str_num[i]) - int(str_num[i+1])
        if tmp >1:
            ceil_digit = i + 1 # 桁数とリストのインデックス調整
            nine = False
        elif tmp < -1:
            ceil_digit = i + 1 # 桁数とリストのインデックス調整
            nine = True
            break
    if ceil_digit is not None:
        if nine:
            num_seq = ''
            for _ in range(len(str_num)-ceil_digit):
                num_seq = num_seq + '9'
            str_num = str_num[:ceil_digit] + num_seq
            str_num = str(int(str_num)+1)
        else:
            num_seq = str(int(str_num[ceil_digit-1])-1)
            for _ in range(len(str_num)-ceil_digit-1):
                num_seq = num_seq + '0'
            str_num = str_num[:ceil_digit] + num_seq
    return int(str_num)


while K > len(base_runrun):
    runrun_flg = check_runrun(test_num)
    if runrun_flg:
        base_runrun.append(test_num)
        test_num += 1
    else:
        test_num = check_ceil(test_num)
print(base_runrun[K-1])

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
nums=[1,2,3,4,5,6,7,8,9]
lst=deque()
for j in nums:
  d=deque()
  d.append(j)
  while len(d)<10**5:
    num=d.popleft()
    lst.append(num)
    s=str(num)
    l=len(s)
    t=int(s[l-1])
    if 1<=t<=8:
      d.append(s+str(t-1))
      d.append(s+str(t))
      d.append(s+str(t+1))
    if t==0:
      d.append(s+str(0))
      d.append(s+str(1))
    if t==9:
      d.append(s+str(8))
      d.append(s+str(9))

Lst=list(lst)
Lst=list(map(int,Lst))
Lst.sort()
print(Lst[k-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
ans = [0] * 10
ans[1] = '1'
for i in range(2, 10):
    ans[i] = str(i)
alpha = "0123456789"
def dfs(s):
    if len(s) == N:
        ans.append(s)
        if len(ans) >= 100001:
            return
    else:
        for c in range(int(s[-1])-1,int(s[-1])+2):
            if c >= 0:
                dfs(s+str(c))
            if c == 9:
                break
K = int(input())
N = 2
while len(ans) < 100001:
    for i in range(1, 10):
        dfs(str(i))
        if len(ans) >= 100001:
            break
    N+=1

print(ans[K])

Submission status: Accepted

Solution code:
N=int(input())
list = []

def standard(n, cur):
  if n == 0:
    add = ''.join(cur)
    if str(add).isnumeric():
        list.append(int(add))
  else:
    newC = chr(ord(cur[-1]) - 1)
    standard(n - 1, cur + [newC])
    newC2 = chr(ord(cur[-1]))
    standard(n - 1, cur + [newC2])
    newC3 = chr(ord(cur[-1]) + 1)
    standard(n - 1, cur + [newC3])

for i in range(10):
    for j in range(9):
        standard(i, [str(j+1)])

print(list[N-1])

Submission status: Accepted

Solution code:
from collections import deque
li=[i for i in range(1,10)]
def bfs(K):
    d=deque()
    for i in range(1,10):
        d.append(str(i))
    while(len(li)<K):
        s=d[0]
        d.popleft()
        now=[int(s+s[-1])]
        if(s[-1]!='0'):
            now.append(int(s+str(int(s[-1])-1)))
        if(s[-1]!='9'):
            now.append(int(s+str(int(s[-1])+1)))
        now.sort()
        for i in range(len(now)):
            li.append(now[i])
            d.append(str(now[i]))
K=int(input())
bfs(K)
print(li[K-1])

Submission status: Accepted

Solution code:
import numpy as np
K=int(input())

n=np.zeros((10,11),dtype=int)
for i in range(9):
	n[i+1,1]=1
	n[i+1,2]=3
n[9,2]=2

for i in range(3,11):
	n[1,i]=n[2,i-1]+np.sum(n[1,:])+1
	n[2,i]=n[1,i-1]+n[2,i-1]+n[3,i-1]
	n[3,i]=n[4,i-1]+n[2,i-1]+n[3,i-1]
	n[4,i]=n[4,i-1]+n[5,i-1]+n[3,i-1]
	n[5,i]=n[4,i-1]+n[5,i-1]+n[6,i-1]
	n[6,i]=n[5,i-1]+n[6,i-1]+n[7,i-1]
	n[7,i]=n[7,i-1]+n[8,i-1]+n[6,i-1]
	n[8,i]=n[7,i-1]+n[8,i-1]+n[9,i-1]
	n[9,i]=n[8,i-1]+n[9,i-1]

i=1
j=1

def ninecheck(i,j,K,ans):
	for k in range(2):
		K-=n[i-1+k,j]
		if K<=0:
			K+=n[i-1+k,j]
			ans+=(i-1+k)*(10**(j-1))
			if j==1:
				a=ans
				return a
			j-=1
			i=i-1+k
			if i==1:
				a=onecheck(i,j,K,ans)
				return a
			elif i==9:
				a=ninecheck(i,j,K,ans)
				return a
			else:
				a=normalcheck(i,j,K,ans)
				return a

def onecheck(i,j,K,ans):
	K-=1
	if K==0:
		a=ans
		return a
	for k in range(1,j+1):
		K-=n[1,k]
		if K<=0:
			K+=n[1,k]
			ans+=10**(k-1)
			j=k
			if j==1:
				a=ans
				return a
			j-=1
			a=onecheck(i,j,K,ans)
			return a
	i=2
	ans+=i*(10**(j-1))
	j-=1
	a=normalcheck(i,j,K,ans)
	return a

def normalcheck(i,j,K,ans):
	for k in range(3):
		K-=n[i-1+k,j]
		if K<=0:
			K+=n[i-1+k,j]
			ans+=(i-1+k)*(10**(j-1))
			if j==1:
				a=ans
				return a
			j-=1
			i=i-1+k
			if i==1:
				a=onecheck(i,j,K,ans)
				return a
			elif i==9:
				a=ninecheck(i,j,K,ans)
				return a
			else:
				a=normalcheck(i,j,K,ans)
				return a



ans=0
while True:
	K-=n[i,j]
	if K<=0:
		ans+=i*(10**(j-1))
		K+=n[i,j]
		if j==1:
			b=ans
			break
		j-=1
		if i==1:
			b=onecheck(i,j,K,ans)
			break
		elif i==9:
			b=ninecheck(i,j,K,ans)
			break
		else:
			b=normalcheck(i,j,K,ans)
			break
	if i==9:
		i=1
		j+=1
	else:
		i+=1
		continue




print(b)

Submission status: Accepted

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

def main():
    N = int(input())
    base = [i+1 for i in range(9)]
    m = 3234566667+10000
    
    while len(base) < N:
        use = base
        for num in base:
            st = str(num)
            if st[-1] == "0":
                if int(st+"0") <= m:
                    use.append(int(st+"0")) 
                if int(st+"1") <= m:
                    use.append(int(st+"1"))
            elif st[-1] == "9":
                if int(st+"8") <= m:
                    use.append(int(st+"8"))
                if int(st+"9") <= m:
                    use.append(int(st+"9"))
            else:
                s = int(st[-1])
                st = int(st)
                if st*10+s-1 <= m:
                    use.append(st*10+s-1)
                if st*10+s <= m:
                    use.append(st*10+s)
                if st*10+s+1 <= m:
                    use.append(st*10+s+1)
        base = use
        
    print(base[N-1])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k = int(input())
a = []

def lun(x,y,z): # xが一つ前の桁の数字 yがここまでの仮のルンルン数 zが桁数
  if z == 1:
    if x != 0:
      a.append(y+x-1)
    a.append(y+x)
    if x != 9:
      a.append(y+x+1)
  else:
    if x != 0: 
      b = y + (x-1)*(10**(z-1))
      lun(x-1,b,z-1)
    b = y + x*(10**(z-1))
    lun(x,b,z-1)
    if x!= 9:
      b = y + (x+1)*(10**(z-1))
      lun(x+1,b,z-1)

# 1桁のルンルン数
for i in range(1,10):
  a.append(i)

for j in range(2,11):
  for i in range(1,10):
    lun(i,i*(10**(j-1)),j-1)

print(a[k-1])

Submission status: Accepted

Solution code:
K = int(input())

table = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in table:
	if len(table) > K:
		break
	x = i % 10
	for j in range(max(0, x - 1), min(x + 2, 10)):
		table.append(i * 10 + j)

print(table[K - 1])

Submission status: Accepted

Solution code:
import itertools

K = int(input())

keta_list = [['1', '2', '3', '4', '5', '6', '7', '8', '9']]
keta = 1
count = len(keta_list[0])

def create_lunlun():
    global keta
    global keta_list
    global count

    base_num = keta_list[keta - 1]

    new_keta_list = []

    for num in base_num:
        if num[-1] >= '1' and num[-1] <= '8':
            new_keta_list.append(num + str(int(num[-1])-1))
            new_keta_list.append(num + num[-1])
            new_keta_list.append(num + str(int(num[-1])+1))
        elif num[-1] == '0':
            new_keta_list.append(num + num[-1])
            new_keta_list.append(num + str(int(num[-1])+1))
        else:
            new_keta_list.append(num + str(int(num[-1])-1))
            new_keta_list.append(num + num[-1])

    keta_list.append(new_keta_list)
    keta += 1

    count += len(new_keta_list)
    if count >= 10**5:
        return
    
    create_lunlun()


create_lunlun()

keta_list = list(itertools.chain.from_iterable(keta_list))

print(keta_list[K-1])

Submission status: Accepted

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

cnt = []
cnt.append([[0]*10 for i in range(10)])
cnt.append([[1 if i == j else 0 for j in range(10)] for i in range(10)])
# cnt[1][0][0] = 0

total = 9

loop = True
x = 1
head = 1
while loop:
    x += 1
    cnt.append([[0] * 10 for _ in range(10)])
    for h in range(0, 10):
        head_total = 0
        head = h
        cnt[x][h][0] = cnt[x - 1][h][0] + cnt[x - 1][h][1]
        head_total += cnt[x][h][0]
        for i in range(1, 9):
            cnt[x][h][i] = cnt[x - 1][h][i - 1] + \
                cnt[x - 1][h][i] + cnt[x - 1][h][i + 1]
            head_total += cnt[x][h][i]

        cnt[x][h][9] = cnt[x - 1][h][8] + cnt[x - 1][h][9]
        head_total += cnt[x][h][9]
        if h == 0:
            continue

        if total + head_total >= k:
            loop = False
            break
        else:
            total += head_total


result = head

for i in range(x - 1, 0, -1):

    for h in [head - 1, head, head + 1]:
        if h < 0 or 9 < h:
            continue
        t = sum(cnt[i][h])
        if total+t < k:
            total += t
        else:
            result = result * 10 + h
            head = h
            break
print(result)

Submission status: Accepted

Solution code:
import collections
k = int(input())
n = 10**10

li = list(range(1,10))
num_li = li[:]
q = collections.deque(li)
count = 0

for i in range(1,n):
    num = str(q.popleft())
    go = int(num[-1])
    if go != 0:
        numa = num + str(go - 1)
        num_li.append(int(numa))
        q.append(int(numa))
        count += 1
    numa = num + str(go)
    num_li.append(int(numa))
    q.append(int(numa))
    count += 1
    if go != 9:
        numa = num + str(go + 1)
        num_li.append(int(numa))
        q.append(int(numa))
        count += 1

    if count > k+1:
        break

print(num_li[k-1])

Submission status: Accepted

Solution code:
n=int(input())
if n<10: print(n); exit()
r=range
l=[[[] for _ in r(10)] for _ in r(10)]
l[0]=[[i] for i in r(10)]
c=9
for i in r(9):
  for j in r(10):
    for k in r(-1,2):
      if 0<=j+k<=9:
        for h in l[i][j+k]:
          if j: c+=1
          t=j*10**(i+1)+h
          l[i+1][j]+=[t]
          if c==n: print(t); exit()

Submission status: Accepted

Solution code:
import sys
k=int(input())
ans=[""]
for i in range(1,13):
    ans.append(i)
for i in range(1,8):
    a=10*(i+1)+(i)
    for j in range(3):
        ans.append(a)
        a+=1
ans.append(98)
ans.append(99)
#print(ans)
#print(len(ans))
if k<=35:
    print(ans[k])
else:
    def search(i,j):
        total=0
        if i==1:
            #print(j)
            return 1
        for m in range(10):
            if abs(j-m)<=1:
                total+=search(i-1,m)
        return total
    def search2(i,j,anss):
        global plus,aaa
        if i==1:
            plus+=1
            #print(kind)
            #print(anss)
            #print(aaa+plus)
            if k==aaa+plus:
                #print(aaa+plus)
                print(anss)
            return 
        for m in range(10):
            if abs(j-m)<=1:
                search2(i-1,m,anss+str(m))
    num=[35] #各桁の種類(累計
    for i in range(3,11): #桁数
        for j in range(1,10): #先頭の数字
            count=search(i,j)
            num.append(num[-1]+count)
    #print(num)
    ab=0
    while num[ab]<k:
        ab+=1
    #print(ab)
    rank=ab//9
    sento=ab%9
    if sento==0:
        sento=9
    #where=sento*(10**(2+rank))
    #print(where)
    aaa=num[ab-1]
    plus=0
    search2(3+rank,sento,str(sento))

Submission status: Accepted

Solution code:
k = int(input())
ok = 10**18
ng = 0
while ok-ng>1:
    mid = (ok+ng)//2
    s = list(map(int, list(str(mid))))
    n = len(s)
    dp = [[[0]*2 for i in range(10)] for j in range(n)]
    for i in range(1, s[0]):
        dp[0][i][0] = 1

    dp[0][s[0]][1] = 1
    for i in range(n-1):
        for d in range(1, 10):
            dp[i+1][d][0]+=1
        for d in range(10):
            if d+1 < 10:
                dp[i+1][d+1][0] += dp[i][d][0]
            if d-1 >= 0:
                dp[i+1][d-1][0] += dp[i][d][0]
            dp[i+1][d][0] += dp[i][d][0]
        if s[i]>0:
            if s[i+1] == s[i]-1:
                dp[i+1][s[i]-1][1]+=dp[i][s[i]][1]
            elif s[i+1]>s[i]-1:
                dp[i+1][s[i]-1][0]+=dp[i][s[i]][1]
        if s[i]<9:
            if s[i+1] == s[i]+1:
                dp[i+1][s[i]+1][1]+=dp[i][s[i]][1]
            elif s[i+1]>s[i]+1:
                dp[i+1][s[i]+1][0]+=dp[i][s[i]][1]
        if s[i+1] == s[i]:
            dp[i+1][s[i]][1]+=dp[i][s[i]][1]
        elif s[i+1]>s[i]:
            dp[i+1][s[i]][0]+=dp[i][s[i]][1]
    res = 0
    for d in range(10):
        res+=dp[n-1][d][0]+dp[n-1][d][1]
    if res>=k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
k = int(input())
n = 1
cnt = 0
flg = 0
while True:
  if flg == 1:
    n += 1
  flg = 0
  strn = str(n)
  if len(strn) == 1:
    cnt += 1
    flg = 1
  else:
    for s in range(len(strn)):
      if s == len(strn) - 1:
        cnt += 1
        flg = 1
      else:
        if abs(int(strn[s]) - int(strn[s+1])) > 1:
          if int(strn[s]) - int(strn[s+1]) > 1:
            new = ''
            for ss in range(len(strn)):
              if s+1 == ss:
                new += str(int(strn[s]) - 1)
              else:
                new += strn[ss]
            n = int(new)
          else:
            new = ''
            for ss in range(len(strn)):
              if s == ss:
                new += str(int(strn[s]) + 1)
              elif s+1 == ss:
                new += '0'
              else:
                new += strn[ss]
            n = int(new)
          break
          
    
  if cnt == k:
    print(n)
    break

Submission status: Accepted

Solution code:
k = int(input())
n = 0

def ff(s, i):
    for j in range(i+1, len(s)):
        #print(s[j-1])
        if s[j-1] > 0:
            s[j] = s[j-1] - 1
        else:
            s[j] = 0
    return s

def next(s):
    ls = len(s)
    for i in range(ls-1, 0, -1):
        if s[i-1] >= s[i] and s[i] != 9:
            s[i] += 1
            #print(s[i-1],s[i])
            return ff(s, i)
    if s[0] == 9:
        return [1] + ([0] * ls)
    else:
        s[0] += 1
        return ff(s, 0)

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

ans = [1,0]
for i in range(k - 10):
    ans = next(ans)
#print(ans)
print(''.join(map(str, ans)))

Submission status: Accepted

Solution code:
k = int(input())
l = set()

# lunnum : 構築中のルンルン数
#  depth : 桁数
#   flag : 上位桁が全て0かどうかのフラグ
def construct(lunnum: str, depth: int, flag: bool):
    global l
    if depth == 0:
        l.add(int(lunnum))
        return
    # m = 末尾桁の値
    m = int(lunnum[-1])
    if flag:
        # 上位桁に0以外の数字が無いなら
        for i in range(0, 10):
            construct(lunnum + str(i), depth - 1, i == 0)
    else:
        # m=[1,8] は [m-1,m,m+1], m=0 は [0,1], m=9 は [8,9] を末尾にくっつけて再帰
        for i in set([max(0, m - 1), m, min(9, m + 1)]):
            construct(lunnum + str(i), depth - 1, False)


# サンプルケース(input=100000 output=3234566667)より、答えは10桁以下であるのでdepth=10としてDFS
construct("0", 10, True)
ls = sorted(list(l))
print(ls[k])

Submission status: Accepted

Solution code:
#coding:utf-8

def up(nums):
    if len(nums) == nums.count(9):
        nums = [1] + [0] * len(nums)
        return nums
    
    for i in list(reversed(range(len(nums)))):
        if nums[i] > nums[i-1] or nums[i] == 9:
            continue
        else:
            nums[i] += 1
            for j in range(i+1, len(nums)):
                if j == len(nums) - 1:
                    nums[j] = max(nums[j-1]-1, 0)
                else:
                    nums[j] = max(nums[j-1] - 1, 0)
            return nums
          
  
def main():
    k = int(input())
    if k < 10:
        print(k)
        return
    cnt = 11
    nums = [1, 0]
    while cnt <= k:
        cnt += 1
        nums = up(nums)
        #print(nums)
        
    print(''.join([str(num) for num in nums]))
        
    
        
  
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K=int(input())

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

def Judge1(number):
    letter=str(number)
    judge=1
    if number==1:
        judge=0
    elif letter[0]!='1':
        judge=0
    else:
        for i in range(1,len(letter)):
            if letter[i]!='0':
                judge=0
                break 
    return judge

def Judge9(number):
    letter=str(number)
    judge=1
    for i in range(len(letter)):
        if letter[i]!='9':
            judge=0
            break
    return judge

def generate(number):
    if Judge1(number)==1:
        return [number*10,number*10+1]
    elif Judge9(number)==1:
        return [number*10+8,number*10+9]
    else:
        letter=str(number)
        newnumber=int(letter+letter[-1])
        return [newnumber-1,newnumber,newnumber+1]

def Generate(L):
    A=[]
    for i in range(len(L)):
        A.extend(generate(L[i]))
    return A

def check(number):
    letter=str(number)
    judge=1
    for i in range(len(letter)-1):
        if abs(int(letter[i])-int(letter[i+1]))>1:
            judge=0
            break
    return judge

Ans=[G]
ANS=[1,2,3,4,5,6,7,8,9]
for x in range(9):
    N=Generate(Ans[-1])
    NN=[]
    for y in range(len(N)):
        if check(N[y])==1:
            NN.append(N[y])
    Ans.append(NN)
    ANS.extend(NN)


#print(Ans)
#print(LastANS)
#print(len(ANS))
print(ANS[K-1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
n = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
q = deque(['0'])
cnt = 0
ans = []
while len(q):
    v = q.pop()
    # print(v, cnt)
    if k + 1 == cnt:
        print(ans[-1])
        # print(ans)
        exit()
    check = int(v[-1])

    # print(v, check)

    for plus in n:
        st = str(v) + str(plus)

        if str(st)[0] == '0' and str(st)[1] == '0':
            continue

        if len(st) > 12:
            continue

        if abs(check - plus) > 1 and len(st) != 2:
            # print(check, plus, str(v) + str(plus))
            continue
        cnt += 1
        if k + 1 == cnt:
            ans_show = ans[-1]
            for g in range(len(ans_show)):
                if g == 0 and ans_show[0] == '0':
                    pass
                else:
                    print(ans_show[g], end='')
            exit()
        # print(q)
        ans.append(str(v) + str(plus))
        q.appendleft(st)

Submission status: Accepted

Solution code:
K = int(input())

lunlun = list(range(1, 10))
last_lunlun = lunlun
for j in range(9):
    new = []
    for l in last_lunlun:
        last = int(str(l)[-1])
        for i in [-1, 0, 1]:
            if last + i >= 0 and last + i < 10:
                new.append(10 * l + last + i)
    last_lunlun = new
    lunlun.extend(new)

lunlun.sort()

print(lunlun[K-1])

Submission status: Accepted

Solution code:

def resolve():
    import sys
    input = sys.stdin.readline
    k = int(input().rstrip())

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

    def judge(number_list, index, total):
        if index == len(number_list) - 2:  # 最後から2番目の桁
            num = number_list[index]
            add_num = 2 if num in (0, 9) else 3
            if (total + add_num) < k:
                total += add_num
                return total
            else:
                if num == 0:
                    right_nums = [num, num + 1]
                elif num == 9:
                    right_nums = [num-1,num]
                else:
                    right_nums = [num-1,num,num+1]
                number_list[-1] = right_nums[k-total-1]
                # print("".join(number_list))
                print(*number_list,sep="")
                sys.exit()
        else:  # 最後から２番目の桁じゃない
            num = number_list[index]
            if num == 0:
                right_nums = [num, num + 1]
            elif num == 9:
                right_nums = [num - 1, num]
            else:
                right_nums = [num - 1, num, num + 1]

            for right_num in right_nums:
                number_list[index+1] = right_num
                total = judge(number_list, index+1, total)
            return total

    total = 9
    num_list = [9]
    while True:
        num_list = [0 for _ in range(len(num_list)+1)]
        for left in [1,2,3,4,5,6,7,8,9]:
            num_list[0] = left
            # print(num_list, 0, total)
            total = judge(num_list, 0, total)




if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
k=int(input())
L=[1,2,3,4,5,6,7,8,9]
Sz=['0']
Tz=[]
Sn=[1,2,3,4,5,6,7,8,9]
Tn=[]

i=9
while i<=k:
    for z in Sz:
        L.append(int('1'+z))
        i+=1
        Tn.append(int('1'+z))
        Tz.append('0'+z)
    Sz=[]
    Sz=Tz[:]
    Tz=[]
    
        
    for n in Sn:
        if int(str(n)[0])==1:
            Sz.append(str(int(str(n)[0])-1)+str(n))
            L.append(int(str(n)[0]+str(n)))
            L.append(int(str(int(str(n)[0])+1)+str(n)))
            Tn.append(int(str(n)[0]+str(n)))
            Tn.append(int(str(int(str(n)[0])+1)+str(n)))
            i+=2
        elif 2<=int(str(n)[0])<=8:
            L.append(int(str(int(str(n)[0])-1)+str(n)))
            L.append(int(str(n)[0]+str(n)))
            L.append(int(str(int(str(n)[0])+1)+str(n)))
            Tn.append(int(str(int(str(n)[0])-1)+str(n)))
            Tn.append(int(str(n)[0]+str(n)))
            Tn.append(int(str(int(str(n)[0])+1)+str(n)))
            i+=3
        else:    
            L.append(int(str(int(str(n)[0])-1)+str(n)))
            L.append(int(str(n)[0]+str(n)))
            Tn.append(int(str(int(str(n)[0])-1)+str(n)))
            Tn.append(int(str(n)[0]+str(n)))
            i+=2
    Sn=[]
    Sn=Tn[:]
    Tn=[]

LS=sorted(L)
print(LS[k-1])

Submission status: Accepted

Solution code:
K = int(input())

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

for i in table:
	if len(table) > K:
		break
	x = i % 10
	if x != 0 and x != 9:
		for j in range(x - 1, x + 2):
			table.append(i * 10 + j)
	elif x == 0:
		for j in range(x, x + 2):
			table.append(i * 10 + j)
	else:
		for j in range(x - 1, x + 1):
				table.append(i * 10 + j)

print(table[K - 1])

Submission status: Accepted

Solution code:
k = int(input())

def get_below(a):
    s = str(a)
    if len(s) == 1:
        return a
    else:
        ret = 0
        for i in range(len(s)):
            ret += sum(nums[i][1:])

        for i in range(1, int(s[0])):
            ret += nums[len(s)][i]

        def dfs(ss):
            # start: fixed
            if len(ss) == 1:
                return 1
            if int(ss[0]) > int(ss[1]) + 1:
                return 0
            elif int(ss[0]) == int(ss[1]) + 1:
                return dfs(ss[1:])
            elif int(ss[0]) == int(ss[1]):
                ret = 0
                if int(ss[1]) != 0:
                    ret += nums[len(ss) - 1][int(ss[1]) - 1]
                return ret + dfs(ss[1:])
            elif int(ss[0]) + 1 == int(ss[1]):
                ret = 0
                if int(ss[1]) >= 1:
                    ret += nums[len(ss) - 1][int(ss[1]) - 1]
                if int(ss[1]) >= 2:
                    ret += nums[len(ss) - 1][int(ss[1]) - 2]
                return ret + dfs(ss[1:])
            else:
                return nums[len(ss)][int(ss[0])]

        return ret + dfs(str(a))

if k <= 10:
    print(k)
else:
    nums = [[0] * 10 for _ in range(11)]
    nums[1] = [1] * 10

    for i in range(11):
        for j in range(10):
            if j != 0:
                nums[i][j] += nums[i-1][j-1]
            if j != 9:
                nums[i][j] += nums[i-1][j+1]
            nums[i][j] += nums[i-1][j]

    lo = 0
    hi = 10 ** 10
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if get_below(mid) - k >= 0:
            hi = mid
        else:
            lo = mid

    print(hi)

Submission status: Accepted

Solution code:
K = int(input())

def count(idx, n):
    if idx==0:
        return 1
    if n==0:
        return count(idx-1, 1)+count(idx-1, 0)
    elif n==9:
        return count(idx-1, 9)+count(idx-1, 8)
    else:
        return count(idx-1, n-1)+count(idx-1, n)+count(idx-1, n+1)

lists = []
def count_2(idx, n, list_b):
    lis = list_b[:]
    lis.append(str(n))
    if idx==0:
        lists.append(int(''.join(lis)))
        return 1
    if n==0:
        count_2(idx-1, 1, lis)
        count_2(idx-1, 0, lis)
    elif n==9:
        count_2(idx-1, 9, lis)
        count_2(idx-1, 8, lis)
    else:
        count_2(idx-1, n-1, lis)
        count_2(idx-1, n, lis)
        count_2(idx-1, n+1, lis)

d = 0
now = 0
while 1:
    p = sum([count(d, i) for i in range(1, 10)])
    now += p
    if now>K:
        now -= p
        break
    d += 1

sump = 0
for i in range(1, 10):
    sump_old = sump
    sump += count(d, i)
    if sump+now>=K:
        break
count_2(d, i, [])
lists.sort()
if K<10:
    print(K)
else:
    print(lists[K-now-sump_old-1])

Submission status: Accepted

Solution code:
K=int(input())

D=[0]*12
kt=0

def up(i):
    global kt
    u = 1
    while u:
        kt = max(kt, i)
        D[i] += u
        if D[i] >= 10:
            D[i] = 0
            u = 1
        else: u = 0
        i += 1

def down(i,d):
    for j in range(i, -1, -1):
        if d >= 1: d -= 1
        D[j] = d

for i in range(K):
    up(0)
    j = 0
    while j < kt:
        if abs(D[j] - D[j+1]) > 1:
            if D[j+1] < D[j]: up(j+1)
            D[j] = D[j+1] - 1
            if j > 0: down(j-1, D[j])
        j += 1

f = True
for d in reversed(D):
    if f and d==0: continue
    f = False
    print(d, end='')

Submission status: Accepted

Solution code:
from collections import deque

def generate():
    global que, cnt1, cnt2
    for i in range(cnt2):
        num = que.popleft()
        if 0 < int(num[-1]) < 9:
            for j in range(int(num[-1])-1, int(num[-1])+2, 1):
                que.append(num + str(j))
        elif int(num[-1]) == 0:
            que.append(num + '0')
            que.append(num + '1')
        else:
            que.append(num + '8')
            que.append(num + '9')
    cnt1 = cnt1 + cnt2
    cnt2 = len(que)

K = int(input())
cnt1 = 0
cnt2 = 9
que = deque(['1', '2', '3', '4', '5', '6', '7', '8', '9'])

if K <= 9:
    print(que[K-1])
    exit()

while True:
    generate()
    if K <= cnt1 + cnt2:
        print(que[K - cnt1 - 1])
        exit()

Submission status: Accepted

Solution code:
K = int(input())
global cnt
cnt = 9
def func(cur, d):
    global cnt
    c = cur % 10
    for i in range(0 if c==0 else c-1, 10 if c==9 else c+2):
        if d == 1:
            cnt += 1 
            if cnt == K:
                print(cur*10+i)
                exit()
        else:
            func(cur*10+i, d-1)

if K <= 9:
    print(K)
else:
    for d in range(2, 11):
        for i in range(1, 10):
            func(i, d-1)

Submission status: Accepted

Solution code:
def dp():
    cnt = []
    for i in range(10):
        cnt.append([0] * 10)
    for i in range(10):
        cnt[0][i] = 1
    for i in range(1, 10):
        for j in range(10):
            cnt[i][j] = 0
            for k in range(-1, 2):
                if 0 <= j+k and j+k < 10:
                    cnt[i][j] += cnt[i-1][j+k]
    return cnt


def main():
    k = int(input())
    cnt = dp()
    tot = [0] * 10
    for i in range(10):
        tot[i] = sum(cnt[i][1:])
    # print(*cnt, sep='\n')
    # print(tot)

    res = 0
    length = -1
    digit = -1
    for i in range(10):
        if tot[i] < k:
            k -= tot[i]
        else:
            length = i
            for j in range(1, 10):
                if k > cnt[i][j]:
                    k -= cnt[i][j]
                else:
                    digit = j
                    break
            break

    length -= 1
    res = digit
    while length >= 0:
        # print(length, k, digit, res)
        for i in range(-1, 2):
            # print('#', length, k, digit, digit + i, cnt[length][digit + i])
            if 0 <= digit + i and digit + i <= 9:
                if cnt[length][digit + i] >= k:
                    digit = digit + i
                    break
                else:
                    k -= cnt[length][digit + i]
        length -= 1
        # print(digit)
        res = res * 10 + digit
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
lunluns = []

def dfs(n, cur):
    global lunluns
    lunluns.append(int(n))
    if cur > 8:
        return
    if n[-1] == '0':
        dfs(n+'0', cur+1)
        dfs(n+'1', cur+1)
    elif n[-1] == '9':
        dfs(n+'8', cur+1)
        dfs(n+'9', cur+1)
    else:
        last = int(n[-1])
        dfs(n + str(last-1), cur+1)
        dfs(n + str(last), cur+1)
        dfs(n + str(last+1), cur+1)

for i in range(1,10):
    dfs(str(i), 0)

K = int(input())
lunluns.sort()
print(lunluns[K-1])

Submission status: Accepted

Solution code:
import collections
k = int(input())
que = collections.deque()
cnt = 9
for i in range(1, 10):
    que.append(str(i))
Lun = []
while True:
    if len(Lun) >= 10**5:
        # print(que[-1])
        break
    now = que.popleft()
    Lun.append(now)
    # snow = str(now)
    if now[-1] == '0':
        que.append(now + '0')
        que.append(now + '1')
        cnt += 2
    elif now[-1] == '9':
        que.append(now + '8')
        que.append(now + '9')
        cnt += 2
    else:
        que.append(now + str(int(now[-1]) - 1))
        que.append(now + str(int(now[-1])))
        que.append(now + str(int(now[-1]) + 1))
        cnt += 3

    # print(now)
# print(que)
print(Lun[k-1])

Submission status: Accepted

Solution code:
def main():
    k = int(input())
    dp = [[1] * 10]
    count = 9
    while k > count:
        dp.append([])
        dp[-1].append(dp[-2][0] + dp[-2][1])
        for i in range(1, 9):
            dp[-1].append(dp[-2][i - 1] + dp[-2][i] + dp[-2][i + 1])
        dp[-1].append(dp[-2][8] + dp[-2][9])
        count += sum(dp[-1][1:])
    ans = []
    li = [count - sum(dp[-1][i:]) for i in range(11)]
    for i in range(1, 10):
        if li[i + 1] >= k:
            ans.append(i)
            c = li[i]
            break
    for li in reversed(dp[:-1]):
        for i in range(max(0, ans[-1] - 1), min(9, ans[-1] + 1) + 1):
            if c + li[i] >= k:
                ans.append(i)
                break
            c += li[i]

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


if __name__ == '__main__':
    main()