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
sys.setrecursionlimit(10**6)

k = int(input())
S = []
def dfs(s):
  if len(s)<10:
    for i in range(-1, 2, 1):
      a = str(min(9, max(0, int(s[0])+i)))+s
      S.append(a)
      dfs(a)

for i in range(10):
  S.append(i)
  dfs(str(i))
S = sorted(set([int(s) for s in S]))
print(S[k])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

from collections import deque

def main():
    k = int(input())
    lst = []
    bfs("",k,lst)
    print(lst[k-1])


def bfs(s,k,lst=[]):
    d = deque()
    for c in "0123456789":
        d.append(c)
    while d:
        if len(lst) > k:
            return
        now = d.popleft()
        if now=="0":
            continue
        lst.append(now)
        for nxt in [int(now[-1])-1,int(now[-1]),int(now[-1])+1]:
            if nxt < 0 or nxt > 9:
                continue
            d.append(now+str(nxt))









if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def is_lunlun(num):
    if num < 10:
        return True
    str_num = str(num)
    length = len(str_num)
    for i in range(length - 1):
        left = int(str_num[i])
        right = int(str_num[i + 1])
        # 頭からi+1 桁目とi+2桁目の差がおかしい
        if abs(left - right) > 1:
            if left > right:
                # 下の桁を上げる
                return i + 2
            # 頭の桁を上げて、そこの頭から
            return [i + 1, left + 1]
            
    return True

k = int(input())

i = 1
counta = 0
lunlun = 0
while(True):
    lunlun = is_lunlun(i)
    if lunlun == True:
        counta += 1
        if counta >= k:
            break
        i += 1
    elif type(lunlun) == int:
        length = len(str(i))
        i += 10 ** (length - lunlun)
        continue
    else:
        length = len(str(i))
        div = 10 ** (length - lunlun[0])
        i = math.floor(i / div / 10) * div * 10 + lunlun[1] * div
print(i)

Submission status: Accepted

Solution code:
k = int(input())

ans = 1
cnt = 0
while cnt < k:
    # print(ans, cnt)
    if ans <= 9:
        cnt+=1
        ans+=1
        continue
    li = list(map(int, list(str(ans))))
    flag=1
    for i in range(len(li)-1):
        if abs(li[i]-li[i+1]) > 1:
            ans+=10**(len(li)-i-2)
            flag=0
            break
    if flag:
        cnt+=1
        ans+=1
print(ans-1)

Submission status: Accepted

Solution code:
k = int(input())

def lunlun(a):
    res = []
    for i in a:
        j = int(i[-1])
        if j == 0:
            res += [i + '0', i +'1']
        elif j == 9:
            res += [i + '8', i +'9']
        else:
            res += [i + str(j-1),  i + str(j), i + str(j+1)]
    return res


res = []
a = list(map(str, range(1, 10)))
while len(res) < k:
    if not res:
        tmp = a
    else:
        tmp = lunlun(tmp)
    res.extend(tmp)

print(res[k-1])

Submission status: Accepted

Solution code:
k = int(input())

num = [0] * 10
num[0] = 1
keta = 1
for i in range(k-1):
  change = 0
  for j in range(keta-1):
    if (num[j] < num[j+1]) or (num[j]==num[j+1] and num[j+1]<9):
      num[j] += 1
      change = 1
      for x in range(j, 0, -1):
        num[x-1] = max(0, num[x]-1) 
      break
  if not change:
    if num[keta-1]<9:
      num[keta-1] += 1
      for x in range(keta-1, 0, -1):
        num[x-1] = max(0, num[x]-1) 
    else:
      num[keta-1] = 0
      num[keta] = 1
      for x in range(keta, 0, -1):
          num[x-1] = max(0, num[x]-1) 
      keta += 1
  #print(num)
ans = 0
d = 1
for i in range(10):
  #print(num[i])
  ans += num[i]*d
  d *= 10
  
print(ans)

Submission status: Accepted

Solution code:
def dp(i, j, memo):
    key = "{}.{}".format(i, j)

    if i == 1:
        memo[key] = 1
        return memo[key]

    if key in memo:
        return memo[key]

    if j == 0:
        memo[key] = dp(i-1, j, memo) + dp(i-1, j+1, memo)
        return memo[key]

    if j == 9:
        memo[key] = dp(i-1, j-1, memo) + dp(i-1, j, memo)
        return memo[key]

    memo[key] = dp(i-1, j-1, memo) + dp(i-1, j, memo) + dp(i-1, j+1, memo)
    return memo[key]


k = int(input())
memo = {"1.0": 0}

num = 0

i = 1
j = 0

while(num < k):
    j += 1
    j %= 10
    if j == 0:
        i += 1
    else:
        num += dp(i, j, memo)

p = k - num + dp(i, j, memo)
ans = [j]
for l in range(1, i):
    n = 0
    x = max(-1, ans[-1] - 2)
    while n < p and x < 10:
        x += 1
        n += dp(i-l, x, memo)
    ans.append(x)
    p = p - n + dp(i-l, x, memo)

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

Submission status: Accepted

Solution code:
K = int(input())
Lun_count = 0
if K<=9:
    print(K)
else:
    N=10
    Lun_count = 9
    while(1):
        strN = list(str(N))
        lenN = len(strN)
        for i in range(1,lenN):
            if int(strN[i-1])-int(strN[i]) > 1:
                strN[i]= str(int(strN[i-1])-1)
                N = int(''.join(strN))
                break
            elif int(strN[i-1])-int(strN[i]) < -1:
                strN[i-1] = str(int(strN[i-1])+1)
                strN[i] = '0'
                N = int(''.join(strN))
                break
        else:
            Lun_count +=1
            if Lun_count == K:
                break
            N +=1
    print(N)

Submission status: Accepted

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

b = 9  #個目まで生成済み
runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9] + [0]*150000
hk = 1
keta = 2

def hi(hitoketamae):
    pass

'''
if k<=9:
    print(k)
else:
'''
while b<k:
    """
    if keta == 11:
        for i1 in a[hk]:
            for i2 in a[i1]:
                for i3 in a[i2]:
                    for i4 in a[i3]:
                        for i5 in a[i4]:
                            for i6 in a[i5]:
                                for i7 in a[i6]:
                                    for i8 in a[i7]:
                                        for i9 in a[i8]:
                                            for i10 in a[i9]:
                                                b += 1
                                                runrun[b] = [hk, i1, i2, i3, i4, i5, i6, i7, i8, i9]
        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    """
    if keta == 10:
        for i1 in a[hk]:
            for i2 in a[i1]:
                for i3 in a[i2]:
                    for i4 in a[i3]:
                        for i5 in a[i4]:
                            for i6 in a[i5]:
                                for i7 in a[i6]:
                                    for i8 in a[i7]:
                                        for i9 in a[i8]:
                                            b += 1
                                            runrun[b] = [hk, i1, i2, i3, i4, i5, i6, i7, i8, i9]
        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 9:
        for i1 in a[hk]:
            for i2 in a[i1]:
                for i3 in a[i2]:
                    for i4 in a[i3]:
                        for i5 in a[i4]:
                            for i6 in a[i5]:
                                for i7 in a[i6]:
                                    for i8 in a[i7]:
                                        b += 1
                                        runrun[b] = [hk, i1, i2, i3, i4, i5, i6, i7, i8]
        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 8:
        for i1 in a[hk]:
            for i2 in a[i1]:
                for i3 in a[i2]:
                    for i4 in a[i3]:
                        for i5 in a[i4]:
                            for i6 in a[i5]:
                                for i7 in a[i6]:
                                    b += 1
                                    runrun[b] = [hk, i1, i2, i3, i4, i5, i6, i7]
        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 7:
        for i1 in a[hk]:
            for i2 in a[i1]:
                for i3 in a[i2]:
                    for i4 in a[i3]:
                        for i5 in a[i4]:
                            for i6 in a[i5]:
                                b += 1
                                runrun[b] = [hk, i1, i2, i3, i4, i5, i6]
        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 6:
        for i1 in a[hk]:
            for i2 in a[i1]:
                for i3 in a[i2]:
                    for i4 in a[i3]:
                        for i5 in a[i4]:
                            b += 1
                            runrun[b] = [hk, i1, i2, i3, i4, i5]
        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 5:
        for i in a[hk]:
            for j in a[i]:
                for jj in a[j]:
                    for jjj in a[jj]:
                            b += 1
                            runrun[b] = [hk, i, j, jj, jjj]

        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 4:
        for i in a[hk]:
            for j in a[i]:
                for jj in a[j]:
                    b += 1
                    runrun[b] = [hk, i, j, jj]

        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    if keta == 3:
        for i in a[hk]:
            for j in a[i]:
                b += 1
                #runrun[b] = hk * (10 ** (keta-1)) + i * (10 ** (keta-2)) + j
                runrun[b] = [hk, i, j]

        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
    elif keta == 2:
        for i in a[hk]:
            b += 1
            runrun[b] = [hk, i]

        if hk!=9:
            hk += 1
        else:
            hk = 1
            keta = keta + 1
        
ans = ''


if k<=9:
    ans = int(k)
else:
    for i in runrun[k]:
        ans = ans + str(i)
    ans = int(ans)
print(ans)

Submission status: Accepted

Solution code:
K=int(input())
u12 = [i for i in range(1,10)]
ans = 0
for i in range(K):
    if ans <=11:
        ans += 1
        continue
    flg = True
    l = len(str(ans))
    for j in range(l-1,-1,-1):
        if 0<j<l-1:
            x,y,z = map(int,str(ans)[j-1:j+2])
            if y!=9 and abs(x-(y+1))<=1 and abs((y+1)-z)<=1:
                ans = int(str(ans)[:j]+''.join([str(max(0,y+1-i)) for i in range(l-j)]))
                flg = False
                break
        elif j==0:
            x,y = map(int,str(ans)[:2])
            if x != 9 and abs(x+1-y) <=1:
                ans = int(''.join([str(max(0,x+1-i))for i in range(l)]))
                flg = False
                break
        else:
            x,y = map(int,str(ans)[-2:])
            if y != 9 and abs(x-(y+1))<=1:
                ans += 1
                flg = False
                break
    if flg:
        ans = 10**l
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
K=int(input())

lun=[[] for i in range(10)]

for i in range(10):
    for j in range(10):
        if abs(i-j)<=1:
            lun[i].append(j)

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

for i in range(9):
    lunlun.append([])

for i in range(9):
    for j in range(len(lunlun[i])):
        for k in range(len(lun[lunlun[i][j]%10])):
            lunlun[i+1].append(lunlun[i][j]*10+lun[lunlun[i][j]%10][k])
LUNLUN=[]

for i in range(10):
    LUNLUN.extend(lunlun[i])
LUNLUN.sort

print(LUNLUN[K-1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    L = []
    n1 = [[i + 1] for i in range(9)]
    L.append(n1)
    cnt = 0
    if 1 <= K <= 9:
        print(K)
        exit()
    else:
        cnt += 9

    # 10 ~ 99
    n2 = [[] for _ in range(9)]
    L.append(n2)
    for i in range(9):
        base = 11 * (i + 1)
        if i != 8:
            L[1][i].extend([base - 1, base, base + 1])
        else:
            L[1][i].extend([base - 1, base])
        if K <= cnt + len(L[1][i]):
            print(L[1][i][K - cnt - 1])
            exit()
        else:
            cnt += len(L[1][i])

    k = 2
    while True:
        n = [[] for _ in range(9)]
        L.append(n)
        for i in range(9):
            base = (10 ** k) * (i + 1)
            if i == 0:
                ll = []
                ll += [base, base + 1]
                if k >= 3:
                    for m in range(2, k):
                        ll += [base + j for j in L[m-1][0]]
                ll += [base + j for j in L[k-1][i]]
                ll += [base + j for j in L[k-1][i + 1]]
                L[k][i].extend(ll)
            elif i < 8:
                ll = []
                ll += [base + j for j in L[k-1][i - 1]]
                ll += [base + j for j in L[k-1][i]]
                ll += [base + j for j in L[k-1][i + 1]]
                L[k][i].extend(ll)
            else:
                ll = []
                ll += [base + j for j in L[k-1][i - 1]]
                ll += [base + j for j in L[k-1][i]]
                L[k][i].extend(ll)
            if K <= cnt + len(L[k][i]):
                print(L[k][i][K - cnt - 1])
                exit()
            else:
                cnt += len(L[k][i])
        k += 1


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
X=int(input())
a=[1,2,3,4,5,6,7,8,9]
if 1<=X<=10**5:
    while len(a)<X:
        i=0
        for i in range(X-10):
            if i<len(a):
                c=int(a[i])
                d=10*c
                b=c%10
                b_1=b-1
                b_2=b
                b_3=b+1
                if (b_1>=0)and(b_3<10):
                    a_1=d+b_1
                    a_2=d+b_2
                    a_3=d+b_3
                    a.append(a_1)
                    a.append(a_2)
                    a.append(a_3)
                elif b_1<0:
                    a_2=d+b_2
                    a_3=d+b_3
                    a.append(a_2)
                    a.append(a_3)
                else:
                    a_1=d+b_1
                    a_2=d+b_2
                    a.append(a_1)
                    a.append(a_2)
            i+=1
    a=sorted(a)
    print(a[X-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr  4 21:48:09 2020

@author: Kanaru Sato
"""

k = int(input())

gl = list(map(str,[0,1,2,3,4,5,6,7,8,9]))

starti = 0
endi = len(gl)
l=[]

while len(l) < k:
    ngl = gl[starti:endi]
    for i in range(len(ngl)):
        if ngl[i][0] == "0":
            gl.append("0"+ngl[i])
            gl.append("1"+ngl[i])
        elif ngl[i][0] == "9":
            gl.append("8"+ngl[i])
            gl.append("9"+ngl[i])
        else:
            gl.append(str(int(ngl[i][0])-1)+ngl[i])
            gl.append(str(int(ngl[i][0]))+ngl[i])
            gl.append(str(int(ngl[i][0])+1)+ngl[i])
    starti = endi
    endi = len(gl)
    
    l = []
    for i in gl:
        if i[0] != "0":
            l.append(int(i))

l.sort()
print(l[k-1])

Submission status: Accepted

Solution code:
"""k = int(input())
A = [0] * k

i = 1
r = 0
while r < k:
    if i <= 9:
        A[r] = i
        r = r + 1
    else:
        for j in range(len(str(i)) - 1):
            if not (-1 <= int(str(i)[j]) - int(str(i)[j + 1]) <= 1):
                break
            if j == len(str(i)) - 2:
                A[r] = i
                r = r + 1

    i = i + 1

print(A[k - 1])"""

k = int(input())
A = [1] * k
i = 0
j = 0
treat = [-1, 0, 1]

while i < k:
    if i < 9:
        A[i] = i + 1
        i = i + 1
    else:
        for l in range(3):
            if l == 0 and str(A[j])[-1] == "0":
                continue
            elif l == 2 and str(A[j])[-1] == "9":
                continue
            else:
                A[i] = int(str(A[j]) + str(int(str(A[j])[-1]) + treat[l]))
                i = i + 1

            if i == k:
                break
        j = j + 1

print(A[-1])

Submission status: Accepted

Solution code:
class Tree:
    def __init__(self, num, count, zeroflag, accum):
        self.num = num
        self.count = count
        self.zeroflag = zeroflag
        self.accum = accum.copy()
        self.accum.append(self.num)

        if self.num != 0:
            self.zeroflag = False

        if self.zeroflag == True:
            self.list = list(range(0,10))
        elif self.zeroflag == True and self.count == 10:
            self.list = list(range(0,3))
        else:
            self.list = list(filter(lambda x: 0<=x and x<=9, [num-1,num,num+1]))

        if(count > 0):
            self.nodes = [Tree(elem, count-1,self.zeroflag,self.accum.copy()) for elem in self.list]

    def __repr__(self):
        if(self.count == 0):
            return "Tree: {}".format(self.num)
        else:
            return "Tree: {}<".format(self.num) + str(list(self.nodes))

    def print_accum(self, a):
        if(self.count == 0):
            #print(self.accum)
            a.append(self.accum)
        else:
            for elem in self.nodes:
                elem.print_accum(a)



if __name__ == '__main__':
    #print(Tree(0,2,True,[]))
    K = int(input())
    a = []
    t = Tree(0,9,True,[])
    t.print_accum(a)
    t = Tree(1,9,True,[])
    t.print_accum(a)
    t = Tree(2,9,True,[])
    t.print_accum(a)
    t = Tree(3,9,True,[])
    t.print_accum(a)
    lst = a[K]
    flag = True;
    for i in lst:
        if i != 0:
            flag = False                
        if i == 0 and flag == True:
            print("", end="")
        else:
            print(i, end="")

    print("")

Submission status: Accepted

Solution code:
N=int(input())

list = []

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

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

list = sorted(list)
print(list[N-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
K = int(input())
mapping = defaultdict(list)
for j in range(10):
    mapping[(0, j)].append(str(j))

# iは何桁目かを表す
for i in range(1, 10):
    for j in range(10):
        if j == 0:
            for item in mapping[(i-1, j)]:
                mapping[(i, j)].append( str(j) + item )
            for item in mapping[(i-1, j+1)]:
                mapping[(i, j)].append( str(j) + item )
        elif j == 9:
            for item in mapping[(i-1, j-1)]:
                mapping[(i, j)].append( str(j) + item )
            for item in mapping[(i-1, j)]:
                mapping[(i, j)].append( str(j) + item )
        else:
            for item in mapping[(i-1, j-1)]:
                mapping[(i, j)].append( str(j) + item )
            for item in mapping[(i-1, j)]:
                mapping[(i, j)].append( str(j) + item )
            for item in mapping[(i-1, j+1)]:
                mapping[(i, j)].append( str(j) + str(item) )


ans = set()
for j in range(10):
    for item in mapping[(0, j)]:
        ans.add(int(item))
for i in range(1, 10):
    for j in range(1, 10):
        for item in mapping[(i, j)]:
            ans.add(int(item))
ans = sorted(list(ans))
print(ans[K])

Submission status: Accepted

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

K = int(input())

fueru = [[(x + i - 1) for x in range(3) if 0 <= x + i - 1 <= 9]
         for i in range(10)]

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

last_lst = [i + 1 for i in range(9)]
count = len(last_lst)
for idx in range(10):
    new_lst = []
    for l in last_lst:
        for c in fueru[int(str(l)[-1])]:
            new_lst.append(str(l) + str(c))

    if K <= count + len(new_lst):
        ans = new_lst[K - count - 1]
        print(ans)
        exit()

    count += len(new_lst)
    last_lst = new_lst

Submission status: Accepted

Solution code:
import copy

    
keta=2
lis=[]
for i in range(1,10):
    lis.append(i)

# while count<20**5:
while len(lis)<=10**5:

    que=[]
    for i in range(1,10):
        a=[-1]*keta
        a[0]=i
        que.append(a)
    # ここから先繰り返し
    for k in range(1,keta):
        que_new=[]
        for q in que:
            a,b,c=q[k-1]-1,q[k-1],q[k-1]+1

            if (0<=a) and (9>=a):

                p=copy.copy(q)
                p[k]=a
                que_new.append(p)

            if (0<=b) and (9>=b):
                p=copy.copy(q)
                p[k]=b
                que_new.append(p)
            if (0<=c) and (9>=c):
                p=copy.copy(q)
                p[k]=c
                que_new.append(p)
        que=que_new
    lis+=que
    keta+=1
    
# lis.sort()
ans=lis[int(input())-1]
if type(ans)==int:
    print(ans)
else:
    en=0
    for i in range(len(ans)):
        en+=10**(len(ans)-i-1)*ans[i]
    print(en)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
K = int(input())

MAX = 22
dp = [[0]*10 for _ in [0]*MAX]

for j in range(0, 10):
    dp[1][j] = 1

for i in range(2, MAX):
    for j in range(1, 9):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]
    dp[i][0] = dp[i-1][0] + dp[i-1][1]
    dp[i][9] = dp[i-1][8] + dp[i-1][9]

acc = [[] for _ in [0]*MAX]
for i in range(1, MAX):
    acc[i] = accumulate(dp[i])

# i桁で最大のルンルン数(99...9)は何番目か
num = [0]
for i in range(1, MAX):
    num.append(num[i-1] + sum(dp[i][1:]))


cnt = 0
for i, n in enumerate(num):
    if n < K:
        keta = i+1
        cnt = n
    else:
        break

ans = 0

rg = range(1, 10)
p = 1
for i in range(keta, 0, -1):
    for j in rg:
        if cnt + dp[i][j] < K:
            flg = True
            p = j+1
            cnt += dp[i][j]
        else:
            break

    ans += 10**(i-1)*p

    rg = range(max(0, p-1), min(10, p+2))
    p = max(0, p-1)

print(ans)

Submission status: Accepted

Solution code:
K = int(input())
k =9
i = 10
if K > 9:
    while True:
        # print(i)
        flag = True
        I  = list(map(int,list(str(i))))
        for l in range(len(I)-1):
            if abs(I[l]-I[l+1]) > 1:
                flag = False
                if I[l] < I[l+1]:
                    i = i -i%(10**(len(I)-l-1)) + 10**(len(I)-l-1) -1
                else:
                    i = i -i%(10**(len(I)-l-1)) + (I[l]-1)*10**(len(I)-l-2) -1
                break
        if flag == True:
            k +=1
        
        # print("k = {}".format(k))
        
        if k == K:
            break
        
        i+=1
    print(i)  
else:
    print(K)

Submission status: Accepted

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


def solve(K: int):
    if K <= 12:
        print(K)
        return
    # a = []
    # for i in range(1,10000):
    #     s = str(i)
    #     for j in range(len(s)-1):
    #         if abs(int(s[j])-int(s[j+1]))<=1:
    #             continue
    #         else:
    #             break
    #     else:
    #         a.append(i)
    # print(a)
    # matrix[i][j] = i桁で最上位がjから始まるものの数
    matrix = [[0]*10 for _ in range(11)]

    for i in range(0,10):
        matrix[1][i] = 1

    keta = 2
    SUM = 9
    last = 0
    while True:
        for i in range(10):
            if SUM >= K:
                break

            if i == 0:                
                matrix[keta][i] = matrix[keta-1][0]+matrix[keta-1][1]
            elif i == 9:
                matrix[keta][i] = matrix[keta-1][i-1]+matrix[keta-1][i]
            else:
                matrix[keta][i] = matrix[keta-1][i-1]+matrix[keta-1][i]+matrix[keta-1][i+1]

            if i > 0:
                SUM += matrix[keta][i]
            last = i

        else:
            keta += 1
            continue
        
        break

    answer = str(last)

    while keta > 0:
        i = int(answer[-1])
        SUM -= matrix[keta][i]
        keta -= 1
 
        if i == 0:                
            for j in range(0,2):
                SUM += matrix[keta][j]
                if SUM >= K:
                    answer += str(j)
                    break        
        elif i == 9:
            for j in range(8,10):
                SUM += matrix[keta][j]
                if SUM >= K:
                    answer += str(j)
                    break
        else:
            for j in range(i-1,i+2):
                SUM += matrix[keta][j]
                if SUM >= K:
                    answer += str(j)
                    break
    print(answer)

    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:
import copy
k = int(input())
tmp = [1, 2, 3, 4, 5, 6, 7, 8, 9]
tmp2 = []
if k <= 9:
    print(tmp[k - 1])
    exit()
cnt = 9
while True:
    for t in tmp:
        for i in range(10):
            if abs(int(str(t)[-1]) - i) <= 1:
                tmp2.append(t * 10 + i)
                cnt += 1
                if k == cnt:
                    print(t * 10 + i)
                    exit()
    tmp = copy.copy(tmp2)
    tmp2 = []

Submission status: Accepted

Solution code:
def count_lunlun(num):
    num = list(map(int, str(num)))
    d = len(num)
    dp = [[[[0] * 10 for _ in range(2)] for _ in range(2)] for _ in range(d + 1)]
    dp[0][0][0][0] = 1
    for i in range(d):
        for j in range(2):
            for k in range(10):
                for z in range(2):
                    for x in range(10 if j else (num[i] + 1)):
                        if abs(x - k) <= 1:
                            dp[i + 1][j or x < num[i]][x != 0 or z][x] += dp[i][j][z][k]
                        elif z == 0:
                            dp[i + 1][j or x < num[i]][x != 0 or z][x] += dp[i][j][z][k]
    return sum(dp[d][0][0]) + sum(dp[d][0][1]) + sum(dp[d][1][0]) + sum(dp[d][1][1]) - 1


K = int(input())
left = 0
right = 10 ** 12
while right - left > 1:
    mid = (left + right) // 2
    count = count_lunlun(mid)
    if count >= K:
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

Solution code:
k = int(input())
l = [[0,1]] + [[i,i+1,i+2] for i in range(8)]+[[8,9]]
ln = [i+1 for i in range(9)]
aln = [i+1 for i in range(9)]
for i in range(10):
    tln = []
    for j in ln:
        for m in l[int(str(j)[-1])]:
            tln.append(j*10+m)
    aln += tln
    ln =tln
    if len(aln) >= k:
      break
print(aln[k-1])

Submission status: Accepted

Solution code:
def make_tree(G,keta,count):
    if keta==1:
        num =[]
        for i in range(1,10):
            count+=1
            if count ==k:
                print(i)
                exit()
            else:
                num.append(i)
        G.append(num)
        make_tree(G,2,count)
    else:
        
        num_list = G[keta-2]
        num_lis =[]
        for num in num_list:
            num_str = str(num)
            num_e = int(num_str[-1])
            if num_e == 0:
                count +=1
                if count == k :
                    print(int(num_str + "0"))
                    exit()
                num_lis.append(int((num_str)+"0"))
                count+=1
                if count == k :
                    print(int(num_str + "1"))
                    exit()
                num_lis.append(int((num_str)+"1"))
            elif num_e == 9:
                count +=1
                if count == k :
                    print(int(num_str + "8"))
                    exit()
                num_lis.append(int((num_str)+"8"))
                count+=1
                if count == k :
                    print(int(num_str + "9"))
                    exit()
                num_lis.append(int((num_str)+"9"))
            else:
                count +=1
                if count == k :
                    print(int(num_str + str(num_e-1)))
                    exit()
                num_lis.append(int(num_str + str(num_e-1)))
                count+=1
                if count == k :
                    print(int(num_str + str(num_e)))
                    exit()
                num_lis.append(int(num_str + str(num_e)))
                count+=1
                if count == k :
                    print(int(num_str + str(num_e+1)))
                    exit()
                num_lis.append(int(num_str + str(num_e+1)))
        G.append(num_lis)

        make_tree(G,keta+1,count)


k = int(input())
G=[]
make_tree(G,1,0)

Submission status: Accepted

Solution code:
cnt = 9


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

    numl = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    keta = 1
    dr = [-1, 0, 1]

    def dfs(n, nowk, s):
        if nowk == keta:
            global cnt
            cnt = cnt + 1
            # print(s, cnt, k)
            if cnt == k:
                print(s)
                return True
            else:
                return False


        for d in dr:
            cand = n + d
            if cand == -1 or cand == 10:
                continue
            if dfs(cand, nowk+1, s + str(cand)):
                return True
        return False

    flag = False

    while 1:
        if k < 10:
            print(k)
            break
        keta = keta + 1
        for n in numl:
            # print('1st: ', n)
            if dfs(n, 1, str(n)):
                flag = True
                # print(cnt, 'aaa')
                break
        if flag:
            break




if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import *
N = int(input())
things = []

def giveNext(first, left_n):
    if left_n < 0:
        return
    if first[-1] +1 < 10:
        things.append(first+ [first[-1]+1])
        giveNext(first+ [first[-1]+1],left_n-1)
    if first[-1] -1 > -1:
        things.append(first+ [first[-1]-1])
        giveNext(first+ [first[-1]-1],left_n-1)

    things.append(first+ [first[-1]])
    giveNext(first+ [first[-1]],left_n-1)

for i in range(1, 10):
    giveNext([i], 8)
things = [int("".join(str(y) for y in x)) for x in things]

things += [1,2,3,4,5,6,7,8,9]
things.sort()
print(things[N-1])