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

ans = [[] for _ in range(10)]
ans[0] = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]

for i in range(9):
    for num in ans[i]:
        if num[-1] == "0":
            ans[i + 1].append(num + "0")
            ans[i + 1].append(num + "1")
        elif num[-1] == "1":
            ans[i + 1].append(num + "0")
            ans[i + 1].append(num + "1")
            ans[i + 1].append(num + "2")
        elif num[-1] == "2":
            ans[i + 1].append(num + "1")
            ans[i + 1].append(num + "2")
            ans[i + 1].append(num + "3")
        elif num[-1] == "3":
            ans[i + 1].append(num + "2")
            ans[i + 1].append(num + "3")
            ans[i + 1].append(num + "4")
        elif num[-1] == "4":
            ans[i + 1].append(num + "3")
            ans[i + 1].append(num + "4")
            ans[i + 1].append(num + "5")
        elif num[-1] == "5":
            ans[i + 1].append(num + "4")
            ans[i + 1].append(num + "5")
            ans[i + 1].append(num + "6")
        elif num[-1] == "6":
            ans[i + 1].append(num + "5")
            ans[i + 1].append(num + "6")
            ans[i + 1].append(num + "7")
        elif num[-1] == "7":
            ans[i + 1].append(num + "6")
            ans[i + 1].append(num + "7")
            ans[i + 1].append(num + "8")
        elif num[-1] == "8":
            ans[i + 1].append(num + "7")
            ans[i + 1].append(num + "8")
            ans[i + 1].append(num + "9")
        elif num[-1] == "9":
            ans[i + 1].append(num + "8")
            ans[i + 1].append(num + "9")

for j in range(10):
    l = len(ans[j])
    if k <= l:
        print(ans[j][k - 1])
        break
    elif k > l:
        k -= l

Submission status: Accepted

Solution code:
import heapq
K=int(input())
if K<10:
  print(K)
  exit()
  
nums=[1, 2, 3, 4, 5, 6, 7, 8, 9]
heapq.heapify(nums)
for i in range(K):
  value=heapq.heappop(nums)
  tmp=str(value)
  if tmp[-1]=='0':
    cand=[int(tmp+'0'), int(tmp+'1')]
  elif tmp[-1]=='9':
    cand=[int(tmp+'8'), int(tmp+'9')]
  else:
    h=int(tmp[-1])
    cand=[int(tmp+str(h-1)), int(tmp+str(h)), int(tmp+str(h+1))]
  for c in cand:
    heapq.heappush(nums, c)
print(value)

Submission status: Accepted

Solution code:
from collections import deque

d = deque([(0, i) for i in range(1, 10)])
K = int(input())
cnt = 0

while len(d) > 0:
    s, i = d.popleft()
    # print(d)

    cnt += 1
    ns = 10*s + i
    # print(ns)
    if cnt == K:
        print(10*s + i)
        break

    l = max(0, i-1)
    r = min(10, i+2)
    for i in range(l, r):
        d.append((ns, i))

Submission status: Accepted

Solution code:
def is_ll(n):
    cur = n % 10
    while n > 10:
        n //= 10
        if abs(n % 10 - cur) > 1:
            return False
        cur = n % 10
    return True

def find_next_ll(n):
    o = n
    cur = n % 10
    while n > 10:
        n //= 10
        if -1 < n % 10 - cur < 2 and cur != 9:
            n *= 10
            n += cur
            break
        cur = n % 10
    n += 1
    while n < o:
        cur = n % 10
        n *= 10
        n += max(0, cur - 1)
    return n

K = int(input())

ll = 1
for i in range(1, K):
    n = ll + 1
    if not is_ll(n):
        ll = find_next_ll(ll)
    else:
        ll = n
print(ll)

Submission status: Accepted

Solution code:
import copy
k=int(input())
l=[1,2,3,4,5,6,7,8,9]
h=1
s=0
s1=0
A=[]
C=[1]
D=[]
while len(l)<k:
    s1=len(l)
    for i in range(0,len(A)):
        l.append(A[i]+10**h)
        D.append(A[i]+10**h)
    A.extend(C)
    C=copy.deepcopy(D)
    D=[]
    for i in range(s,s1):
        j=str(l[i])
        an=int(j[0])
        if an==1:
            l.append((10**h)+l[i])
            l.append(2*(10**h)+l[i])
            C.append((10**h)+l[i])
        elif an==9:
            l.append(9*(10**h)+l[i])
            l.append(8*(10**h)+l[i])
        elif an==2:
            l.append((10**h)+l[i])
            l.append((2)*(10**h)+l[i])
            l.append((3)*(10**h)+l[i])
            C.append((10**h)+l[i])
        else:
            l.append(an*(10**h)+l[i])
            l.append((an+1)*(10**h)+l[i])
            l.append((an-1)*(10**h)+l[i])
    l.append(10**h)
    C.append(10**h)
    h=h+1
    s=s1
B=l[s:]
B.sort()
print(B[k-s-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def is_runrun(n):
    str_n = str(n)
    for i, s in enumerate(str_n):
        if i < len(str_n) - 1:
            if abs(int(s) - int(str_n[i + 1])) > 1:
                return False

    return True


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

    i = 0
    keta = 1
    created = {}
    count = 0
    while True:
        before_runruns = created.get(keta - 1, [])
        now_runruns = created.get(keta, [])

        if keta == 1:
            now_runruns.append(str(i))

            if str(i) != "0":
                count += 1
                if count == k:
                    return str(i)

        for runrun in before_runruns:
            if abs(int(str(runrun)[0]) - i) <= 1:
                now_runruns.append(str(i) + str(runrun))

                if str(i) != "0":
                    count += 1
                    if count == k:
                        return str(i) + str(runrun)

        created[keta] = now_runruns

        if i == 9:
            keta += 1
            i = 0
        else:
            i += 1


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return helper


@memoize
def f(d, k):
    if d == 1:
        return 1

    s = f(d-1, k)

    if k > 0:
        s += f(d-1, k-1)

    if k < 9:
        s += f(d-1, k+1)

    return s


def g1(K):
    d = 1
    cnt = 0

    while True:
        for i in range(1, 10):
            cnt2 = f(d, i)
            if (cnt + cnt2 >= K):
                return (cnt, d, i)

            cnt += cnt2

        d += 1


def g2(K, cnt, d, k):
    d -= 1
    X = [k]

    while d > 0:
        for j in range(-1, 2):
            if k+j < 0 or k+j > 9:
                continue

            cnt2 = f(d, k+j)

            if (cnt + cnt2 >= K):
                X.append(k+j)
                k = k+j
                break

            cnt += cnt2

        d -= 1

    return X

K = int(input())
cnt, d, k = g1(K)
print(''.join(map(str, g2(K, cnt , d, k))))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

k = int(input())

ans = list(range(1, 10))
d = 10
prev = ['0'] + list(map(str, ans))
while len(ans) <= k:
    _next = []
    for v in prev:
        if v[0] == '0':
            _next.append('0' + v)
            _next.append('1' + v)
            ans.append(int('1' + v))
            continue
        if v[0] == '1':
            _next.append('0' + v)
            _next.append('1' + v)
            ans.append(int('1' + v))
            _next.append('2' + v)
            ans.append(int('2' + v))
            continue
        if v[0] == '9':
            _next.append('8' + v)
            ans.append(int('8' + v))
            _next.append('9' + v)
            ans.append(int('9' + v))
            continue
        i = int(v[0])
        s1 = str(i - 1)
        s2 = str(i)
        s3 = str(i + 1)
        _next.append(s1 + v)
        ans.append(int(s1 + v))
        _next.append(s2 + v)
        ans.append(int(s2 + v))
        _next.append(s3 + v)
        ans.append(int(s3 + v))
    prev = _next

print(sorted(ans)[k-1])

Submission status: Accepted

Solution code:
K = int(input())
ans = []
R = [[] for _ in range(11)]
for i in range(1,10):
  R[0].append(i)
for i in range(1,11):
  R[i] = [10**i]
  if i > 1:
    for j in range(i-1):
      for r in R[i-2-j]:
        d = r//(10**(i-2-j))
        if d <= 1:
          R[i].append(10**i+r)
  for r in R[i-1]:
    d = r//(10**(i-1))
    for j in [-1,0,1]:
      if 1<= d+j <= 9:
        R[i].append((d+j)*(10**i)+r)
A = []
#print(sorted(R[0]))
#print(sorted(R[1]))
#print(sorted(R[2]))
#print(sorted(R[3]))
#print(sorted(R[4]))
#print(sorted(R[10]))
for i in range(11):
  for r in R[i]:
    A.append(r)
A.sort()
#print(len(A))
print(A[K-1])

Submission status: Accepted

Solution code:
def add(N):
    n = N % 10
    ret = N * 10
    if n == 0:
        return [ret, ret + 1]
    elif n == 9:
        return [ret + 9,ret + 8]
    else:
        return [ret + n - 1, ret + n, ret + n + 1]

X = int(input())
l = [1,2,3,4,5,6,7,8,9]
lists = list()
lists.append(l)
n = 9
while n < X:
    list_ = lists[-1]
    templist = list()
    for l_ in list_:
        vals = add(l_)
        n += len(vals)
        templist.extend(vals)
    lists.append(templist)

R = list()
for list_ in lists:
    R.extend(list_)
R.sort()
print(R[X-1])

Submission status: Accepted

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

left = 0
right = 9

while len(lst) < k:
  for i in range(left, right + 1):
    if lst[i] % 10 > 0:
      lst.append(lst[i] * 10 + lst[i] % 10 - 1)
    lst.append(lst[i] * 10 + lst[i] % 10)
    if lst[i] % 10 < 9:
      lst.append(lst[i] * 10 + lst[i] % 10 + 1)
  left = right + 1
  right = len(lst) - 1

print(lst[k - 1])

Submission status: Accepted

Solution code:
k = int(input())
if k < 11:
    print(k)
else:
    s = [None] * 20
    target = k
    target -= 10
    s[1] = 1
    for i in range(target):
        # print(s[::-1])
        for j in range(20):
            if s[j] is None:
                s[j] = 0
            # print("add try j=",j, "s[j]",s[j], "->", s[j] + 1)
            s[j] += 1  # その桁を足す

            if s[j] > 9:  # もし10になったら
                # print("reach 10")
                s[j] = 0
                continue  # 続ける

            if j != 0:
                # print(" j!=1")
                for k in range(j, -1, -1):
                    if s[k] == 0:
                        s[k - 1] = 0
                    else:
                        s[k - 1] = s[k] - 1

            if s[j + 1] != None and abs(s[j] - s[j + 1]) > 1:
                # print(" over")
                continue
            # print(" pass")
            break
    #print(s)
    res = ""
    for i in range(20):
        if s[i] != None:
            res = str(s[i]) + res
        else:
            break
    print(int(res))

Submission status: Accepted

Solution code:
K = int(input())
now = 0
if K < 10:
    result = K
else:
    tmp_list = []
    for i in range(1, 10):
        tmp_list.append(i)
    now = 9
    while now != K:
        next_list = []
        for i in range(len(tmp_list)):
            fig = tmp_list[i] % 10
            if fig != 0:
                next_list.append(tmp_list[i] * 10 + fig - 1)
                now += 1
                if now == K:
                    break
            next_list.append(tmp_list[i] * 10 + fig)
            now += 1
            if now == K:
                break

            if fig != 9:
                next_list.append(tmp_list[i] * 10 + fig + 1)
                now += 1
                if now == K:
                    break
        tmp_list = next_list

if K > 10:
    result = tmp_list[-1]

print(result)

Submission status: Accepted

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

def next_lunlun(x):
    K = len(x)
    if len(x) == 1:
        return str(int(x) + 1)
    elif x[-1] == '9':
        next =  next_lunlun(x[:-1])
        if int(next[-1]) - 1 >= 0:
            return next + str(int(next[-1]) - 1)
        else:
            return next + '0'
    elif x[-2] >= x[-1]:
        return x[:-1] + str(int(x[-1]) + 1)
    else:
        next = next_lunlun(x[:-1])
        if int(next[-1]) - 1 >= 0:
            return next + str(int(next[-1]) - 1)
        else:
            return next + '0'


def solve(K: int):
    x = '0'
    for k in range(K):
        x = next_lunlun(x)
    print(x)
    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()

Submission status: Accepted

Solution code:
def aaa(val):
    val = int(val)
    if val == 0:
        return [0, 1]
    if val == 1:
        return [0, 1, 2]
    if val == 2:
        return [1, 2, 3]
    if val == 3:
        return [2, 3, 4]
    if val == 4:
        return [3, 4, 5]
    if val == 5:
        return [4, 5, 6]
    if val == 6:
        return [5, 6, 7]
    if val == 7:
        return [6, 7, 8]
    if val == 8:
        return [7, 8, 9]
    if val == 9:
        return [8, 9]
        
l = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range(100000):
    # print(aaa(0))
    # print(str(l[i])[-1])
    ll = aaa(str(l[i])[-1])
    for a in ll:
        l.append(int(str(l[i]) + str(a)))
    if len(l) > 100000:
        break
        
# print(l)
k = int(input())
print(l[k - 1])

Submission status: Accepted

Solution code:
#[int(i) for i in input().split()]
"""
1,2,3,4,5,6,7,8,9,10,11,12,21,22,23,32,33,34...100,101,110,111,112,121,122,123,210,211,212,321,322,323,332,333,334,343,
"""

"""
最大の位
1のとき、100とか120とかある
9のとき、987,989,998,999
...狭い
"""
import time
t = time.time();
k = int(input())
if k <= 9:
    print(k)
else:
    ls = []
    ls_str = ["0","1","2","3","4","5","6","7","8","9"]
    ls.append(ls_str)
    #累積和
    len_ls = [9]
    dic = {"0":["0","1"],"9":["8","9"]}

    for i in range(1,9):
        dic[str(i)] = [str(i-1),str(i),str(i+1)]
    for i in range(9):
        ls_tmp = []
        ls_former = ls[-1]
        for j in range(len(ls_former)):
            for l in dic[ls_former[j][0]]:
                ls_tmp.append(l+ls_former[j])
        ls.append(sorted(ls_tmp))
    ls_ans = []
    for i in range(len(ls)):
        ls_ans.append([j for j in ls[i] if j[0] != "0"])

    for i in range(1,len(ls_ans)):
        len_ls.append(len_ls[-1] + len(ls_ans[i]))

    for i in range(len(len_ls)):
        if i != 0 and len_ls[i] >= k:
            k -= (len_ls[i-1]+1)
            break

    #print(k)
    #print(i)
    print(ls_ans[i][k])
    #print(ls_ans[i][:20])

    #print(time.time()-t)

Submission status: Accepted

Solution code:
k = int(input())
if k < 10:
	print(k)
else:
	dp = [[0 for _ in range(10)] for _ in range(30)] #確認
	for i in range(10):
		dp[1][i] = 1
	for i in range(2, 30):
		for j in range(10):
			if j == 0:
				dp[i][j] = dp[i-1][j] + dp[i-1][j+1]
			elif j == 9:
				dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
			else:
				dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j-1]

	#print(dp)
	cnt = 0
	for i in range(1, 30):
		for j in range(1, 10):
			cnt += dp[i][j]
			#print(cnt)
			if cnt >= k:
				keta = i
				num = j
				break
		else:
			continue
		break

	left = k - cnt + dp[keta][num]


	ans = [num]
	while keta != 1:
		if num == 0:
			li = [0, 1]
		elif num == 9:
			li = [-1, 0]
		else:
			li = [-1, 0, 1]
		for i in li:
			#print(li, i)
			if left > dp[keta-1][num+i]:
				left -= dp[keta-1][num+i]
			else:
				num += i
				ans.append(num)
				keta -= 1
				break
	ansl = []
	for i in range(len(ans)):
		ansl.append(str(ans[i]))
	anss = ''.join(ansl)
	print(anss)

Submission status: Accepted

Solution code:
K = int(input())
ln = [["0"]]
ln.append([str(i) for i in range(1,10)])
for i in range(1,10):
  tmp = []
  for j in ln[i]:
    for k in range(-1,2):
      if int(j[-1])+k >=0 and int(j[-1])+k<10:
        tmp.append(j+str(int(j[-1])+k))
  ln.append(tmp) 
ln = sum(ln,[])
print(ln[K])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

K=int(input())
c=9
cb=0
r_list=[1,2,3,4,5,6,7,8,9]
while(c<K):
    tmp=[]
    for i in r_list:
        if(i%10==0):
            tmp.append(i*10)
            tmp.append(i*10+1)
        elif(i%10==9):
            tmp.append(i*10+8)
            tmp.append(i*10+9)
        else:
            tmp.append(i*10+i%10-1)
            tmp.append(i*10+i%10)
            tmp.append(i*10+i%10+1)
    cb=c
    r_list=tmp
    c+=len(r_list)

    
r_list.sort()
ans=r_list[K-cb-1]
print(ans)

Submission status: Accepted

Solution code:
import json
k = int(input())
# 1
# 2
# 3
# 10

# assume_valid
# list of num ??
def next_lunlun(k):
    k[0] += 1
    for i in range(len(k) - 1):
        if k[i] < 10:
            break
        k[i] -= 10
        k[i+1] += 1

    if k[-1] >= 10:
        k[-1] -= 10
        k.append(1)

    for i in range(len(k)-1, 0, -1):
        if abs(k[i] - k[i-1]) <= 1:
            continue
        elif k[i] > k[i-1]:
            k[i-1] = k[i] - 1
            for j in range(i-2, -1, -1):
                k[j] = max(k[j + 1] - 1, 0)
            break
        else:
            pivot = len(k) - 1
            for j in range(i, len(k) - 1):
                if k[j + 1] > k[j] or (k[j] < 9 and k[j+1] == k[j]):
                    pivot = j
                    break
            if pivot == len(k) - 1 and k[-1] == 9:
                for j in range(len(k)):
                    k[j] = 0
                k.append(1)
            else:
                k[pivot] += 1
                for j in range(pivot-1, -1, -1):
                    k[j] = max(k[j+1] -1 , 0)
            break

    return k

i = [0]
for idx in range(k):
    next_lunlun(i)
base = 0
for num in reversed(i):
    base *= 10
    base += num
print(base)

Submission status: Accepted

Solution code:
def inputs(): return [int(x) for x in input().split()]
def bfs(s):
    if len(s)==cnt1:
        return s
    a = s[-1]
    if a=="0":
        A = ["0","1"]
    elif a=="9":
        A = ["8","9"]
    else:
        A=[str(int(a)-1),a,str(int(a)+1)]
    for i in A:
        if bfs(s+i)!=None:
            ans.append(bfs(s+i))
ans=["1","2","3","4","5","6","7","8","9"]
n = int(input())
cnt1 = 2
while len(ans)<n:
    for i in ans:
        if len(i)==cnt1-1:
            bfs(i)
    cnt1+=1
ans = list(map(int,ans))
ans.sort()
#print(ans)
print(ans[n-1])

Submission status: Accepted

Solution code:
# coding: utf-8
k = int(input())
"""
1,2,3 ... ,9
           10, 11, 12,  21, 22, 23,  ...  98, 99,
100, 101, 110,111,112, 121,122,123
          210,211,212, 221,222,223, 232,233,234
          
...
                                            987,988,989, 998,999
"""
"""
a = ['1','2','3','4','5','6','7','8','9'] # 3*3

b = [] # 3*3*3-1
for i in range(8):
    b += [str(i+1)+str(i), str(i+1)+str(i+1), str(i+1)+str(i+2)]
i = 8
b_ [str(i+1)+str(i), str(i+1)+str(i+1)]
"""
li = []

li_ = []
for i in range(9):
    li_.append(str(i+1))
li += li_

keta = 10
#keta = 4

for t in range(keta-1): #t=0 : 2keta
    li_x = []
    for v in li_:
        i = int(v[-1])
            
        
        if i != 0:
            li_x.append(v+str(i-1))
        li_x.append(v+str(i))
        if i+1 < 10:
            li_x.append(v+str(i+1))
            
    li += li_x
    li_ = li_x
    
    #print(li)
    #print(li_)
    #print(li_x)
    
li = list(map(int, li))
li.sort()
#print(li)
print(li[k-1])

Submission status: Accepted

Solution code:
dic = {}
def rec(d, pre, acc):
    if d == 1:
        if 1 <= pre <= 8:
            return [acc+c for c in map(str, [pre-1, pre, pre+1])]
        elif pre == 9:
            return [acc+c for c in ["8", "9"]]
        else:
            return [acc+c for c in ["0", "1"]]
    ans = []
    for x in range(max(0,pre-1), min(pre+2, 10)):
        ans += rec(d-1, x, acc+str(x))
    return ans
K = int(input())
ls = [1,2,3,4,5,6,7,8,9]
d = 2
while len(ls) < K:
    for i in range(1,10):
        ls += rec(d-1, i, str(i))
    d+=1
print(ls[K-1])

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial
from fractions import gcd
import sys
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10**9+7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


K = ii()

runrun = deque()
runrunAll = []
new = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
runrun.append(new)
runrunAll.extend(new)
for i in range(1, 10):
    before = runrun[i-1]
    new = deque()
    for b in before:
        head = b[0]
        ihead = int(head)
        if head == '0':
            new.append(str(ihead) + b)
            new.append(str(ihead+1) + b)
        elif head == '9':
            new.append(str(ihead-1) + b)
            new.append(str(ihead) + b)
        else:
            new.append(str(ihead-1) + b)
            new.append(str(ihead) + b)
            new.append(str(ihead+1) + b)
    runrun.append(new)
    runrunAll.extend(new)

runrunAll = [int(r) for r in runrunAll]
runrunAll = sorted(set(runrunAll))
print(runrunAll[K])

Submission status: Accepted

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

def next_lunlun(x):
    K = len(x)
    if len(x) == 1:
        return str(int(x) + 1)
    if x[-1] == '9':
        next =  next_lunlun(x[:-1])
        if int(next[-1]) - 1 >= 0:
            return next + str(int(next[-1]) - 1)
        else:
            return next + '0'

    if x[-2] >= x[-1]:
        return x[:-1] + str(int(x[-1]) + 1)
    else:
        next = next_lunlun(x[:-1])
        if int(next[-1]) - 1 >= 0:
            return next + str(int(next[-1]) - 1)
        else:
            return next + '0'


def solve(K: int):
    x = '0'
    for k in range(K):
        x = next_lunlun(x)
    print(x)
    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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque


def solve(K: int):
    G = []
    m = {
        '0': [0, 1],
        '1': [0, 1, 2],
        '2': [1, 2, 3],
        '3': [2, 3, 4],
        '4': [3, 4, 5],
        '5': [4, 5, 6],
        '6': [5, 6, 7],
        '7': [6, 7, 8],
        '8': [7, 8, 9],
        '9': [8, 9],
    }
    q = deque([])
    for i in list(range(1, 10)):
        q.appendleft(i)
    while(len(G) <= 100000):
        v = str(q.pop())
        G.append(v)
        for nv in m[v[-1]]:
            q.appendleft(v + str(nv)) 
    print(G[K-1])
    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()

Submission status: Accepted

Solution code:
def pat(K,count,keta,num):
    #print(str(num)+":"+str(count)+":"+str(keta))
    if count == -1:
        return -1
    elif keta == 1:
        if count == K-1:
            print(num)
            return count + 1
        else:
            return (count+1)

    else:
        if (int(num[-1])) -1 >= 0:
            count = pat(K,count,keta-1,num+str(int(num[-1])-1))
        count = pat(K,count,keta-1,num+num[-1])
        if (int(num[-1])+1) <= 9:
            count = pat(K,count,keta-1,num+str(int(num[-1])+1))
    if count >=K:
        return -1
    else:
        return count
K = int(input())
count = 0
ans = list()
keta = 0

while True:
    keta += 1
    for i in range(1,10):
        count = pat(K,count,keta,str(i))
        #print(count)
        if count  == -1:
            break
    if count == -1:
        break

Submission status: Accepted

Solution code:
list=[]
for a in range(1,10):
 list.append(a)
 for b in range(a-(a>0),a+(a<9)+1):
  list.append(a*10+b) 
  for c in range(b-(b>0),b+(b<9)+1):
   list.append(a*100+b*10+c)
   for d in range(c-(c>0),c+(c<9)+1):
    list.append(a*1000+b*100+c*10+d)
    for e in range(d-(d>0),d+(d<9)+1):
     list.append(a*10000+b*1000+c*100+d*10+e)
     for f in range(e-(e>0),e+(e<9)+1):
      list.append(a*100000+b*10000+c*1000+d*100+e*10+f)
      for g in range(f-(f>0),f+(f<9)+1):
       list.append(a*1000000+b*100000+c*10000+d*1000+e*100+f*10+g)
       for h in range(g-(g>0),g+(g<9)+1):
        list.append(a*10000000+b*1000000+c*100000+d*10000+e*1000+f*100+g*10+h)
        for i in range(h-(h>0),h+(h<9)+1):
         list.append(a*100000000+b*10000000+c*1000000+d*100000+e*10000+f*1000+g*100+h*10+i)
         for j in range(i-(i>0),i+(i<9)+1):
          list.append(a*1000000000+b*100000000+c*10000000+d*1000000+e*100000+f*10000+g*1000+h*100+i*10+j)

list.sort()
x=int(input())
print(list[x-1])

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def dil(i):
    if 1<=i<=8:
        return [i-1,i,i+1]
    if i==0:
        return [0,1]
    if i==9:
        return [8,9]

K = I()

#dp[i][j][k]:i桁，スタートj,ラストk
dp = [[[0]*10 for _ in range(10)] for _ in range(12)]
for i in range(10):
    dp[1][i][i] = 1

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

#dp2[i][j]: i桁，スタートjのルンルン数の総数
dp2 = [[0]*10 for _ in range(12)]
for i in range(12):
    for j in range(10):
        dp2[i][j] = sum(dp[i][j])

i = 1
aa = 0
while 1:
    if aa+sum(dp2[i][1:]) >= K:
        L = i
        break
    aa += sum(dp2[i][1:])
    i += 1

for i in range(L):
    K -= sum(dp2[i][1:])

temp = 0
now = 0
ans = ''
dl = [i for i in range(1,10)]
for l in range(L):
    last_j = dl[0]
    for j in dl:
        if temp+now+dp2[L-l][j]>=K:
            break
        else:
            now += dp2[L-l][j]
            last_j = j+1
    ans += str(last_j)
    temp = temp+now
    now = 0
    dl = dil(last_j)

print(int(ans))

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(200000)


def read():
    K = int(input())
    return K,


def dfs(i, d, s, q):
    if i == 1:
        q.append(s + str(d))
        return
    if d >= 1:
        dfs(i-1, d-1, s+str(d), q)
    dfs(i-1, d, s+str(d), q)
    if d < 9:
        dfs(i-1, d+1, s+str(d), q)


def solve(K):
    q = deque()
    for i in range(1, 11):
        for d in range(1, 10):
            dfs(i, d, "", q)
    return q[K-1]
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Accepted

Solution code:
X = [1, 2, 3, 4, 5, 6, 7, 8, 9]
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(9):
    B = []
    for a in A:
        r = a % 10
        if r > 0:
            B.append(10*a+r-1)
        if r < 9:
            B.append(10*a+r+1)
        B.append(10*a+r)
    X = X+B
    A = B
X.sort()
k = int(input())
print(X[k-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
que = deque()
runrun = []

for i in range(1,10):
    que.append(i)

def abs01(n):
    if n == 0:
        return [0,1]
    elif n == 9:
        return [8,9]
    else:
        return [n-1,n,n+1]

while True:
    n = que.popleft()
    n_simo1 = int(str(n)[-1])
    nums = abs01(n_simo1)
    for num in nums:
        que.append(n*10+num)
    runrun.append(n)
    if len(runrun) == K:
        print(runrun[-1])
        #print(runrun)
        #print(que)
        exit()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

K = int(input())

NL = {}

def nextLunlun(n):
    if n in NL:
        return NL[n]
    if n < 9:
        ans = n + 1
    else:
        k = n + 1
        sk = str(k)
        a = int(sk[-2])
        b = int(sk[-1])
        if b == 0 or b - a > 1:
            l = nextLunlun(n // 10)
            l1 = l % 10
            if l1 == 0:
                ans = l * 10
            else:
                ans = l * 10 + l1 - 1
        else:
            ans = k
    NL[n] = ans
    return ans

def lunlun(n):
    if n < 10:
        ans = n
    else:
        ans = 10
        for i in range(n-10):
            ans = nextLunlun(ans)
    return ans

print(lunlun(K))

Submission status: Accepted

Solution code:
k = int(input())
cnt = 9
q = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]

if k <= cnt:
    print(q[k-1])

while True:
    if cnt >= k:
        break
    num = q.pop(0)
    list_num = list(num)
    a = int(list_num[-1])
    for i in range(10):
        if abs(a-i) < 2:
            cnt += 1
            if i == 0:
                q.append(num+"0")
            elif i == 1:
                q.append(num +"1")
            elif i == 2:
                q.append(num +"2")
            elif i == 3:
                q.append(num+"3")
            elif i == 4:
                q.append(num+"4")
            elif i == 5:
                q.append(num+"5")
            elif i == 6:
                q.append(num+"6")
            elif i == 7:
                q.append(num+"7")
            elif i == 8:
                q.append(num+"8")
            elif i == 9:
                q.append(num+"9")

if k > 9:
    print(q[k-cnt-1])