Problem:


Score : 400 points

Problem Statement

A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:

In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1.

For example, 1234, 1, and 334 are lunlun numbers, while none of 31415, 119, or 13579 is.

You are given a positive integer K. Find the K-th smallest lunlun number.

Constraints

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer.

Sample Input 1

15

Sample Output 1

23

We will list the 15 smallest lunlun numbers in ascending order:

1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
21,
22,
23.

Thus, the answer is 23.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

13

Sample Output 3

21

Sample Input 4

100000

Sample Output 4

3234566667

Note that the answer may not fit into the 32-bit signed integer type.



Sample input:
15


Sample output:
23

Submission status: Accepted

Solution code:

import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

T = list(map(int,input().split()))

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''


K = int(input())

runrun = []
runrun.append([1, 2, 3, 4, 5, 6, 7, 8, 9])


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


keta = 10
for i in range(1, 20):
    max = 9*pow(3, i-1)

    if max>=K:
        keta = i
        break

for i in range(2, keta+2):
    temp = []
    for j in range(len(runrun[i-2])):

        last = runrun[i-2][j] % 10

        tugi = (last+1) 
        same = last
        mae = (last-1) 

        if tugi != 10:
            temp.append(runrun[i-2][j]*10 + tugi)
        temp.append(runrun[i-2][j]*10 + same)
        
        if mae != -1:
            temp.append(runrun[i-2][j]*10 + mae)

    runrun.append(temp)

sum_size = 0
nokori  =0
for i in range(100):
    runrun[i].sort()
    sum_size+=len(runrun[i])
    if sum_size >= K:
        keta = i
        nokori = K- sum_size+len(runrun[i])
        break

runrun[keta].sort()

print(runrun[keta][nokori-1])

Submission status: Accepted

Solution code:
K=int(input())
cnt=0
dp=[0]*(10**6)
piv=0
dig=[0]*10000
d=0
cnt=float("inf")
zure=0
befnum=0
i=0
buf=""
cntall=0
while i<2*(10**5):
    if i+1<10:
        dp[i]=i+1
        dig[d]=dig[d]+1
    else:
        if cnt>=dig[d-1]:
            i=i+zure
            zure=0
            cnt=0
            befnum=dig[d]
            d=d+1
        #print(i,befnum)
        buf=str(dp[i-befnum])
        piv=buf[len(buf)-1]
        #print(buf, piv,i-befnum)
        #print(dp,dig,zure,i,dig[i],dp[i-befnum],befnum)
        if int(piv)==0:
            dp[i+zure]=dp[i-befnum]*10
            dp[i+1+zure]=dp[i - befnum] * 10+1
            dig[d]=dig[d]+2
            zure=zure+1
        elif int(piv)==9:
            dp[i + zure] = dp[i - befnum] * 10+8
            dp[i + 1 + zure] = dp[i - befnum] * 10+9
            dig[d] = dig[d] + 2
            zure = zure + 1
        else:
            dp[i+zure]=dp[i-befnum]*10+int(piv)-1
            dp[i+1+zure]=dp[i - befnum] * 10+int(piv)
            dp[i+2+zure] = dp[i - befnum] * 10 + int(piv)+1
            dig[d] = dig[d] + 3
            zure=zure+2
        cnt=cnt+1
    i=i+1
    #if i%20000==0:
        #print(i)
    #print(dp)
    #input()
print(dp[K-1])

Submission status: Accepted

Solution code:
target=int(input())

if target<13:
    print(target)
    exit()

cnt=9

result={}
for i in range(10):
    result[i]=[[i],[],[],[],[],[],[],[],[],[],[],[],[],[]]

for j in range(20):
    temp=[]
    for i in [1,2,3,4,5,6,7,8,9]:
        for k in result[i-1][j]:
            result[i][j+1].append(str(i)+str(k))
            cnt+=1
            if cnt==target:
                print(str(i)+str(k))
                exit()
        for k in result[i][j]:
            result[i][j+1].append(str(i)+str(k))
            cnt+=1
            if cnt==target:
                print(int(str(i)+str(k)))
                exit()
        if i!=9:                
            for k in result[i+1][j]:
                result[i][j+1].append((str(i)+str(k)))
                cnt+=1
                if cnt==target:
                    print(int(str(i)+str(k)))
                    exit()
    for item in result[0][j]:
        result[0][j+1].append(str(0)+str(item))
        #print(str(0)+str(k))
    for item in result[1][j]:
        result[0][j+1].append(str(0)+str(item))

print(result[0])

Submission status: Accepted

Solution code:

import copy

k = int(input())

lun = [1,2,3,4,5,6,7,8,9]
tlun = []
tlun = copy.deepcopy(lun)
length = 2
while len(lun) < k:
    tmp = []
    for x in tlun:
        y = str(x)
        xt = int( y[-1] )
        a = xt + 1
        b = xt - 1
        if a != 10:
            lun.append(int(y+str(a)))
            tmp.append(int(y+str(a)))
        
        if b != -1:
            lun.append(int(y+str(b)))
            tmp.append(int(y+str(b)))
        
        lun.append(int(y+str(xt)))
        tmp.append(int(y+str(xt)))
    tlun = copy.deepcopy(tmp)

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

Submission status: Accepted

Solution code:
def addketa(x):
    lunlun.append(x)
    if(x > 999999999):
        return 0
    strx = str(x)
    strxlast = int(strx[-1])
    if(strxlast == 0):
        addketa(int(strx+"0"))
        addketa(int(strx+"1"))
    else:
        if(strxlast == 9):
            addketa(int(strx+"8"))
            addketa(int(strx+"9"))
        else:
            addketa(int(strx+str(strxlast-1)))
            addketa(int(strx+str(strxlast)))
            addketa(int(strx+str(strxlast+1)))

            
K = int(input())
lunlun = []


for x in range (1, 10):
    addketa(x)

lunlun.sort()

print(lunlun[K-1])

Submission status: Accepted

Solution code:
k = int(input())

a = [list(range(1, 10))]
while True:
    new = []
    for aa in a[-1]:
        mod = aa % 10
        if mod != 0:
            new.append(aa * 10 + mod - 1)
        new.append(aa * 10 + mod)
        if mod != 9:
            new.append(aa * 10 + mod + 1)
    a.append(new)

    if sum([len(aa) for aa in a]) > k:
        break
flat = sorted(sum(a, []))

print(flat[k - 1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
K = int(input())
RUN = {
    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]
}
cnt = 0
for i10 in range(10):
    ans10 = i10 * 10 ** 9
    if ans10 == 0:
        i9s = range(10)
    else:
        i9s = RUN[i10]
    for i9 in i9s:
        ans9 = ans10 + i9 * 10 ** 8
        if ans9 == 0:
            i8s = range(10)
        else:
            i8s = RUN[i9]
        for i8 in i8s:
            ans8 = ans9 + i8 * 10 ** 7
            if ans8 == 0:
                i7s = range(10)
            else:
                i7s = RUN[i8]
            for i7 in i7s:
                ans7 = ans8 + i7 * 10 ** 6
                if ans7 == 0:
                    i6s = range(10)
                else:
                    i6s = RUN[i7]
                for i6 in i6s:
                    ans6 = ans7 + i6 * 10 ** 5
                    if ans6 == 0:
                        i5s = range(10)
                    else:
                        i5s = RUN[i6]
                    for i5 in i5s:
                        ans5 = ans6 + i5 * 10 ** 4
                        if ans5 == 0:
                            i4s = range(10)
                        else:
                            i4s = RUN[i5]
                        for i4 in i4s:
                            ans4 = ans5 + i4 * 10 ** 3
                            if ans4 == 0:
                                i3s = range(10)
                            else:
                                i3s = RUN[i4]
                            for i3 in i3s:
                                ans3 = ans4 + i3 * 10 ** 2
                                if ans3 == 0:
                                    i2s = range(10)
                                else:
                                    i2s = RUN[i3]
                                for i2 in i2s:
                                    ans2 = ans3 + i2 * 10
                                    if ans2 == 0:
                                        i1s = range(1, 10)
                                    else:
                                        i1s = RUN[i2]
                                    for i1 in i1s:
                                        ans1 = ans2 + i1
                                        cnt += 1
                                        # print(cnt, ans1)
                                        if cnt == K:
                                            print(ans1)
                                            exit()

Submission status: Accepted

Solution code:
k = int(input())

one_digit = ["1","2","3","4","5","6","7","8","9"]
tem_digit = []
entity = []
entity.append(one_digit)
for j in range(10):
    tem_digit = []
    for i in range(len(entity[-1])):
        if entity[-1][i][-1] == "9":
            tem_digit.append(entity[-1][i] + "8")
            tem_digit.append(entity[-1][i] + "9")
        elif entity[-1][i][-1] == "0":
            tem_digit.append(entity[-1][i] + "0")
            tem_digit.append(entity[-1][i] + "1")
        else:
            tem_digit.append(entity[-1][i] + str(int(entity[-1][i][-1]) - 1))
            tem_digit.append(entity[-1][i] + str(int(entity[-1][i][-1])))
            tem_digit.append(entity[-1][i] + str(int(entity[-1][i][-1]) + 1))
    tem_digit.sort()
    entity.append(tem_digit)

entity = sum(entity, [])
#print(entity)
print(entity[k-1])

Submission status: Accepted

Solution code:
def next(n):
    i = len(n) -1
    nine = False
    if len(n) == 1:
        if n == [9]:
            return [1,0]
        else:
            return [n[0]+1]
    while i >= 0:
        if nine:
            if n[i] == 8:
                nine = False
                if n[i] - n[i-1] != 1:
                    break
            if i == 0:
                return [1] + [0 for m in range(len(n))]
        else:
            if n[i] == 9:
                nine = True
            elif n[i] - n[i-1] != 1:
                break
        i -= 1
    n[i] += 1
    i += 1
    while i < len(n):
        n[i] = max(0, n[i-1] - 1)
        i += 1
    return n

k = int(input())
if k == 1:
    print('1')
    exit()
i = 1
n = [1]
while i < k:
    i += 1
    n = next(n)
print(*n, sep='')

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

d = deque()
for i in range(1,10):
    d.append(i)

i = 0
while i < k:
    a = str(d.popleft())

    if a[-1] == "0":
        d.append(a + "0")
        d.append(a + "1")
    elif a[-1] == "9":
        d.append(a + "8")
        d.append(a + "9")
    else:
        d.append(a + str(int(a[-1]) - 1))
        d.append(a + str(int(a[-1])))
        d.append(a + str(int(a[-1]) + 1))
        pass
    i += 1

print(a)

Submission status: Accepted

Solution code:
K = int(input())

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

def concat(org):
  end = int(org[-1])
  r = []
  if end != 0:
    r.append(org + str(end-1))
  r.append(org + str(end))
  if end != 9:
    r.append(org + str(end+1))
  return r

t = [str(i) for i in range(1, 10)]
for i in range(2, 11):
  r = []
  for e in t:
    r.extend(concat(e))
  t = r
  lunlun.extend(t)

# print(lunlun)
# print(len(lunlun))
print(lunlun[K-1])

Submission status: Accepted

Solution code:
K = int(input())


def lun(n):
    found = []

    def _lun(top, m):
        if m == 0:
            found.append(int("".join(map(str, top))))
            return
        for t in (top[-1] - 1, top[-1], top[-1] + 1):
            if 0 <= t <= 9:
                _lun(top + [t], m - 1)

    for i in range(1, 10):
        _lun([i], n - 1)

    return found


d = 1
luns = []
while True:
    luns.extend(lun(d))
    if len(luns) >= K:
        break
    d += 1

print(luns[K - 1])

Submission status: Accepted

Solution code:
K = int(input())
l_lun = [i for i in range(1, 10)]
nowp = 0
while(nowp < K):
  newp = len(l_lun)
  for i in range(nowp, newp):
    left = l_lun[i] % 10
    for j in range(left - 1, left + 2):
      if j < 0 or j >= 10:
        continue
      l_lun.append(l_lun[i] * 10 + j)
  nowp = newp
print(l_lun[K-1])

Submission status: Accepted

Solution code:
K = int(raw_input())

MAXX = 10**5*3
#gen lunlun

list = []
def genLunlun(dep, last, res):
    if dep <= 0:
        list.append(res)
        return 1

    cnt = 0
    if res == 0:
        for d in range(1, 10):
            cnt = cnt + genLunlun(dep-1, d, d)
        return cnt


    for d in range(-1,2):
        num = last + d
        if (num >= 0) and (num <= 9):
            cnt = cnt + genLunlun(dep-1, num, res*10 + num)
    return cnt

def findX(list, K):
    last = -1
    cnt = 0
    for item in list:
        if item != last:
            cnt = cnt + 1
            last = item
            if cnt == K:
                return last
    return -1

total = 0
num = 0
dep = 0
while True:
    dep = dep + 1
    cnt = genLunlun(dep, -1, 0)
    total = total + cnt
    if total >= K:
        num = list[K-1]
        #list.sort()
        #num = findX(list, K)
        break

print(num)

Submission status: Accepted

Solution code:
k = int(input())
if k <10:
    print(k)
    exit()
ls = [0] * (k+1)
for i in range(10):
    ls[i] = str(i)

l = len(str(k))
cnt = 10
tag = 1
f = False
for j in range(k+1):
    s = ls[tag]
    for i in range(10):
        if  abs(int(s[-1])-i) <=1:
            ls[cnt] =  s+str(i)
            cnt+=1
        if cnt ==k+1:
            f = True
            break
    if f:
        break
    tag +=1
print(ls[-1])

Submission status: Accepted

Solution code:



K = int(input())

list0 = ['0']
list1 = ['1']
list2 = ['2']
list3 = ['3']
list4 = ['4']
list5 = ['5']
list6 = ['6']
list7 = ['7']
list8 = ['8']
list9 = ['9']

an = 0


def AAA(list0,list1,list2,list3,list4,list5,list6,list7,list8,list9):
    nlist0 = [0]*(len(list0)+len(list1))
    nlist1 = [0]*(len(list0)+len(list1)+len(list2))
    nlist2 = [0]*(len(list1)+len(list2)+len(list3))
    nlist3 = [0]*(len(list2)+len(list3)+len(list4))
    nlist4 = [0]*(len(list3)+len(list4)+len(list5))
    nlist5 = [0]*(len(list4)+len(list5)+len(list6))
    nlist6 = [0]*(len(list5)+len(list6)+len(list7))
    nlist7 = [0]*(len(list6)+len(list7)+len(list8))
    nlist8 = [0]*(len(list7)+len(list8)+len(list9))
    nlist9 = [0]*(len(list8)+len(list9))
    
    for i in range(len(list0)):
        nlist0[i] = '0' + list0[i]
    for j in range(len(list1)):
        nlist0[len(list0)+j] = '0' + list1[j]
        
        
    for i in range(len(list0)):
        nlist1[i] = '1' + list0[i]
    for j in range(len(list1)):
        nlist1[len(list0)+j] = '1' + list1[j]
    for k in range(len(list2)):
        nlist1[len(list0)+len(list1)+k] = '1' + list2[k]
        
    
    for i in range(len(list1)):
        nlist2[i] = '2' + list1[i]
    for j in range(len(list2)):
        nlist2[len(list1)+j] = '2' + list2[j]
    for k in range(len(list3)):
        nlist2[len(list1)+len(list2)+k] = '2' + list3[k]
        

    for i in range(len(list2)):
        nlist3[i] = '3' + list2[i]
    for j in range(len(list3)):
        nlist3[len(list2)+j] = '3' + list3[j]
    for k in range(len(list4)):
        nlist3[len(list2)+len(list3)+k] = '3' + list4[k]
    
    for i in range(len(list3)):
        nlist4[i] = '4' + list3[i]
    for j in range(len(list4)):
        nlist4[len(list3)+j] = '4' + list4[j]
    for k in range(len(list5)):
        nlist4[len(list3)+len(list4)+k] = '4' + list5[k]
    
    for i in range(len(list4)):
        nlist5[i] = '5' + list4[i]
    for j in range(len(list5)):
        nlist5[len(list4)+j] = '5' + list5[j]
    for k in range(len(list6)):
        nlist5[len(list4)+len(list5)+k] = '5' + list6[k]
    
    for i in range(len(list5)):
        nlist6[i] = '6' + list5[i]
    for j in range(len(list6)):
        nlist6[len(list5)+j] = '6' + list6[j]
    for k in range(len(list7)):
        nlist6[len(list5)+len(list6)+k] = '6' + list7[k]
    
    for i in range(len(list6)):
        nlist7[i] = '7' + list6[i]
    for j in range(len(list7)):
        nlist7[len(list6)+j] = '7' + list7[j]
    for k in range(len(list8)):
        nlist7[len(list6)+len(list7)+k] = '7' + list8[k]
    
    for i in range(len(list7)):
        nlist8[i] = '8' + list7[i]
    for j in range(len(list8)):
        nlist8[len(list7)+j] = '8' + list8[j]
    for k in range(len(list9)):
        nlist8[len(list7)+len(list8)+k] = '8' + list9[k]
    
    for i in range(len(list8)):
        nlist9[i] = '9' + list8[i]
    for j in range(len(list9)):
        nlist9[len(list8)+j] = '9' + list9[j]
        
    return(nlist0,nlist1,nlist2,nlist3,nlist4,nlist5,nlist6,nlist7,nlist8,nlist9)


while an + len(list1)+len(list2)+len(list3)+len(list4)+len(list5)+len(list6)+len(list7)+len(list8)+len(list9) < K:
    an = an + len(list1)+len(list2)+len(list3)+len(list4)+len(list5)+len(list6)+len(list7)+len(list8)+len(list9)
    list0,list1,list2,list3,list4,list5,list6,list7,list8,list9 = AAA(list0,list1,list2,list3,list4,list5,list6,list7,list8,list9)

nK = K - an
if len(list1) >= nK:
    ans = list1[nK-1]
    nK = 10**8
else:
    nK = nK - len(list1)

if len(list2) >= nK:
    ans = list2[nK-1]
    nK = 10**8
else:
    nK = nK - len(list2)

if len(list3) >= nK:
    ans = list3[nK-1]
    nK = 10**8
else:
    nK = nK - len(list3)

if len(list4) >= nK:
    ans = list4[nK-1]
    nK = 10**8
else:
    nK = nK - len(list4)

if len(list5) >= nK:
    ans = list5[nK-1]
    nK = 10**8
else:
    nK = nK - len(list5)

if len(list6) >= nK:
    ans = list6[nK-1]
    nK = 10**8
else:
    nK = nK - len(list6)
    
if len(list7) >= nK:
    ans = list7[nK-1]
    nK = 10**8
else:
    nK = nK - len(list7)

if len(list8) >= nK:
    ans = list8[nK-1]
    nK = 10**8
else:
    nK = nK - len(list8)

if len(list9) >= nK:
    ans = list9[nK-1]
    nK = 10**8
else:
    nK = nK - len(list9)
    
    
print(int(ans))

Submission status: Accepted

Solution code:
K=int(input())
x=[0]*11
p=0
def f(p):
    if x[p]<9:
        x[p]+=1
        g(p)
    else:
        p+=1
        x[:p+1]=[0]*p+[1]
    return p
def g(p):
    y=x[p]
    for i in range(p-1,-1,-1):
        y=max(y-1,0)
        x[i]=y
for i in range(K):
    z=0
    if p==0:
        p=f(p)
    else:
        for q in range(p):
            if x[q]<x[q+1]+1 and x[q]<9:
                x[q]+=1
                g(q)
                z=1
                break
        if z==0:
            p=f(p)
while x[-1]==0:
    x.pop()
print("".join(reversed([str(n) for n in x])))

Submission status: Accepted

Solution code:
k = int(input())
num = {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]}
lun = [[1,2,3,4,5,6,7,8,9]]
lun_len = sum([len(l) for l in lun])
while lun_len < k:
    new_lun=[]
    for l in lun[-1]:
        for n in num[int(str(l)[-1])]:
            a=int(str(l)+str(n))
            new_lun.append(a)
    lun.append(new_lun)
    lun_len = sum([len(l) for l in lun])

for l in lun:
    if len(l)>k:
        print(l[k-1])
    else:
        k-=len(l)

Submission status: Accepted

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

K=one_int()



def solve(start, goal, lists):
    ret_lists=[]
    
    for i in lists:
        str_i = str(i)
        t = int(str_i[-1])
        
        if t==0:
            ret_lists.append(i*10)
            start+=1
            if start==goal:
                return ret_lists, start
            
            ret_lists.append(i*10+1)
            start+=1
            if start==goal:
                return ret_lists, start

        elif t==9:
            ret_lists.append(i*10+8)
            start+=1
            if start==goal:
                return ret_lists, start
            
            ret_lists.append(i*10+9)
            start+=1
            if start==goal:
                return ret_lists, start
        
        else:
            for s in range(-1,2):
                ret_lists.append(i*10+int(t)+s)
                start+=1
                if start==goal:
                    return ret_lists, start
  
    return ret_lists, start

if K>9:
    lists = [i for i in range(1,10)]
    start = 9
    while True:
        lists, start = solve(start, K, lists)
        if K<=start:
            print(lists[-1])
            break
else:
    print(K)

Submission status: Accepted

Solution code:
n = int(input())
if n < 10:
    print(n)
else:
    n -= 10
    num = [1, 0]
    while n:
        i = len(num)-1
        while i > 0 and (num[i] == 9 or num[i] > num[i-1]):
            i -= 1
        if i == 0 and num[0] == 9:
            num = [1] + [0]*len(num)
        else:
            num[i] += 1
            for j in range(i+1, len(num)):
                num[j] = max(num[j-1] - 1, 0)
        n -= 1
        # print(''.join(map(str, num)))
    print(''.join(map(str, num)))

Submission status: Accepted

Solution code:
c = 0
K = int(input())
for i in range(1,10):
    c += 1
    if c == K:
        print(i)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        c += 1
        if c == K:
            print(10*i+j)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            c += 1
            if c == K:
                print(100*i+10*j+k)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                c += 1
                if c == K:
                    print(1000*i+100*j+10*k+l)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                for m in range(max(l-1,0),min(l+2,10)):
                    c += 1
                    if c == K:
                        print(10000*i+1000*j+100*k+10*l+m)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                for m in range(max(l-1,0),min(l+2,10)):
                    for n in range(max(m-1,0),min(m+2,10)):
                        c += 1
                        if c == K:
                            print(100000*i+10000*j+1000*k+100*l+10*m+n)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                for m in range(max(l-1,0),min(l+2,10)):
                    for n in range(max(m-1,0),min(m+2,10)):
                        for o in range(max(n-1,0),min(n+2,10)):
                            c += 1
                            if c == K:
                                print(1000000*i+100000*j+10000*k+1000*l+100*m+10*n+o)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                for m in range(max(l-1,0),min(l+2,10)):
                    for n in range(max(m-1,0),min(m+2,10)):
                        for o in range(max(n-1,0),min(n+2,10)):
                            for q in range(max(o-1,0),min(o+2,10)):
                                c += 1
                                if c == K:
                                    print(10000000*i+1000000*j+100000*k+10000*l+1000*m+100*n+10*o+q)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                for m in range(max(l-1,0),min(l+2,10)):
                    for n in range(max(m-1,0),min(m+2,10)):
                        for o in range(max(n-1,0),min(n+2,10)):
                            for q in range(max(o-1,0),min(o+2,10)):
                                for t in range(max(q-1,0),min(q+2,10)):
                                    c += 1
                                    if c == K:
                                        print(100000000*i+10000000*j+1000000*k+100000*l+10000*m+1000*n+100*o+10*q+t)

for i in range(1,10):
    for j in range(i-1,min(i+2,10)):
        for k in range(max(j-1,0),min(j+2,10)):
            for l in range(max(k-1,0),min(k+2,10)):
                for m in range(max(l-1,0),min(l+2,10)):
                    for n in range(max(m-1,0),min(m+2,10)):
                        for o in range(max(n-1,0),min(n+2,10)):
                            for q in range(max(o-1,0),min(o+2,10)):
                                for t in range(max(q-1,0),min(q+2,10)):
                                    for y in range(max(t-1,0),min(t+2,10)):
                                        c += 1
                                        if c == K:
                                            print(1000000000*i+100000000*j+10000000*k+1000000*l+100000*m+10000*n+1000*o+100*q+10*t+y)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
z = int(input())
l = []
for i in range(1,10):
    l.append(i)
    for j in range(max(0,i-1),min(10,i+2)):
        l.append(int(str(i)+str(j)))
        for k in range(max(j-1,0),min(10,j+2)):
            l.append(int(str(i)+str(j)+str(k)))
            for m in range(max(k-1,0),min(10,k+2)):
                l.append(int(str(i)+str(j)+str(k)+str(m)))
                for n in range(max(m-1,0),min(10,m+2)):
                    l.append(int(str(i)+str(j)+str(k)+str(m)+str(n)))
                    for o in range(max(n-1,0),min(10,n+2)):
                        l.append(int(str(i)+str(j)+str(k)+str(m)+str(n)+str(o)))
                        for p in range(max(o-1,0),min(10,o+2)):
                            l.append(int(str(i)+str(j)+str(k)+str(m)+str(n)+str(o)+str(p)))
                            for q in range(max(p-1,0),min(10,p+2)):
                                l.append(int(str(i)+str(j)+str(k)+str(m)+str(n)+str(o)+str(p)+str(q)))
                                for r in range(max(q-1,0),min(10,q+2)):
                                    l.append(int(str(i)+str(j)+str(k)+str(m)+str(n)+str(o)+str(p)+str(q)+str(r)))
                                    for s in range(max(r-1,0),min(10,r+2)):
                                        l.append(int(str(i)+str(j)+str(k)+str(m)+str(n)+str(o)+str(p)+str(q)+str(r)+str(s)))

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

Submission status: Accepted

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

if K <= 9 :
    print(lun[K])
else :
    def dfs(digit, max_digit, cur, K) :
        if digit == max_digit :
            lun.append( "".join(cur) )
            if len(lun) == K :
                return True
            return False
        elif digit > max_digit :
            return False

        c = int(cur[-1])
        for i in [-1,0,1] :
            if c+i < 0 or c+i > 9 :
                continue
            cur.append(str(c+i) )
            if dfs(digit+1, max_digit, cur, K) :
                return True
            cur.pop()
        return False

    max_digit = 2
    stop = False
    while True :
        for i in range(1, 10) :
            cur = [str(i)]
            if dfs(1, max_digit, cur, K+1) :
                stop = True
                break 
        if stop :
            break 
        max_digit += 1

    print(lun[-1])

Submission status: Accepted

Solution code:
K = int(input())
last_ind = 0
li =[1,2,3,4,5,6,7,8,9]
length =0
while K>len(li):
    new_li = li[length:len(li)]
    length = len(li)
    for l in new_li:
        matsubi = int(list(str(l))[-1])
        if matsubi == 0:
            li.append(int(str(l)+str(matsubi)))
            li.append(int(str(l)+str(matsubi+1)))
        elif matsubi == 9:
            li.append(int(str(l)+str(matsubi-1)))
            li.append(int(str(l)+str(matsubi)))
        else:
            li.append(int(str(l)+str(matsubi-1)))
            li.append(int(str(l)+str(matsubi)))
            li.append(int(str(l)+str(matsubi+1)))
        if len(li)>K:
            break
        
print(li[K-1])

Submission status: Accepted

Solution code:
def main():
    K=int(input())
    total=[9, 35, 110, 327, 956, 2782, 8089, 23527, 68468, 199368]
    if K<10:
        print(K)
    else:
        for i in range(9):
            if total[i]<K and total[i+1]>=K:
                a=[1,2,3,4,5,6,7,8,9]
                for j in range(i+1):
                    b=[]
                    for k in range(len(a)):
                        if a[k]%10==0:
                            b.append(10*a[k])
                            b.append(10*a[k]+1)
                        elif a[k]%10==9:
                            b.append(10*a[k]+8)
                            b.append(10*a[k]+9)
                        else:
                            b.append(10*a[k]+a[k]%10-1)
                            b.append(10*a[k]+a[k]%10)
                            b.append(10*a[k]+a[k]%10+1)
                    a,b=b,a
                print(a[K-total[i]-1])
if __name__=="__main__":
    main()