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

def is_lunlun(x):
    x_str = str(x)
    for i in range(len(x_str)-1):
        if abs(int(x_str[i]) - int(x_str[i+1])) > 1:
            return False
    return True

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

    lunlun_map = {
        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]
    }

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

    count = 9
    all_lunluns = [list(range(1, 10))]
    i = 0
    while True:
        for lunlun in all_lunluns[i]:
            least = int(str(lunlun)[-1])
            lunluns = []
            for j in lunlun_map[least]:
                new_lunlun = int(str(lunlun) + str(j))
                lunluns.append(new_lunlun)
                count += 1
                if count == k:
                    print(new_lunlun)
                    sys.exit(0)
            all_lunluns.append(lunluns)
        i += 1

if __name__ == "__main__":
    main()

Submission status: Accepted

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

@author: ctiuser
"""
import sys

K = int(input())

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

M = [0,[1,1,1,1,1,1,1,1,1,1]]
s = 9
while K > s:    
    m = [0 for _ in range(10)]
    for i in range(10):
        if i == 0:
            m[i] += M[-1][i] + M[-1][i+1]
        elif i == 9:
            m[i] += M[-1][i-1] + M[-1][i]
        else:
            m[i] += M[-1][i-1] + M[-1][i] + M[-1][i+1]
    M.append(m)
    s += sum(m[1:])
s -= sum(m[1:])
keta = len(M) - 1
ans = ''

i = 0
while K > s:
    i += 1
    s += M[keta][i]

s -= M[keta][i]
ans += str(i)
keta -= 1
d = K - s
#print(ans)
#print(i, d)
while keta > 0:
    if i == 0:
        d -= M[keta][i]
        if d <= 0:
            i = i
            ans += str(i)
            d += M[keta][i]            
        else:
            d -= M[keta][i+1]
            if d <= 0:
                i = i+1
                ans += str(i)
                d += M[keta][i]
    elif i == 9:
        d -= M[keta][i-1]
        if d <= 0:
            i = i-1
            ans += str(i)
            d += M[keta][i]
        else:
            d -= M[keta][i]
            if d <= 0:
                i = i
                ans += str(i)
                d += M[keta][i]
    else:
        d -= M[keta][i-1]
        if d <= 0:
            i = i-1
            ans += str(i)
            d += M[keta][i]
        else:
            d -= M[keta][i]
            if d <= 0:
                i = i
                ans += str(i)
                d += M[keta][i]
            else:
                d -= M[keta][i+1]
                if d <= 0:
                    i = i+1
                    ans += str(i)
                    d += M[keta][i]
        
        
    keta -= 1
#    print(ans)
#    print(i,d)


print(ans)

Submission status: Accepted

Solution code:
k = int(input())
lun = [str(e) for e in list(range(10))]
num = [str(e) for e in list(range(10))]
preindex = 1
index = 10
count = 10
while count <= 100003:
    for i in range(preindex,index):
        if int(lun[i][-1]) !=0:
            lun.append(lun[i]+num[int(lun[i][-1])-1])
            count +=1
        lun.append(lun[i] +num[int(lun[i][-1])])
        count +=1
        if int(lun[i][-1]) !=9:
            lun.append(lun[i]+num[int(lun[i][-1])+1])
            count+=1
    preindex = index
    index = count
print(lun[k])

Submission status: Accepted

Solution code:
K = int(input())


dp = [[1 for _ in range(10)]]
dp
s = [[sum(dp[0][1:i + 1]) for i in range(1, 10)]]
ends = s[0][8]

for j in range(10 * 5):
    dp.append([dp[j][0] + dp[j][1]] + [dp[j][i - 1] + dp[j][i] + dp[j][i + 1]
                                       for i in range(1, 9)] + [dp[j][8] + dp[j][9]])
    s.append([ends + sum(dp[j + 1][1:i + 1]) for i in range(1, 10)])
    ends = s[j + 1][8]
    if ends > 10**5:
        break


def search(jj, ii, m):
    if jj == 0:
        return ii
    else:
        if ii != 0:
            if m <= dp[jj - 1][ii - 1]:
                return (ii) * 10**jj + search(jj - 1, ii - 1, m)
            elif m <= dp[jj - 1][ii - 1] + dp[jj - 1][ii]:
                return (ii) * 10**jj + search(jj - 1, ii, m - dp[jj - 1][ii - 1])
            else:
                return (ii) * 10**jj + search(jj - 1, ii + 1, m - dp[jj - 1][ii - 1] - dp[jj - 1][ii])
        else:
            if m <=  dp[jj - 1][ii]:
                return (ii) * 10**jj + search(jj - 1, ii, m)
            else:
                return (ii) * 10**jj + search(jj - 1, ii + 1, m - dp[jj - 1][ii])


for j in range((len(s))):
    if s[j][8] >= K:
        jj = j
        break
for i in range(9):
    if s[jj][i] >= K:
        ii = i + 1
        if ii > 1:
            m = K - s[jj][i - 1]  # 該当するところの文字で始まる何番目の数かを取得
        else:
            m = K - s[jj - 1][8]
        break

print(search(jj, ii, m))

Submission status: Accepted

Solution code:
n=int(input())
now=[1,2,3,4,5,6,7,8,9]
if n<10:
  print(now[n-1])
  exit()
cnt=9
while True:
  next=[]
  for s in now:
    s=str(s)
    if s[-1]!="0":
      cnt+=1
      if cnt<n:
        next.append(s+str(int(s[-1])-1))
      else:
        print(s+str(int(s[-1])-1))
        exit()
    cnt+=1
    if cnt<n:
      next.append(s+s[-1])
    else:
      print(s+s[-1])
      exit()
    if s[-1]!="9":
      cnt+=1
      if cnt<n:
        next.append(s+str(int(s[-1])+1))
      else:
        print(s+str(int(s[-1])+1))
        exit()
  now=next

Submission status: Accepted

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

DP = [[0] * 10 for _ in range(11)]

for i in range(10):
    DP[1][i] = 1

for j in range(2, 11):
    for i in range(10):
        if i == 0:
            DP[j][i] = DP[j-1][0] + DP[j-1][1]
        elif i == 9:
            DP[j][i] = DP[j-1][8] + DP[j-1][9]
        else:
            DP[j][i] = DP[j-1][i-1] + DP[j-1][i] + DP[j-1][i+1]

total = 0

ans = []

# j桁目がk


def dfs(j, k):
    global ans
    global total
    if j == 0:
        print(int("".join(ans)))
        sys.exit(0)

    if k == 0:
        kList = [0, 1]
    elif k == 9:
        kList = [8, 9]
    else:
        kList = [k-1, k, k+1]

    for i in kList:
        if total + DP[j][i] >= K:
            ans.append(str(i))
            dfs(j-1, i)
        else:
            total += DP[j][i]


for j in range(1, 11):
    for i in range(1, 10):
        if total + DP[j][i] >= K:
            ans.append(str(i))
            dfs(j-1, i)
        else:
            total += DP[j][i]

Submission status: Accepted

Solution code:
n=int(input())
ans=[]
def dfs(num,step,tmp):
    if len(ans)>1e5:
        return
    if num==step:
        ans.append(tmp)
        return
    if step==0:
        for i in range(1,10):
            dfs(num,step+1,tmp*10+i)
    else:
        if tmp%10!=0:
            dfs(num,step+1,tmp*10+tmp%10-1)
        dfs(num,step+1,tmp*10+tmp%10)
        if tmp%10!=9:
            dfs(num,step+1,tmp*10+tmp%10+1)
for i in range(11):
    dfs(i+1,0,0)
print(ans[n-1])

Submission status: Accepted

Solution code:
k = int(input())

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

if k <= 12 :
    print(k)
else :
    for i in range(10) :
        b = []
        for s in a[i] :
            if s[-1] == '0' :
                b.append(s+'0')
                b.append(s+'1')
            elif s[-1] == '9' :
                b.append(s+'8')
                b.append(s+'9')
            else :
                b.append(s+str(int(s[-1])-1))
                b.append(s+str(int(s[-1])))
                b.append(s+str(int(s[-1])+1))

            if c + len(b) > k :
                print(b[k-c-len(b)-1])
                break
    
        if c + len(b) > k :
            break
    
        a.append(b)
        c += len(b)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    k = int(input())
    d = deque([0])

    while 1:
        a = d.popleft()
        if a==0:
            for i in range(1, 10):
                d.append(i)
                k -= 1
                if k==0:
                    print(i)
                    exit()
        else:
            b = a%10
            if b==0:
                d.append(a*10+b)
                k -= 1
                if k == 0:
                    print(a*10+b)
                    exit()
                d.append(a*10+(b+1))
                k -= 1
                if k == 0:
                    print(a*10+(b+1))
                    exit()
            elif b==9:
                d.append(a*10+(b-1))
                k -= 1
                if k == 0:
                    print(a*10+(b-1))
                    exit()
                d.append(a*10+b)
                k -= 1
                if k == 0:
                    print(a*10+b)
                    exit()
            else:
                d.append(a*10+(b-1))
                k -= 1
                if k == 0:
                    print(a*10+(b-1))
                    exit()
                d.append(a*10+b)
                k -= 1
                if k == 0:
                    print(a*10+b)
                    exit()
                d.append(a*10+(b+1))
                k -= 1
                if k == 0:
                    print(a*10+(b+1))
                    exit()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K = int(input())

ans = 9

def countup(before):
  global ans
  global K
  next_arr = []
  for s in before:
    for diff in range(-1, 2):
      next_num = int(s[-1]) + diff
      if(0 <= next_num and next_num <= 9):
        next_arr.append(s + str(next_num))
        ans += 1
        if(ans == K):
          print(s + str(next_num))
          exit()
  return next_arr


if(K < 10):
  print(K)
  exit()
hoge = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
for _ in range(100):
  hoge = countup(hoge)

Submission status: Accepted

Solution code:
import copy
n = int(input())
ans = [1,2,3,4,5,6,7,8,9]
stock = ["1","2","3","4","5","6","7","8","9"]
stock2 = []
a = 2
def d(x):
    if x == 0:
        return(["0","1"])
    elif x == 9:
        return(["8","9"])
    else:
        return([str(x-1),str(x),str(x+1)])
if n > 9:
    while True:
        if len(ans) > n-1:
            print(ans[n-1])
            break
        for i in stock:
            s = ""
            x = d(int(i[-1]))
            #print(x,i)
            for j in x:
                s = i+j
                ans.append(int(float(s)))
                stock2.append(s)
        stock = copy.deepcopy(stock2)
        stock2 = []
else:
    print(ans[n-1])

Submission status: Accepted

Solution code:
k = int(input())
a = [100]*15
a[0] = 1


def runrun_generater(x):
    for i in range(14):
        if(x[i]+1 - x[i+1] < 2 and (x[i] < 9 or x[i] == 100)):
            if(x[i] == 100):
                x[i] = 1
                if(i != 0):
                    x[:i] = [0]*i
            else:
                x[i] += 1
                if(i != 0):
                    k = i
                    for xx in range(i):
                        if(x[k] == 0):
                            x[k-1] = 0
                        else:
                            x[k-1] = x[k]-1
                        k -= 1
            return x


for i in range(k-1):
    a = runrun_generater(a)
ans = 0
keta = 1
for y in a:
    if(y != 100):
        ans += y * keta
        keta *= 10
print(ans)

Submission status: Accepted

Solution code:
K = int(input())
def runrun(num,keta):
    num_str = str(num)
    result = True
    for i in range(keta-1):
        if abs(int(num_str[i]) - int(num_str[i+1])) > 1:
            result = False
            break
    return result
def next_runrun(n):
    if str(n) == "9"*(len(str(n))):
        return n+1
    keta = len(str(n))
    while keta >= 0:
        tmp = n + 10**(len(str(n))-keta)
        if runrun(tmp,keta):
            break
        else:
            keta -= 1
    tmp_str = str(tmp)[0:keta] + "x"*(len(str(n))-keta)
    tmp_array = []
    for t in tmp_str:
        tmp_array.append(t)
    for i in range(len(tmp_array)-1):
        if tmp_array[i+1] == "x":
            j = int(tmp_array[i]) - 1
            j = j if j >= 0 else 0
            tmp_array[i+1] = str(j)
    
    return int(''.join(tmp_array))
cnt = 1
n = 1
while True:
    if cnt == K:
        break
    else:
        n = next_runrun(n)
        cnt += 1
print(n)

Submission status: Accepted

Solution code:
k=int(input())

alllist=[0,1,2,3,4,5,6,7,8,9]
maelist=[0,1,2,3,4,5,6,7,8,9]
tobilist=[]

for i in range(9):
    atolist=[]
    for j in maelist:
        sentou = j // (10**(i))
        jousuu = 10**(i+1)
        if sentou == 1:
            atolist.append(1 * jousuu + j)
            atolist.append(2 * jousuu + j)
            tobilist.append(j)
        elif sentou == 9:
            atolist.append(8*jousuu+j)
            atolist.append(9*jousuu+j)
        elif sentou == 0:
            atolist.append(jousuu + j)
            tobilist.append(j)
        else:
            atolist.append((sentou - 1)*jousuu+j)
            atolist.append(sentou*jousuu+j)
            atolist.append((sentou + 1)*jousuu+j)

    alllist.extend(atolist)
    maelist=[]
    for l in atolist:
        maelist.append(l)
    maelist.extend(tobilist)

kusolist=list(set(alllist))
kusolist.sort()
print(kusolist[k])

Submission status: Accepted

Solution code:
# coding: utf-8


# n_run = 0
# ans = -1


def rec(x, digit, K):
    # global n_run, ans
    global candidates

    # if ans > 0:
    #     return None
    # # print(x)
    # if len(str(x)) > digit:
    #     return None
    
    if len(str(x)) == digit:
        candidates.append(x)
        return None
        # n_run += 1

    # if n_run == K:
    #     # print(x)
    #     ans = x
    #     # print(type(x))
    #     # input()
    #     return x
        
    tail = int(str(x)[-1])
    if tail == 0:
        rec(10*x + 0, digit, K)
        rec(10*x + 1, digit, K)
    elif tail == 9:
        rec(10*x + 8, digit, K)
        rec(10*x + 9, digit, K)
    else:
        rec(10*x + tail-1, digit, K)
        rec(10*x + tail, digit, K)
        rec(10*x + tail+1, digit, K)


def main():
    global candidates

    K = int(input())

    # def rec(x, digit):
    #     if len(str(x)) > digit:
    #         return None
            
    #     global n_run

    #     if len(str(x)) == digit:
    #         n_run += 1

    #     if n_run == K:
    #         return x

    #     tail = int(str(x)[0])
    #     if tail == 0:
    #         rec(10*x + 0)
    #         rec(10*x + 1)
    #     elif tail == 9:
    #         rec(10*x + 8)
    #         rec(10*x + 9)
    #     else:
    #         rec(10*x + tail-1)
    #         rec(10*x + tail)
    #         rec(10*x + tail+1)

    n_run = 0
    n_digit = 1
    while True:  # 桁数についてのループ
        candidates = []
        for x in range(1, 10):
            rec(x, n_digit, K)
            
            # if ans > 0:
            #     return ans
            # print("BBB")
        if n_run + len(candidates) >= K:
            return candidates[K-n_run-1]
        
        n_run += len(candidates)
        n_digit += 1
        # print("CCC")
    # print("DDD")


print(main())

Submission status: Accepted

Solution code:
K=int(input())
def run(K):
	run=[1,2,3,4,5,6,7,8,9]
	run2=[1,2,3,4,5,6,7,8,9]
	while len(run)<K:
		run3=[]
		for i in run2:
			st=str(i)
			for j in range(10):
				if abs(int(st[-1])-j)<=1:
					run.append(int(10*i+j))
					run3.append(int(10*i+j))
		run2=run3
	return run
ans=run(K)
print(ans[K-1])

Submission status: Accepted

Solution code:
k = int(input())

counter = 0
num_object = [i for i in range(1,10)]

ketaflag_min = 0
ketaflag_max = len(num_object)
index = 1
if k <= 10:
    print(k)

else:
    while True:
        # print(ketaflag_min,ketaflag_max)
        for i in range(ketaflag_min,ketaflag_max):
            last_keta = num_object[i] % 10
            # print(i, num_object[i])
            if last_keta != 9 and last_keta != 0:
                max_keta = last_keta + 1
                min_keta = last_keta - 1
                newnum_max =  num_object[i] * 10 + max_keta
                newnum_mid =  num_object[i] * 10 + last_keta
                newnum_min =  num_object[i] * 10 + min_keta
                num_object.append(min(newnum_max,newnum_min))
                num_object.append(newnum_mid)
                num_object.append(max(newnum_max,newnum_min))
            elif last_keta == 9:
                newnum_min = num_object[i] * 10 + 8
                newnum_mid = num_object[i] * 10 + 9
                num_object.append(newnum_min)
                num_object.append(newnum_mid)
            else:
                newnum_min = num_object[i] * 10 + 0
                newnum_mid = num_object[i] * 10 + 1
                num_object.append(newnum_min)
                num_object.append(newnum_mid)
            if len(num_object) >= k:
                print(num_object[k-1])
                exit()
        ketaflag_min = ketaflag_max
        ketaflag_max = len(num_object)
        # print(num_object)

Submission status: Accepted

Solution code:
import collections, math

local = False
if local:
    file = open("inputt.txt", "r")

def inp():
    if local:
        return file.readline().rstrip()
    else:
        return input().rstrip()

def ints():
    return [int(_) for _ in inp().split()]



K = int(inp())

nex = [[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]]
globcount = 0

def dfs(curdepth, curval):
    if curdepth<0:
        return False
    
    if curdepth==0:
        global globcount
        globcount += 1

        if globcount==K:
            print(curval)
            return True

    nexarr = nex[int(curval[-1])]
    for j in range(len(nexarr)):
        if dfs(curdepth-1, curval+str(nexarr[j])):
            return True
    
    return False


for depth in range(1, 15):
    found = False
    for i in range(1, 10):
        if dfs(depth-1, str(i)):
            found = True
            break
    
    if found:
        break

Submission status: Accepted

Solution code:
import sys
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import deque
K = ii()

#l = deque([1,2,3,4,5,6,7,8,9])
l = [1,2,3,4,5,6,7,8,9]
for i in range(K-9):
    a = l[i]
    b = int(str(a)[-1])
    if b!=0 and b != 9:
        for k in range(b-1, b+2):
            l.append(int(str(a)+str(k)))
    elif b==0:
        for k in range(b, b+2):
            l.append(int(str(a)+str(k)))
    else:
        for k in range(8, 10):
            l.append(int(str(a)+str(k)))

print(l[K-1])

Submission status: Accepted

Solution code:
K=int(input())


ANS=[[[] for _ in range(10)] for _ in range(10)]
for i in range(10):
    ANS[0][i].append(str(i))
for i in range(1,10):
    for j in range(10):
        if 1<=j and j<=8:
            for k in [j-1,j,j+1]:
                for v in ANS[i-1][k]:
                    ANS[i][j].append(str(j)+v)
        elif j==0:
            for k in [j,j+1]:
                for v in ANS[i-1][k]:
                    ANS[i][j].append(str(j)+v)
        elif j==9:
            for k in [j-1,j]:
                for v in ANS[i-1][k]:
                    ANS[i][j].append(str(j)+v)

X=[]
for i in range(10):
    for j in range(1,10):
        for k in ANS[i][j]:
            X.append(int(k))
X.sort()
print(X[K-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

d = [-1, 0, 1]

que = deque([])
for i in range(1, 10):
    que.append(i)
cnt = 0
while que:
    p = que.popleft()
    cnt += 1
    if cnt == K:
        print(p)
        break
    for i in d:
        if 0 <= int(str(p)[-1]) + i <= 9:
            que.append(int(str(p) + str(int(str(p)[-1]) + i)))

Submission status: Accepted

Solution code:
import sys

inputLine=input()
K=int(inputLine)

runrunNumberList=[]
runrunNumberCount=0
for i in range(10):
    runrunNumberList.append(str(i))
    if i != 0:
        runrunNumberCount += 1
    if runrunNumberCount == K:
        result = i
        print(result)
        sys.exit()

startPoint=0
endPoint=len(runrunNumberList)


while(True):
    for i in range(10):
        for j in range(startPoint, endPoint):
            
            if abs( int(i) - int( runrunNumberList[j][0] ) ) <= 1:
                runrunNumberList.append( str(i) + runrunNumberList[j] )

                if i != 0:
                    runrunNumberCount += 1

                if runrunNumberCount == K:
#                    print(runrunNumberList)
                    result = int( str(i) + runrunNumberList[j] )
                    print(result)
                    sys.exit()

    startPoint = endPoint
    endPoint = len(runrunNumberList)

Submission status: Accepted

Solution code:
import itertools

def new_lunlun(org_str):
    last_digit = org_str[-1]
    if last_digit == "0":
        return org_str + "0", org_str + "1"
    elif last_digit == "9":
        return org_str + "8", org_str + "9"
    else:
        minus_digit = str(int(last_digit) - 1)
        plus_digit = str(int(last_digit) + 1)
        return org_str + minus_digit, org_str + last_digit, org_str + plus_digit

def get_next_lunluns(lunluns):
    next_lunluns = [list(new_lunlun(lunlun)) for lunlun in lunluns]
    return list(itertools.chain.from_iterable(next_lunluns))

K = int(input())
# K = 100000
sum_num = 0

digits = [0,1,2,3,4,5,6,7,8,9]
ditits_str = list(map(str, digits))
lunluns = ditits_str.copy()[1:]

while(True):
    prev_num = sum_num
    sum_num += len(lunluns)
    if sum_num < K:
        lunluns = get_next_lunluns(lunluns)
    else:
        ind = K - prev_num - 1
        print(lunluns[ind])
        break

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
k = int(input())

x = [0]

while(k > 0):
    len_x = len(x)

    if len_x == 1:
        if x[0] != 9:
            x[0] = x[0] + 1
        else:
            x[0] = 1
            x.append(0)
    elif len_x == 2:
        if (x[0] == 9 and x[1] == 9):
            x = [0] * len(x)
            x.insert(0, 1)
        elif x[1] - x[0] < 1:
            x[1] += 1
        else:
            x[0] += 1
            x[1] = x[0] - 1
    else:
        for i in range(len_x):
            if sum(x) == 9 * len_x:
                x = [0] * len(x)
                x.insert(0, 1)
                break
            elif i == len_x - 1:
                x[0] += 1
                temp = x[0]
                x = [temp - i if temp - i >= 0 else 0 for i in range(len_x)]
                break
            elif x[-1 - i] - x[-2 - i] < 1:
                if x[-1 - i] == 9:
                    continue
                x[-1 - i] = x[-1 - i] + 1
                temp = x[-1 - i]
                for j in range(i):
                    j = i - j
                    x[-j] = x[-1 -j] - 1 if x[-1 -j] - 1 >= 0 else 0
                break
    k -= 1

print("".join([str(x) for x in x]))

Submission status: Accepted

Solution code:
K = int(input())

idx = 0
l = list(range(1, 10))

while len(l) < K:
    m = l[idx]
    for i in (-1, 0, 1):
        n = (m % 10) + i
        if n in {-1, 10}:
            continue
        tmp = int(str(m) + str(n))
        l.append(tmp)
    idx = idx + 1

print(l[K-1])

Submission status: Accepted

Solution code:
k = int(input())
cnt = 1
loop = 1
r_li = []

# 一桁小さいるんるんリストから次のるんるんリストを作成
def make_runrun(i, runrun_list):
    new_list = []
    for runrun in runrun_list:
        new_list.append('{}{}'.format(i, runrun))
    return new_list

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

# 桁数ごとにループ
while len(r_li) < k:
    # 一桁小さいルンルン数のリスト
    next_tmp = [[]] * 10
    for i in range(1, 10):
        l = 0
        r_li.extend(make_runrun(i, tmp[i - 1]))
        l += len(tmp[i - 1])
        r_li.extend(make_runrun(i, tmp[i]))
        l += len(tmp[i])
        if i != 9:
            r_li.extend(make_runrun(i, tmp[i + 1]))
            l += len(tmp[i + 1])
        next_tmp[i] = r_li[-l:]
    for i in tmp[0]:
        next_tmp[0].append('{}{}'.format(0, i))
    for i in tmp[1]:
        next_tmp[0].append('{}{}'.format(0, i))
    tmp = next_tmp

print(r_li[k - 1])

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
# N, K = map(int, input().split(' '))
N = int(input())
run = [list(map(str, range(1, 10)))]
l = 0
count = 9
stop = 10**5
while(1):
    if count > stop:
        break
    nextrun = []
    for i in run[l]:
        if i[-1] == '0':
            nextrun.append(i+'0')
            nextrun.append(i+'1')
        elif i[-1] == '9':
            nextrun.append(i+str(int(i[-1])-1))
            nextrun.append(i+str(int(i[-1])))
        else:
            nextrun.append(i+str(int(i[-1])-1))
            nextrun.append(i+str(int(i[-1])))
            nextrun.append(i+str(int(i[-1])+1))
    run.append(nextrun)
    count += len(nextrun)
    l += 1

newrun = []
for i in run:
    newrun.extend(i)
print(newrun[N-1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
import numpy as np

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()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]

k = int(input())
m = []
flatten = lambda x: [str(z) for y in x for z in (flatten(y) if hasattr(y, '__iter__') and not isinstance(y, str) else (y,))]

ll = [str(i) for i in range(1,10)]
o = []
for s in ll:
    l = []
    l.append(s)
    for i in range(10):
        p = []
        for j in l[-1]:
            t = []
            if str(j[-1])=='0':
                t.append(j+'0')
                t.append(j+'1')
            elif str(j[-1])=='9':
                t.append(j+'8')
                t.append(j+'9')
            else:
                t.append(j+str(int(j[-1])-1))
                t.append(j+str(int(j[-1])))
                t.append(j+str(int(j[-1])+1))
            p.append(t)
        l.append(flatten(p))
    o.append(l)

flatten = lambda x: [int(z) for y in x for z in (flatten(y) if hasattr(y, '__iter__') and not isinstance(y, str) else (y,))]

#print(sorted(set(flatten(o))))
print(sorted(set(flatten(o)))[k-1])

Submission status: Accepted

Solution code:
from itertools import product

k = int(input())
ls = []

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

while len(ls) < k:
    for i in range(1, 10):
        for j in product([-1, 0, 1], repeat=digit):
            num = str(i)
            skip = 0
            for y in j:
                x = int(num[-1])+y
                if x < 0 or 9 < x:
                    skip = 1
                    break
                num += str(x)
            if skip:
                continue
            ls.append(int(num))
    digit += 1
print(ls[k-1])

Submission status: Accepted

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

    if K < 10:
        print(K)
        return

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

    x = 9
    while True:
        T = []
        for r in R:
            if r % 10 > 0:
                T.append(r * 10 + (r % 10) - 1)
                x += 1
                if x >= K:
                    print(r * 10 + (r % 10) - 1)
                    return
            T.append(r * 10 + (r % 10))
            x += 1
            if x >= K:
                print(r * 10 + (r % 10))
                return
            if r % 10 < 9:
                T.append(r * 10 + (r % 10) + 1)
                x += 1
                if x >= K:
                    print(r * 10 + (r % 10) + 1)
                    return

        R = T[::]

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k = int(input())
ans = [str(i) for i in range(1,10)]
c = 0

while len(ans) < k:
    now = ans[c]
    t = int(now[-1])
    if t != 0:
        ans.append(str(now) +str(t-1))

    ans.append(str(now) +str(now)[-1])

    if t != 9:
        ans.append(str(now) +str(t+1))

    c += 1
print(ans[k-1])

Submission status: Accepted

Solution code:
k = int(input())

def dfs(now, depth):
    STACK.append(str(now))
    if depth == limit:
        LUNLUN.append(int("".join(STACK)))
    else:
        for next in range(now - 1, now + 2):
            if next == -1 or next == 10:
                continue
            dfs(next, depth + 1)
    STACK.pop()

LUNLUN = []
STACK= []
for limit in range(10):
    for i in range(1, 10):
        dfs(i, 0)

print(LUNLUN[k - 1])

Submission status: Accepted

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

while len(a) < K:
    temp = set()
    for now in prev:
        c = now%10
        if c == 0:
            temp.add(now*10)
            temp.add(now*10+1)
        elif c == 9:
            temp.add(now*10+9)
            temp.add(now*10+8)
        else:
            temp.add(now*10+c-1)
            temp.add(now*10+c)
            temp.add(now*10+c+1)
    prev = temp
    a = a|temp
print(sorted(list(a))[K-1])