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:
import sys
import heapq

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	k = II()
	a = [1,2,3,4,5,6,7,8,9]
	heapq.heapify(a)
	total = 0
	while(total!=k):
		i = heapq.heappop(a)
		total+=1
		li = i%10
		if(li%10==0):
			heapq.heappush(a,i*10+li)
			heapq.heappush(a,i*10+li+1)
		elif(li%10==9):
			heapq.heappush(a,i*10+li-1)
			heapq.heappush(a,i*10+li)
		else:
			heapq.heappush(a,i*10+li-1)
			heapq.heappush(a,i*10+li)
			heapq.heappush(a,i*10+li+1)
	print(i)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
k = int(input())
ans = [-1] * 11
ans[-1] = 1
idx = 1
def add(keta):
    if ans[keta] == -1:
        ans[keta] = 1
    else:
        ans[keta] += 1
        if ans[keta] == 10:
            add(keta - 1)
            ans[keta]=max(0,ans[keta-1]-1)
        elif abs(ans[keta - 1] - ans[keta]) > 1 and ans[keta - 1] != -1:
            add(keta - 1)
            ans[keta] = max(0, ans[keta - 1] - 1)
        
while idx != k:
    idx+=1
    if ans[-2] == -1:
        if ans[-1] == 9:
            ans[-2] = 1
            ans[-1] = 0
        else:
            ans[-1] += 1
        continue
    add(-1)
# print(ans)
ans=[ans[i] for i in range(len(ans)) if ans[i]!=-1]
ans=map(str,ans)
print("".join(ans))

Submission status: Accepted

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
#import time
#start = time.time()

#s = input().split()
#t = [int(p) for p in s]
K = int(input())

#10桁まで生成する
l_1 = [] #1桁を格納するリスト

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

for i in range(1, len(num_list)):
    l_1.append(num_list[i])

#print('l_1:{}'.format(l_1))

def plus_keta(l):
    #前の桁数のリストを受け取って、もう一桁増やしたリストを返す
    list_return = []
    for i in range(len(l)):
        last_number = l[i][-1]
        #print(last_number)
        if(last_number == '0'):
            list_return.append(l[i] + num_list[0])
            list_return.append(l[i] + num_list[1])
        elif(last_number == '9'):
            list_return.append(l[i] + num_list[8])
            list_return.append(l[i] + num_list[9])
        else:
            last_number_index = eval(last_number)
            list_return.append(l[i] + num_list[last_number_index-1])
            list_return.append(l[i] + num_list[last_number_index])
            list_return.append(l[i] + num_list[last_number_index+1])
    return list_return



#plus_keta(l_1)
l_2 = plus_keta(l_1)
#print('l_2:{}'.format(l_2))
l_3 = plus_keta(l_2)
#print('l_3:{}'.format(l_3))
l_4 = plus_keta(l_3)
#print('l_4:{}'.format(l_4))
l_5 = plus_keta(l_4)
#print('l_5:{}'.format(l_5))
l_6 = plus_keta(l_5)
#print('l_6:{}'.format(l_6))
l_7 = plus_keta(l_6)
#print('l_7:{}'.format(l_7))
l_8 = plus_keta(l_7)
#print('l_8:{}'.format(l_8))
l_9 = plus_keta(l_8)
#print('l_9:{}'.format(l_9))
l_10 = plus_keta(l_9)
#print('l_10:{}'.format(l_10))

l = []
l.extend(l_1)
l.extend(l_2)
l.extend(l_3)
l.extend(l_4)
l.extend(l_5)
l.extend(l_6)
l.extend(l_7)
l.extend(l_8)
l.extend(l_9)
l.extend(l_10)
#print(l)
#print(l[100000-1])
print(int(l[K-1]))
#print('time:{}'.format(time.time()-start))

'''
s = ''
for i in range(len(n)):
    s += n[i]
print(s)
print(eval(s) - 3)
''' 
'''
def gen_lun(n):
    #nは桁数
    #nは2以上の整数を入れる（10まで）
    for i in range(1, len(num_list)):
        print(i)
'''

#gen_lun(2)

Submission status: Accepted

Solution code:
def inc(t):
	n=len(t)
	if n==1:
		if t[0] <9:
			t[0]+=1
		else : t=[1,0]
		return t
	if all(t[i]==9 for i in range(n)):
		t = [1]
		t.extend([0]*n)
		return t
	for i in range(n-1,-1,-1):
		if i==0 or t[i]-t[i-1]<1:
			if t[i]<9:
				t[i]+=1
				for j in range(i+1,n):
					t[j] = max(0,t[j-1]-1)
				return t
			
	

k=int(input())
t = [0]

for i in range(k):
	t = inc(t)
print("".join([str(i) for i in t]))

Submission status: Accepted

Solution code:
K=int(input())
A = [[] for j in [0]*(10**5)]
A[0]=[1,2,3,4,5,6,7,8,9]
B=9
C=0
while B<=K:
 for i in range(len(A[C])):
  if A[C][i]%10>0:
   A[C+1].append(A[C][i]*10+(A[C][i]%10)-1)
  A[C+1].append(A[C][i]*10+(A[C][i]%10))
  if A[C][i]%10<9:
   A[C+1].append(A[C][i]*10+(A[C][i]%10)+1)
 B+=len(A[C+1])
 C+=1
print(A[C][len(A[C])-B+K-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

if K <= 9:
    print(str(K))
else:
    tmp = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
    k = 9
    while k < K:
        cur = tmp.popleft()
        ones_place = int(str(cur)[-1])
        if ones_place == 0:
            tmp.append(int(str(cur)+str(0)))
            tmp.append(int(str(cur)+str(1)))
            k += 2
        elif ones_place == 9:
            tmp.append(int(str(cur)+str(8)))
            tmp.append(int(str(cur)+str(9)))
            k += 2
        else:
            tmp.append(int(str(cur)+str(ones_place - 1)))
            tmp.append(int(str(cur)+str(ones_place)))
            tmp.append(int(str(cur)+str(ones_place+1)))
            k += 3

    print(str(tmp[-(k-K)-1]))

Submission status: Accepted

Solution code:
# ABC161d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    def dump(*args):
        sys.stderr.write(str(args))

    k = int(input())

    def isOk(n):
        n = str(n)
        for i in range(len(n)):
            if (i+1 < len(n) and abs(int(n[i]) - int(n[i + 1])) > 1 or i+2 < len(n) and abs(int(n[i + 1]) - int(n[i + 2])) > 1):
                return False
        return True

    def swap(n, i, f):
        ori = n
        ns = str(n)
        try:
            t = ns[-i-1]
            w = ns[-i - 2]
        except:
            s = int(f) + 1
            l = len(ns)
            if s == 10:
                l += 1
            a = ''
            for i in range(s, -1, -1):
                a += str(i)
            a += '0'*(l-len(a))
            return int(a[:l])
        if t == w:
            return swap(n, i+1, f)
        n -= int(t) * 10 ** i
        n -= int(w)*10**(i+1)
        n += int(t) * 10 ** (i + 1)
        n += int(w) * 10 ** (i)
        l = len(ns)
        a = str(n)[:-i-1]
        for i in range(int(a[-1])-1, -1, -1):
            a += str(i)
        a = a[:l]
        a += '0'*(l-len(a))
        n = int(a[:l])
        if not isOk(n):
            return swap(ori, i+1, f)
        return n

    def calc(n, I):
        if isOk(n):
            return n
        n -= 10**I
        n += 10 ** (I + 1)
        a = str(n)[: -I - 1]
        l = len(str(n))
        for i in range(int(a[-1])-1, -1, -1):
            a += str(i)
        a = a[:l]
        a += '0'*(l-len(a))
        n = int(a[:l])
        return calc(n, I+1)

    dp = [0] * (k+1)
    ind = 0
    for i in range(k):
        # if i == 43:
            # print('hi')
        dp[i + 1] = calc(dp[i] + 1, 0)
        # if dp[i] == 123:
        # print('hi')

        # if not isOk(dp[i + 1]):
        #    dp[i + 1] = swap(dp[i], 0, str(dp[i])[0])
        #print(i, dp[i + 1])
        # if i == 990:
        # print('hi')
    print(dp[k])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k=int(input())
l=["1","2","3","4","5","6","7","8","9"]
for i in range(k):
    x=l[i]
    y=int(x[-1])
    if y==0:
        l.append(x+str(y))
        l.append(x+str(y+1))
    elif y==9:
        l.append(x+str(y-1))
        l.append(x+str(y))
    else:
        l.append(x+str(y-1))
        l.append(x+str(y))
        l.append(x+str(y+1))
print(l[k-1])

Submission status: Accepted

Solution code:
K = int(input())

d = [[] for i in range(12)]

for i in range(1, 10):
    d[1].append(i)

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

cur = K - 9

for i in range(2, 12):
    for t in d[i - 1]:
        r = t % 10
        if r == 0:
            d[i].append(t * 10)
            d[i].append(t * 10 + 1)
        elif r == 9:
            d[i].append(t * 10 + 9)
            d[i].append(t * 10 + 8)
        else:
            d[i].append(t * 10 + r - 1)
            d[i].append(t * 10 + r)
            d[i].append(t * 10 + r + 1)

    d[i].sort()

    if cur <= len(d[i]):
        print(d[i][cur - 1])
        exit()

    cur -= len(d[i])

Submission status: Accepted

Solution code:
import math

K = int(input())

def develop_lun(lun):
  lastdigit = lun % 10
  if lastdigit==0:
    return [lun*10+lastdigit, lun*10+lastdigit+1]
  elif lastdigit==9:
    return [lun*10+lastdigit-1, lun*10+lastdigit]
  else:
    return [lun*10+lastdigit-1, lun*10+lastdigit, lun*10+lastdigit+1]

lunlist = [1,2,3,4,5,6,7,8,9]
i = 0
while len(lunlist)<K:
  lunlist.extend(develop_lun(lunlist[i]))
  i+=1

print(lunlist[K-1])

Submission status: Accepted

Solution code:
k = int(input())

def lunlun(x):
    s = str(x)
    good = 0
    for i in range(1, len(s)):
        if abs(int(s[i - 1]) - int(s[i])) > 1:
            # what is the "digit value" of s[i]
            return 10 ** (len(s) - i - 1)
    return good

n = 1
last = 0
total = 0
while total < k:
    skip = lunlun(n)
    if skip == 0:
        last = n
        total += 1
        n += 1
    else:
        n += skip

print(last)

Submission status: Accepted

Solution code:
K = int(input())

if K < 10:
    print(K)
else:
    l, temp1, temp2, i, j = [[1]*10], K, 9, 1, 0
    while temp1 > temp2:
        temp1 -= temp2
        if j == 0:
            l.append([0]*10)
            l[i][j] = l[i-1][0] + l[i-1][1]
            temp2 = 0
            j += 1
        elif j == 9:
            l[i][j] = l[i-1][8] + l[i-1][9]
            temp2 = l[i][j]
            i += 1
            j = 0
        else:
            l[i][j] = l[i-1][j-1] + l[i-1][j] + l[i-1][j+1]
            temp2 = l[i][j]
            j += 1

    ans, p = j - 1, j - 1
    K = temp1
    for k in range(i)[::-1]:
        if p == 0:
            if K > l[k][0]:
                p, K = 1, K - l[k][0]
            else:
                p, K = 0, K
        elif p == 9:
            if K > l[k][8]:
                p, K = 9, K - l[k][8]
            else:
                p, K = 8, K
        else:
            if K > l[k][p-1] + l[k][p]:
                p, K = p+1, K - (l[k][p-1] + l[k][p])
            elif K > l[k][p-1]:
                p, K = p, K - l[k][p-1]
            else:
                p, K = p-1, K
        ans = ans*10 + p

    print(ans)

Submission status: Accepted

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


def construct(lunnum: str, depth: int, flag: bool):
    global l
    if depth == 0:
        l.add(int(lunnum))
        return
    m = int(lunnum[-1])
    for i in range(0, 10) if flag else set([max(0, m - 1), m, min(9, m + 1)]):
        construct(lunnum + str(i), depth - 1, (i == 0) & flag)


construct("0", 10, True)
ls = sorted(list(l))
print(ls[k])

Submission status: Accepted

Solution code:
k = int(input())
l = set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
l1 = [[[] for i in range(10)] for i in range(10)]
for i in range(10):
  l1[0][i].append(i)
for i in range(1, 10):
  for j in range(0, 10):
    if j == 0:
      l1[i][j] = l1[i-1][0] + l1[i-1][1]
    elif j == 1:
      l1[i][j] = l1[i-1][0] + l1[i-1][1] + l1[i-1][2]
    elif j == 2:
      l1[i][j] = l1[i-1][3] + l1[i-1][1] + l1[i-1][2]
    elif j == 3:
      l1[i][j] = l1[i-1][3] + l1[i-1][4] + l1[i-1][2]
    elif j == 4:
      l1[i][j] = l1[i-1][3] + l1[i-1][4] + l1[i-1][5]
    elif j == 5:
      l1[i][j] = l1[i-1][6] + l1[i-1][5] + l1[i-1][4]
    elif j == 6:
      l1[i][j] = l1[i-1][7] + l1[i-1][6] + l1[i-1][5]
    elif j == 7:
      l1[i][j] = l1[i-1][8] + l1[i-1][7] + l1[i-1][6]
    elif j == 8:
      l1[i][j] = l1[i-1][9] + l1[i-1][8] + l1[i-1][7]
    else:
      l1[i][j] = l1[i-1][9] + l1[i-1][8]
    l1[i][j] = [x + j * 10**i for x in l1[i][j]]
    l = l | set(l1[i][j])
l2 = list(l)
l2.sort()
print(l2[k])

Submission status: Accepted

Solution code:
k = int(input())

def forndigit(l1):
    l = []
    for i in l1:
        if i[-1] == '1':
            l.append(i+'0')
            l.append(i+'1')
            l.append(i+'2')
        elif i[-1] == '2':
            l.append(i+'1')
            l.append(i+'2')
            l.append(i+'3')
        elif i[-1] == '3':
            l.append(i+'2')
            l.append(i+'3')
            l.append(i+'4')
        elif i[-1] == '4':
            l.append(i+'3')
            l.append(i+'4')
            l.append(i+'5')
        elif i[-1] == '5':
            l.append(i+'4')
            l.append(i+'5')
            l.append(i+'6')
        elif i[-1] == '6':
            l.append(i+'5')
            l.append(i+'6')
            l.append(i+'7')
        elif i[-1] == '7':
            l.append(i+'6')
            l.append(i+'7')
            l.append(i+'8')
        elif i[-1] == '8':
            l.append(i+'7')
            l.append(i+'8')
            l.append(i+'9')
        elif i[-1] == '9':
            l.append(i+'8')
            l.append(i+'9')
        elif i[-1] == '0':
            l.append(i+'0')
            l.append(i+'1')
    return l

l1 = [str(i) for i in range(1,10)]
r = [l1]
for i in range(2,11):
    r.append(forndigit(r[i-2]))
ans = []
for item in r:
    ans += item
print(ans[k-1])

Submission status: Accepted

Solution code:
d = int(input())

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

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

times = 9

while True:
    tmps = []
    for i in lists:  
        if i % 10 == 0:
            times += 2
            tmps.append(i * 10)
            tmps.append(i * 10 + 1)
        elif i % 10 == 9:
            times += 2
            tmps.append(i * 10 + 8)
            tmps.append(i * 10 + 9)
        else:
            times += 3
            tmps.append(i * 10 + (i % 10 - 1))
            tmps.append(i * 10 + (i % 10))
            tmps.append(i * 10 + (i % 10 + 1))
        
        if times >= d:
            print(tmps[len(tmps) - abs(times - d) - 1])
            exit()
            
    lists = tmps

Submission status: Accepted

Solution code:
code = '9876543210000000000'
def judge(n):
    n = str(n)
    for i in range(len(n)-1):
        ni = int(n[i])
        if abs((ni) - int(n[i+1])) > 1:
            if ni==9:

                return int(n[:i]+code[:len(n)-i])
            else:
                idx = 8 - ni
                return int(n[:i]+code[idx:idx+len(n)-i])
    return -1


i = 1
cnt = 0
k = int(input())
while(1):
    j = judge(i)
    if j==-1:
        cnt += 1

        i+=1
    else:
        i = j
    if cnt == k:
        print(i-1)
        exit()

Submission status: Accepted

Solution code:
K = int(input())
top = 1
cand = [i for i in range(1,10)]

def dfs(s, c):
    global cand
    if c==0:
        cand.append(int(s))
        return
    if s[-1]=='0':
        dfs(s+str(0), c-1)
        dfs(s+str(1), c-1)
    elif s[-1]=='9':
        dfs(s+str(8), c-1)
        dfs(s+str(9), c-1)
    else:
        dfs(s+str(int(s[-1])-1), c-1)
        dfs(s+str(int(s[-1])), c-1)
        dfs(s+str(int(s[-1])+1), c-1)
        
flag = False
while True:
    for i in range(1,10):
        if len(cand)>1e5:
            flag = True
            break
        dfs(str(i) ,top)
    if flag:
        break
    top+=1
print(cand[K-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
ans = []

def dfs(i):
    if 10 < len(i):
        return

    ans.append(int(i))
    if 0 < int(i[-1]):
        dfs(i + chr(ord(i[-1]) - 1))
    if int(i[-1]) < 9:
        dfs(i + chr(ord(i[-1]) + 1))
    dfs(i + i[-1])


K = int(input())
for i in range(1, 10):
    dfs(str(i))
ans.sort()
#print(ans.sort())
# print(ans)
print(ans[K-1])

Submission status: Accepted

Solution code:
import collections 
  
q = collections.deque([]) 
f=0
l = []
for i in range(1,10):
    q.append(str(i))
    
#print(q)
while f<100003:
    s = q[0]
    l.append(s)
    if int(s[-1])>0:
        q.append(s+str((int(s[-1])-1+10)%10))
    q.append(s+s[-1])
    if int(s[-1])<9:
        q.append(s+str((int(s[-1])+1)%10))
    q.popleft()
    f+=2

for i in q:
    l.append(i)

#print(l[:50])
n = int(input())
print(l[n-1])

Submission status: Accepted

Solution code:
# coding:utf-8

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

runrun_list = [n for n in range(10)]
idx = 1
cnt = 9

while True:
    prefix_str = str(runrun_list[idx])
    prefix = int(prefix_str) * 10
    add_idx = int(prefix_str[-1])

    if add_idx == 0:
        start = 0
        stop = 2
    elif add_idx == 9:
        start = 8
        stop = 10
    else:
        start = add_idx - 1
        stop = (add_idx - 1) + 3

    for n in range(start, stop):
        runrun_list.append(prefix + n)
        cnt += 1
        if cnt == K:
            print(runrun_list[-1])
            exit(0)
    idx += 1

Submission status: Accepted

Solution code:
k = int(input())
dp = [0] * 100000
count = 0
result = []

def u(n, r, now):
    global count
    if r < 0 or r > 9:
        return 0
    if n == 1 and r == 0:
        return 0
    if n == 1 and r >= 1 and r <= 9: # Match!
        count += 1
        result.append(int(now))
        return 1
    return u(n - 1, r - 1, str(r - 1) + now) + u(n - 1, r, str(r) + now) + u(n - 1, r + 1, str(r + 1) + now)

def a(n):
    result = 0
    for i in range(10):
        result += u(n, i, str(i))
    return result

for i in range(1, 11):
    a(i)

result.sort()
print(result[k - 1])
'''
for i in range(1, 1000):
    print(result[i - 1])
'''

Submission status: Accepted

Solution code:
def givenewluns(string):
    if string[-1] == '0':
        return [string + '0', string + '1']
    elif string[-1] == '9':
        return [string + '8', string + '9']
    else:
        return [string + str(int(string[-1])-1), string + string[-1], string + str(int(string[-1])+1)]

luns = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
counter = 0

K = int(input())

while(counter + len(luns) < K):
    counter += len(luns)
    newluns = []
    for l in luns:
        newluns += givenewluns(l)
    luns = newluns

print(luns[K - counter - 1])

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
d = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
if k <= 9:
    print(k)
else:
    cnt = 9
    while cnt < k:
        p = d.popleft()
        pstr = str(p)
        pstr_last = int(pstr[-1])
        
        if pstr_last - 1 >= 0:
            ad = int(pstr + str(pstr_last - 1))
            d.append(ad)
            cnt += 1
        if cnt == k:
            break
            
        ad = int(pstr + str(pstr_last))
        d.append(ad)
        cnt += 1
        if cnt == k:
            break
            
        if pstr_last + 1 <= 9:
            ad = int(pstr + str(pstr_last + 1))
            d.append(ad)
            cnt += 1
        if cnt == k:
            break
            
    print(ad)

Submission status: Accepted

Solution code:
K = int(input())

#nはstr型で入力
def f(n):
    global l
    if len(n) == 11:
        return 
    else:
        l.append(int(n))
        n_last = int(n[-1])
        n1, n2, n3 = n_last-1, n_last, n_last+1
        if n_last == 0:
            f(n+str(n2))
            f(n+str(n3))
        elif n_last == 9:
            f(n+str(n1))
            f(n+str(n2))
        else:
            f(n+str(n1))
            f(n+str(n2))
            f(n+str(n3))
            


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

for j in range(10):
    f(str(j))
ll = sorted(list(set(l)))
print(ll[K])

Submission status: Accepted

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

k = int(input())

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


def lunlun(s):
    a = int(s[-1])
    if a == 0:
        l = [0,1]
    
    elif a == 9:
        l = [8,9]
    
    else:
        l = [a-1,a,a+1]
    
    ret = []
    for i in l:
        ret.append(s+str(i))
        
    return ret

n_2 = []
for i in a:
    temp = lunlun(i)
    for i in temp:
        n_2.append(i)
 
n_3 = []
for i in n_2:
    temp = lunlun(i)
    for i in temp:
        n_3.append(i)

n_4 = []
for i in n_3:
    temp = lunlun(i)
    for i in temp:
        n_4.append(i)

n_5 = []
for i in n_4:
    temp = lunlun(i)
    for i in temp:
        n_5.append(i)

n_6 = []
for i in n_5:
    temp = lunlun(i)
    for i in temp:
        n_6.append(i)

n_7 = []
for i in n_6:
    temp = lunlun(i)
    for i in temp:
        n_7.append(i)

n_8 = []
for i in n_7:
    temp = lunlun(i)
    for i in temp:
        n_8.append(i)

n_9 = []
for i in n_8:
    temp = lunlun(i)
    for i in temp:
        n_9.append(i)

n_10 = []
for i in n_9:
    temp = lunlun(i)
    for i in temp:
        n_10.append(i)


a.extend(n_2)
a.extend(n_3)
a.extend(n_4)
a.extend(n_5)
a.extend(n_6)
a.extend(n_7)
a.extend(n_8)
a.extend(n_9)
a.extend(n_10)

print(str(a[k-1]))

Submission status: Accepted

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

k = int(input())

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

k -= 9

a = [['00', '01'], ['10', '11', '12'], ['21', '22', '23'], ['32', '33', '34'], ['43', '44', '45'], ['54', '55', '56'], ['65', '66', '67'], ['76', '77', '78'], ['87', '88', '89'], ['98', '99']]

for i in range(1, 10):
    if k <= len(a[i]):
        print(a[i][k - 1])
        sys.exit()
    else:
        k -= len(a[i])

while True:
    a_ = [[] for _ in range(10)]
    for i in range(10):
        n = str(i)
        for j in range(i - 1, i + 2):
            if j < 0:
                continue
            if j > 9:
                continue
            for k_ in a[j]:
                a_[i].append(n + k_)
    a = a_
    #print(a)
    for i in range(1, 10):
        if k <= len(a[i]):
            print(a[i][k - 1])
            sys.exit()
        else:
            k -= len(a[i])

Submission status: Accepted

Solution code:
k = int(input())

def next(s):
	n = len(s)
	ind_to_check = n-1
	while ind_to_check != 0 and s[ind_to_check] == 9 or s[ind_to_check] - s[ind_to_check-1] == 1:
		ind_to_check -= 1

	if ind_to_check == 0 and s[ind_to_check] == 9:
		s = [1] + [0]*n
	else:
		s[ind_to_check] += 1
		for j in range(ind_to_check+1, n):
			s[j] = max(0, s[j-1] - 1)

	return s


s = [1]
for i in range(k-1):
	# print(s)
	s = next(s)

print("".join([str(item) for item in s]))

Submission status: Accepted

Solution code:
K=int(input())

dp = [[0]*11 for _ in [0]*11]
dp[1] = [1]*10 + [0]

for i in range(2,11):
    dp[i][0] = dp[i-1][1] + dp[i-1][0]
    for j in range(1,10):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]

S = 0
breakFlg = False
for d in range(1,11):
    for n in range(1,10):
        S += dp[d][n]
        if S>=K:
            breakFlg = True
            S -= dp[d][n]
            break
    if breakFlg: break

memo = dict()
def get(d,n):
    if (d,n) in memo:
        return memo[(d,n)]
    if d==1:
        memo[(d,n)] = [n]
        return [n]
    ret = []
    if n>0:
        for a in get(d-1,n-1):
            ret.append(a+n*(10**(d-1)))
    for a in get(d-1,n):
        ret.append(a+n*(10**(d-1)))
    if n<9:
        for a in get(d-1,n+1):
            ret.append(a+n*(10**(d-1)))
    memo[(d,n)] = ret
    return ret

ans = get(d,n)[K-S-1]
print(ans)

Submission status: Accepted

Solution code:
k=input()

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

# print ln
# print ln[9]
print ln[k-1]

Submission status: Accepted

Solution code:
k = int(input())
from queue import Queue

queue = Queue()
for i in range(1, 10):
    queue.put(i)

n = 0
while n < k:
    i = queue.get()
    n += 1
    j = i % 10
    if j == 0:
        queue.put(i*10)
        queue.put(i*10+1)
    elif j == 9:
        queue.put(i*10+8)
        queue.put(i*10+9)
    else:
        queue.put(i*10+j-1)
        queue.put(i*10+j)
        queue.put(i*10+j+1)

print(i)

Submission status: Accepted

Solution code:
K = int(input())

import collections

run_list = collections.defaultdict(list)
run_list[1] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range(2, 11):
    for j in run_list[i-1]:
        if 0 <= int(str(j)[0]) + 1 < 10:
            run_list[i].append(str(int(str(j)[0]) + 1)+str(j))
        if 0 <= int(str(j)[0]) - 1 < 10:
            run_list[i].append(str(int(str(j)[0]) - 1)+str(j))
        if 0 <= int(str(j)[0]) < 10:
            run_list[i].append(str(int(str(j)[0]))+str(j))
# print(sorted(run_list[3]))
all_list = []
for v in run_list.values():
    for vv in v:
        all_list.append(int(vv))
print(sorted(list(set(all_list)))[K])

Submission status: Accepted

Solution code:
K = int(input())

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

while K > len(res):
  newR = []
  for e in res:
    m = e % 10
    if m == 9:
      newR.extend([e * 10 + 8, e * 10 + 9])
    elif m == 0:
      newR.extend([e * 10, e * 10 + 1])
    else:
      newR.extend([e * 10 + m - 1, e * 10 + m, e * 10 + m + 1])
  K -= len(res)
  #print(res)
  res = newR

#print(res)

print(res[K - 1])

Submission status: Accepted

Solution code:
import numpy as np
k = int(input()) - 1
if len(str(k)) == 1:
    print(k + 1)
else:

    jjj = 0
    ans = [0]

    num = 0
    dps = []
    dp = [1] * 10
    dp[0] = 0

    flag = False
    for i in range(len(dp)):
        num += dp[i]
        if num > k:
            flag = True
            break

    dp[0] = 1
    dps.append(dp)

    flag = False
    while True:
        dp = [0] * 10
        dp[0] = 0
        for i in range(1, 9):
            dp[i] = sum(dps[-1][i - 1 : i + 2])
        dp[9] = dps[-1][8] + dps[-1][9]


        for i in range(len(dp)):
            num += dp[i]
            if num > k:
                flag = True
            if flag:
                num -= dp[i]
                break
        if flag:
            break
        dp[0] = dps[-1][0] + dps[-1][1]
        dps.append(dp)

    ans = [i]
    k = k - num
    jjj += 1

#     print(k)
    try:
        while True:
#             print(k)
            num = 0
            ii = i
            for i in range(max([ii - 1, 0]), ii + 2):
            #     print(i)
                if num + dps[-1][i]> k:
                    break
                else:
                    num += dps[-1][i]

            ans.append(i)
            k -= num
            dps = dps[:-1]
#             print(k)
            if k == 0 and len(dps) > 0:
                aaa = i - 1
                while True:    
                    if aaa < 0 :
                        aaa = 0
                    ans += [aaa]
                    aaa -= 1
                    dps = dps[:-1]
                    if len(dps) == 0:
                        break
                aaaaaa
    except:
        print("".join(map(str, ans)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# D - Lunlun Number
# 標準入力の取得
K = int(input())

# 求解
def get_lunlun_number_list(ln_list:list) -> list:
    lunlun_number_list = []
    for ln in ln_list:
        one_place_value = ln % 10
        lunlun_number_list.append(int(str(ln) + str(one_place_value)))
        if one_place_value != 0:
            lunlun_number_list.append(int(str(ln) + str(one_place_value-1)))
        if one_place_value != 9:
            lunlun_number_list.append(int(str(ln) + str(one_place_value+1)))

    return lunlun_number_list

lunlun_number_list = []

lunlun_number_list1 = list(range(1, 10))
lunlun_number_list.extend(lunlun_number_list1)
lunlun_number_list2 = get_lunlun_number_list(lunlun_number_list1)
lunlun_number_list.extend(lunlun_number_list2)
lunlun_number_list3 = get_lunlun_number_list(lunlun_number_list2)
lunlun_number_list.extend(lunlun_number_list3)
lunlun_number_list4 = get_lunlun_number_list(lunlun_number_list3)
lunlun_number_list.extend(lunlun_number_list4)
lunlun_number_list5 = get_lunlun_number_list(lunlun_number_list4)
lunlun_number_list.extend(lunlun_number_list5)
lunlun_number_list6 = get_lunlun_number_list(lunlun_number_list5)
lunlun_number_list.extend(lunlun_number_list6)
lunlun_number_list7 = get_lunlun_number_list(lunlun_number_list6)
lunlun_number_list.extend(lunlun_number_list7)
lunlun_number_list8 = get_lunlun_number_list(lunlun_number_list7)
lunlun_number_list.extend(lunlun_number_list8)
lunlun_number_list9 = get_lunlun_number_list(lunlun_number_list8)
lunlun_number_list.extend(lunlun_number_list9)
lunlun_number_list10 = get_lunlun_number_list(lunlun_number_list9)
lunlun_number_list.extend(lunlun_number_list10)

lunlun_number_list = sorted(lunlun_number_list)

# 結果出力
print(lunlun_number_list[K-1])

Submission status: Accepted

Solution code:
def func(S,x):
    for i in range(x,len(S)):
        if S[i-1] == "0":
            S[i] = "0"
        else:
            S[i] = chr(ord(S[i-1])-1)
    return S

K = int(input())
X = 0


for _ in range(K):
    X += 1
    S = list(str(X))

    i = len(S)-1
    while S[i] == '0':
        i -= 1
    S = func(S,i+1)
    d = len(S)
    for i in range(len(S)-1,0,-1):
        if ord(S[i]) - ord(S[i-1]) > 1:
            S[i-1] = chr(ord(S[i-1])+1)
            d = i
    X = int("".join(func(S,d)))

print(X)