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 itertools
def addLunLun(str_num):
    last_digit = int(str_num[len(str_num)-1:])
    if last_digit == 0:
        return [str_num+"0",str_num+"1"]
    elif last_digit == 9:
        return [str_num+"8",str_num+"9"]
    else:
        return [str_num + str(last_digit-1),str_num + str(last_digit),str_num + str(last_digit+1)]
    
digits1 = [str(i) for i in range(1,10)]
digits2 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits1]))
digits3 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits2]))
digits4 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits3]))
digits5 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits4]))
digits6 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits5]))
digits7 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits6]))
digits8 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits7]))
digits9 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits8]))
digits10 = list(itertools.chain.from_iterable([addLunLun(i) for i in digits9]))
index = digits1 + digits2 + digits3 + digits4 + digits5 + digits6 + digits7 + digits8 + digits9 + digits10
K = int(input())
print(index[K-1])

Submission status: Accepted

Solution code:
k=int(input())
if k<9:print(k);exit()
t=[i for i in range(1,10)]
c=9
while c<k:
  a=t.pop(0)
  for i in range(max(0,a%10-1),min(10,a%10+2)):
    t.append(a*10+i)
    c+=1
print(t[-1-c+k])

Submission status: Accepted

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

    MAX = 10

    def search(base):
        if len(base) == MAX:
            # print(base)
            return [base]
        else:
            result = [base]
            last = base[-1]
            if last != '9':
                # print('A', base + str(int(last) + 1))
                result.extend(search(base + str(int(last) + 1)))
            if last != '0':
                # print('B', base + str(int(last) - 1))
                result.extend(search(base + str(int(last) - 1)))
            # print('C', base + last)
            result.extend(search(base + last))
            return result

    runrun = []

    for i in range(0, 10):
        el = search(str(i))
        # print(i, el)
        runrun.extend(el)

    runrun_i = list(map(int, list(map(lambda x: x[::-1], runrun))))
    runrun_u = list(set(runrun_i))
    runrun_s = sorted(runrun_u)

    # print(runrun_s)

    print(runrun_s[K])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K = int(input())
# A,B = map(int,input().split())
# S = input()
# X1_list = [int(input()) for i in range(N)]
# X2_list = [list(map(int,input().split())) for i in range(N)]
base = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
result = [1, 2, 3, 4, 5, 6, 7, 8, 9]


def make_lun_lun(tempresult, n):
    stemp = []
    itemp = []
    if n == 0:
        return
    for r in tempresult:
        sa = r[len(r) - 1]
        ia = int(r[len(r) - 1])
        # print(r[len(r) - 1])
        if ia - 1 > -1:
            stemp.append(r + str(ia - 1))
            itemp.append(int(r + str(ia - 1)))
        if ia + 1 < 10:
            stemp.append(r + str(ia + 1))
            itemp.append(int(r + str(ia + 1)))
        stemp.append(r + sa)
        itemp.append(int(r + sa))
    result.extend(itemp)
    make_lun_lun(stemp, n - 1)


make_lun_lun(base, 9)
# print(result)
print(sorted(result)[K - 1])
# print(result)

Submission status: Accepted

Solution code:
K = int(raw_input())
L = []

def dfs(n, m, s):
    if n <= s and s <= m:
        L.append(s)

    if s == 0 or s > m:
        return

    ld = s % 10
    s0 = s*10 + ld-1
    s1 = s*10 + ld
    s2 = s*10 + ld+1

    if ld == 0:
        dfs(n, m, s1)
        dfs(n, m, s2)
    elif ld == 9:
        dfs(n, m, s0)
        dfs(n, m, s1)
    else:
        dfs(n, m, s0)
        dfs(n, m, s1)
        dfs(n, m, s2)

for i in range(10):
    dfs(0, 10**10, i)

A = sorted(L)
print A[K]

Submission status: Accepted

Solution code:
kk = int(input())
if kk < 10:
    print(kk)
    exit()


dp = [[0] * 10 for _ in range(15)]
dp[0] = [1] * 10
for i in range(14):
    #dp[i+1][0] += sum(dp[i])
    for j in range(10):
        for k in range(-1, 2):
            if not (0 <= j + k < 10):
                continue
            dp[i + 1][j + k] += dp[i][j]

a = 0
for i in range(15):
    if a+sum(dp[i][1:]) >= kk:
        break
    a += sum(dp[i][1:])

ii = i


for j in range(1, 10):
    if a + dp[i][j] >= kk:
        kk -= a
        break
    a += dp[i][j]

ans = j
for i in reversed(range(ii)):
    a = 0
    for k in range(-1, 2):
        if not (0 <= j + k < 10):
            continue
        if a + dp[i][j + k] >= kk:
            kk -= a
            j = j + k
            ans = ans * 10 + j

            break
        a += dp[i][j + k]


print(ans)

Submission status: Accepted

Solution code:
K = int(input())
count = 9

def calc(keta, num):
    global count
    if keta == 0:
        if num[-1] == "9":
            count += 1
            if count == K:
                print(num + str(int(num[-1]) - 1))
                quit()
            count += 1
            if count == K:
                print(num + str(int(num[-1])))
                quit()
        elif num[-1] == "0":
            count += 1
            if count == K:
                print(num + str(int(num[-1])))
                quit()
            count += 1
            if count == K:
                print(num + str(int(num[-1]) + 1))
                quit()
        else:
            count += 1
            if count == K:
                print(num + str(int(num[-1]) - 1))
                quit()
            count += 1
            if count == K:
                print(num + str(int(num[-1])))
                quit()
            count += 1
            if count == K:
                print(num + str(int(num[-1]) + 1))
                quit()
    else:
        if num[-1] == "9":
            calc(keta-1,num+str(int(num[-1]) - 1))
            calc(keta-1,num+str(int(num[-1])))
        elif num[-1] == "0":
            calc(keta-1,num+str(int(num[-1])))
            calc(keta-1,num+str(int(num[-1]) + 1))
        else:
            calc(keta-1,num+str(int(num[-1]) - 1))
            calc(keta-1,num+str(int(num[-1])))
            calc(keta-1,num+str(int(num[-1]) + 1))

if K < 10:
    print(K)
    quit()

while(True):
    for i in range(10000):
        for k in range(1,10):
            calc(i, str(k))

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def foo(l,m):
    if m==0:
        return 1
    sm = foo(l,m-1)
    if l<9:
        sm += foo(l+1,m-1)
    if l>0:
        sm += foo(l-1,m-1)
    return sm

d = [[0]*10 for i in range(11)]
for m in range(11):
    for l in range(10):
        d[m][l] = foo(l,m)

#for i in range(11):
#    ddprint(d[i])

k = inn()
sm = 0
ans = []
for m in range(11):
    for l in range(1,10):
        sm += d[m][l]
        if sm>=k:
            break
    if sm>=k:
        break
# leftmost l, m digits
ans.append(l)
sm -= d[m][l]
for n in range(m-1,-1,-1):
    for ll in range(max(0,l-1), min(9,l+1)+1):
        sm += d[n][ll]
        if sm>=k:
            break
    sm -= d[n][ll]
    ans.append(ll)
    l = ll

print(''.join([str(x) for x in ans]))

Submission status: Accepted

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

while len(l)<k:
    t2=[]
    for i in t:
        m=i%10
        if m != 0:
            t2.append(i*10+(m-1))
        t2.append(i*10 + m)
        if m != 9:
            t2.append(i*10+(m+1))
    l.extend(t2)
    t=t2
print(l[k-1])

Submission status: Accepted

Solution code:
k = int(input())
lunluns = list(map(str, range(1,10)))
new = list(map(str, range(1,10)))
new_fueta = 9
end = False
while len(lunluns) < k:
  new_new_fueta = 0
  for x in lunluns[-new_fueta:]:
    str_x = str(x)
    if str_x[-1] == '0':
      lunluns += [int(str_x+'0'),int(str_x+'1')]
      new_new_fueta += 2
    elif str_x[-1] == '9':
      lunluns += [int(str_x+'8'),int(str_x+'9')]
      new_new_fueta += 2
    else:
      l = int(str_x[-1])
      lunluns += [int(str_x+str(l-1)), int(str_x+str(l)), int(str_x+str(l+1))]
      new_new_fueta += 3
  if end:
    break
  new_fueta = new_new_fueta
print(lunluns[k-1])

Submission status: Accepted

Solution code:
count = 0


def dfs(num):
    global count
    if len(str(num)) == 10:
        return
    else:
        tmp = int(str(num)[len(str(num))-1])
        for j in range(tmp-1, tmp+2):
            if 0 <= j <= 9:
                out = int(str(num) + str(j))
                ans.append(out)
                count += 1
                dfs(out)


if __name__ == "__main__":
    k = int(input())

    # まず100000個のルンルン数を列挙しよう

    ans = list()

    for i in range(1, 10):
        ans.append(i)
        count += 1
        dfs(i)

    ans.sort()

    print(ans[k-1])

Submission status: Accepted

Solution code:
k=int(input())
if k==1:
  print(1)
  exit()
if k==10:
  print(10)
  exit()
if k==36:
  print(100)
  exit()
if k==111:
  print(1000)
  exit()
if k==328:
  print(10000)
  exit()
if k==957:
  print(100000)
  exit()
if k==2783:
  print(1000000)
  exit()
if k==8090:
  print(10000000)
  exit()
if k==23528:
  print(100000000)
  exit()
if k==68469:
  print(1000000000)
  exit()
k=k-1
A=[[[1],[2],[3],[4],[5],[6],[7],[8],[9]]]+[[] for i in range(10)]
a=[-1,0,1]
B=[0]
for i in range(10):
  for j in A[i]:
    for s in range(3):
      if j[-1]==0 and s==0:
        continue
      if j[-1]==9 and s==2:
        continue
      A[i+1].append(j+[j[-1]+a[s]])
  B.append(B[-1]+len(A[i]))
i=0
while k>B[i]:
  i=i+1
for t in range(len(A[i-1][k-B[i-1]])):
  print(A[i-1][k-B[i-1]][t],end="")

Submission status: Accepted

Solution code:
import sys
k = int(input())
keta = 0
for x in range(1,11):
    memo_ls = [[0 if (i != 0 or j == 0) else 1 for j in range(10)] for i in range(x)]
    for i in range(1, x):
        for j in range(10):
            memo_ls[i][j] = memo_ls[i-1][j]
            if j > 0:
                memo_ls[i][j] += memo_ls[i-1][j-1]
            if j < 9:
                memo_ls[i][j] += memo_ls[i-1][j+1]
    _sum = sum(memo_ls[-1])
    if _sum >= k:
        keta = x
        break
    else:
        k -= _sum
res = ""
cur_k = k
for start in range(keta, 0, -1):
    last_k = cur_k
    if res == "":
        ls = list(range(1, 10))
    else:
        if 9 > int(res[-1]) > 0:
            ls = [int(res[-1]) - 1, int(res[-1]), int(res[-1]) + 1]
        elif int(res[-1]) > 0:
            ls = [int(res[-1]) - 1, int(res[-1])]
        else:
            ls = [int(res[-1]), int(res[-1]) + 1]
    for i in ls:
        memo_ls = [[0 for i in range(10)] for j in range(start)]
        memo_ls[0][i] = 1
        for ind_keta in range(1, start):
            for j in range(10):
                memo_ls[ind_keta][j] = memo_ls[ind_keta - 1][j]
                if j > 0:
                    memo_ls[ind_keta][j] += memo_ls[ind_keta - 1][j - 1]
                if j < 9:
                    memo_ls[ind_keta][j] += memo_ls[ind_keta - 1][j + 1]
        if sum(memo_ls[-1]) >= cur_k:
            res += str(i)
            break
        else:
            if i == 9:
                res += "0"
                cur_k = last_k
            cur_k -= sum(memo_ls[-1])
print(res)

Submission status: Accepted

Solution code:
k = int(input())

ans = [-10]*11
ans[0] = 1
c = 1
for i in range(k - 1):
    for j in range(c):
        if ans[j] == 9 and ans[j + 1] == -10:
            c += 1
            ans[j + 1] = 1
            for l in range(c - 1):
                ans[l] = 0
            break
        elif ans[j] == 9 or (ans[j] > ans[j + 1] and ans[j + 1] != -10):
            continue
        else:
            ans[j] += 1
            for l in range(j - 1,-1,-1):
                ans[l] = max(0,ans[l + 1] - 1)
            break

for i in range(len(ans)-1,-1,-1):
    if ans[i] == -10:continue
    print(ans[i],end="")
print()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    K = int(input())
    num_list = list(range(0, 10))
    def bfs():
        q = deque(list(map(str, num_list)))
        
        while len(num_list) < 2 * 10**6:
            now_str = q.popleft()
            now = int(now_str[0])
            for j in [now-1, now, now+1]:
                if j not in [-1, 10]:
                    new = str(j) + now_str
                    q.append(new)
                    if j != 0:
                        num_list.append(int(new))
    
    bfs()
    print(sorted(set(num_list))[K])
            
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K = int(input())

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

for keta in range(10):
    for i in range(len(run)):
        x = run[i] // 10**keta
        if x == 0:
            if int(str(run[i])[0]) > 1:
                continue
        for j in range(max(x-1, 1), min(10, x+2)):
            run.append(run[i] + j*10**(keta+1))


run.sort()
print(run[K])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# vim:fenc=utf-8 ff=unix

def nextRR(N):
    for i in range(0, len(N)-1):
        if (N[i] <= N[i+1]) and N[i] != 9:
            m = N[i] + 1
            for j in range(i, -1, -1):
                N[j] = m
                if m > 0:
                    m -= 1
            return N

    if N[-1] == 9:
        N = [0] * len(N) + [1]
        return N

    m = N[-1] + 1
    for i in range(len(N)-1, -1, -1):
        N[i] = m
        if m > 0:
            m -= 1
    return N


def solv(K):
    if K <= 12:
        return str(K)
    N = [1, 2]
    for i in range(13, K):
        N = nextRR(N)
    return "".join(map(str, reversed(N)))


if __name__ == "__main__":
    K = int(input())
    ans = solv(K)
    print(ans)

Submission status: Accepted

Solution code:
N =int(input())
L = [i for i in range(1,10)]
M = L.copy()
for i in range(11):
  S = []
  for x in L:
    if x % 10 == 0:
      S.append(x*10)
      S.append(x*10 + 1)
    elif x % 10 == 9:
      S.append(x*10 + 8)
      S.append(x*10 + 9)
    else:
      S.append(x*10 + x % 10 - 1)
      S.append(x*10 + x % 10)
      S.append(x*10 + x % 10 + 1)
  L = S.copy()
  M += S
print (sorted(M)[N-1])

Submission status: Accepted

Solution code:
K = input()

A = [1]
for k in range(K-1):
  for d in range(len(A)-1):
    if A[d]<9 and A[d]<=A[d+1]:
      A[d] += 1
      for i in range(d)[::-1]:
        A[i] = max(0, A[i+1]-1)
      break
  else:
    if A[-1]<9:
      A[-1]+=1
      for i in range(len(A)-1)[::-1]:
        A[i] = max(0, A[i+1]-1)
    else:
      for i in range(len(A)):
        A[i] = 0
      A += [1]
print "".join(map(str, A[::-1]))

Submission status: Accepted

Solution code:
K = int(input())

runrun = [[1]*10]
s = sum(runrun[0][1:])
i = 1
while K > s:
  K -= s
  r = [sum(runrun[-1][max(0,i-1):min(10, i+2)]) for i in range(10)]
  runrun.append(r)
  s = sum(r[1:])
  i += 1

j = 1
while runrun[-1][j] < K:
  K -= runrun[-1][j]
  j += 1

ans = [j]
k = -2
while K and len(runrun) >= -k:
  j = max(0, j-1)
  while runrun[k][j] < K:
    K -= runrun[k][j]
    j += 1
  k -= 1
  ans.append(j)

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify
K = int(input())
M = K

que = list(range(1, 10))
V = set()
heapify(que)

while M + 100 >= 0:
    top = heappop(que)
    if top in V:
        continue
    V.add(top)
    M -= 1

    top = str(top)
    L = int(top[0])
    R = int(top[-1])

    for i in (L - 1, L, L + 1):
        if 1 <= i <= 9:
            heappush(que, int(str(i) + top))
    for i in (R - 1, R, R + 1):
        if 0 <= i <= 9:
            heappush(que, int(top + str(i)))

V = [int(d) for d in V]
V.sort()
print(V[K - 1])

Submission status: Accepted

Solution code:
K=int(input())
tmp=[1,2,3,4,5,6,7,8,9]
while True:
  k=len(tmp)
  if K<=k:
    print(tmp[K-1])
    break
  else:
    K-=k
    dum=tmp[:]
    tmp=[]
    for a in dum:
      if a%10==0:
        tmp.append(a*10+0)
        tmp.append(a*10+1)
      elif a%10==9:
        tmp.append(a*10+8)
        tmp.append(a*10+9)
      else:
        tmp.append(a*10+a%10-1)
        tmp.append(a*10+a%10)
        tmp.append(a*10+a%10+1)

Submission status: Accepted

Solution code:
def search(i,d,run,md,mrun):
    if d==md:
        run[0]+=1
        if run[0]==mrun:
            return str(i)
        else:
            return -1

    elif i==0:
        s=search(0,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
        s=search(1,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
    elif i==9:
        s=search(8,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
        s=search(9,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
    else:
        s=search(i-1,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
        s=search(i,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
        s=search(i+1,d+1,run,md,mrun)
        if s !=-1:
            return(str(i)+s)
    
    return -1

N=int(input())

digit=1
run=[0]

# max digit = 10
for d in range(1,11):
    for i in range(1,10):
        a=search(i,1,run,d,N)
        if a !=-1:
            print(a)
            break

Submission status: Accepted

Solution code:
K = int(input())

dp = [[str(i)] for i in range(1, 10)]
count = 9

ansFlag = False
while (True):
    if K <= 9:
        break
    for i in range(9):
        numList = dp[i]
        newNumList = []
        for n in numList:
            lastNum = n[-1]
            if int(lastNum) >= 1:
                newNum1 = str(n) + str(int(lastNum) - 1)
                count += 1
                newNumList.append(newNum1)
                if count == K:
                    ansFlag = True
                    break

            newNum2 = str(n) + str(int(lastNum))
            count += 1
            newNumList.append(newNum2)
            if count == K:
                ansFlag = True
                break

            if int(lastNum) <= 8:
                newNum3 = str(n) + str(int(lastNum) + 1)
                count += 1
                newNumList.append(newNum3)
                if count == K:
                    ansFlag = True
                    break
        if ansFlag:
            break
        dp[i] = newNumList
    if ansFlag:
        break

ans = K
if K >= 10:
    ans = newNumList[-1]

print(ans)

Submission status: Accepted

Solution code:
k = int(input())
import sys
c = 0
A = []
for i in range(10):
    for t in range(1, 10):
        if i == 0:
            c += 1
            anss = t
            # print(anss, c)
            if c == k:
                print(anss)
                sys.exit()
        else:
            
            for j in range(3**i):
                jj = j
                j3 = [0] * i
                for p in range(i-1,-1,-1):
                    j3[p] = jj%3-1
                    jj//=3
                # print(j3)
                ng = 0
                tt = t
                ans = [tt]
                # print(j3)
                for p in range(i):
                    tt += j3[p]
                    ans.append(tt)
                    if tt < 0 or tt >= 10:
                        ng = 1
                        break
                # print(j3, ans,ng,c)
                if ng == 0:
                    c += 1
                    anss = "".join([str(ij) for ij in ans])
                # print(anss, c)
                if c == k:
                    print(anss)
                    sys.exit()

Submission status: Accepted

Solution code:
K = int(input())

rnrn = list(range(10))

idx = 0
for idx_base in range(0, K + 1):
    base = rnrn[idx_base]
    for d in (-1, 0, 1):
        digit = base % 10 + d
        if digit < 0 or 9 < digit: continue
        if base == 0: continue
        rnrn.append(10 * base + digit)
        if len(rnrn) >= K + 1: break
    if len(rnrn) >= K + 1: break

# print("#", rnrn)
print(rnrn[K])

# なんでや！阪神関係無いやろ！

Submission status: Accepted

Solution code:
n = int(input())
l = [1,2,3,4,5,6,7,8,9]
if(n<=9):
    print(l[n-1])
else:
    i=9
    j=0
    while(i<n):
        s = str(l[j])
        a = int(s[-1])
        b = l[j]*(10)
        if(a==9):
            l.append(b+(a-1))
            l.append(b+a)
            i+=2
        elif(a==0):
            l.append(b+a)
            l.append(b+(a+1))
            i+=2
        else:
            l.append(b+(a-1))
            l.append(b+a)
            l.append(b+(a+1))
            i+=3
        j+=1
    print(l[n-1])

Submission status: Accepted

Solution code:
k = int(input())

def hantei(n):
    string = str(n)
    length = len(string)
    ret = True
    for i in range(length-1):
        if abs(int(string[i]) - int(string[i+1])) > 1:
            ret = False
            break
    return ret

lst = [i for i in range(10)]
dic = {}
dic[1] = lst.copy()
keta = 2
while len(lst) < k+1:
    new = []
    for i in range(1, 10):
        tasu = i*(10**(keta-1))
        for j in sorted(dic.keys()):
            temp_lst = dic[j]
            bit = 0
            for youso in temp_lst:
                num = tasu + youso
                if hantei(num):
                    new.append(num)
                    bit = 1
                elif bit == 1:
                    break
    dic[keta] = new.copy()
    lst.extend(new)
    keta += 1

print(lst[k])

Submission status: Accepted

Solution code:

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import os

sys.setrecursionlimit(500*500)

runc=0

def tonari(n,x,keta,k):
    #print(n,end="")
    #print(" ",end="")
    #print(x,end="")
    #print(" ",end="")
    #print(keta)
    global runc
    if keta==1:
        runc+=1
        if runc==k:
            print(n)
            sys.exit()
        return 0

    if x==0:
        yy=[0,1]
    elif x==9:
        yy=[8,9]
    else:
        yy=[x-1,x,x+1]
    for y in yy:
        #rint(y)
        tonari(n+y*(10**(keta-2)),y,keta-1,k)
        #if res!=0:
        #    return res

    

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    k=int(readline())

    for keta in range(1,100):
        for i in range(1,10):
            tonari(i*(10**(keta-1)),i,keta,k)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    k = int(args[0])

    ret = 0
    count = 0
    prev = []
    while not ret:
        cur = []
        for i in range(10):
            c = str(i)
            if len(prev):
                for p in prev:
                    if abs(ord(p[0])-ord(c)) <= 1:
                        cur.append(c+p)
                        if c != '0':
                            count += 1
                            if count == k:
                                ret = c+p
            else:
                cur.append(c)
                if c != '0':
                    count += 1
                    if count == k:
                        ret = c
        prev = cur

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
lis = {1,2,3,4,5,6,7,8,9,10}
def dfs(x):
    d = ['-1','0','1']
    que = deque([x])
    cnt = 1
    while len(que) != 0:
        val = que.pop()
        #print(val)
        val3 = str(val)
        if len(str(val)) < 10:
            #print(len(str(val)))
            for i in range(3):
                val2 = int(val3[-1]) + int(d[i])
                #print(val3[-1])
                if val2 >= 0 and val2 < 10:
                    lis.add(int(str(val) + str(val2)))
                    que.append(int(str(val) + str(val2)))
        else:
            lis.add(val)
    return lis
for i in range(1,10):
    ans = dfs(i)
lis = list(lis)
lis.sort()
#print(len(lis))
#print(lis)
#print('3'.join('4'))
#print(lis[:20])
print(lis[k-1])
#print(lis[k])

Submission status: Accepted

Solution code:
k = int(input())
if k < 10:
    print(k)
else:
    k -= 9
    run= {}
    run[1] = {i: 1 for i in range(0, 10)}
    now_dig = 1
    flag = 0
    flag2 = 0
    ans = 0
    while flag == 0:
        now_dig += 1
        run[now_dig] = {}
        for num in range(0, 10):
            if num == 0:
                run[now_dig][num] = run[now_dig-1][num] + run[now_dig-1][num+1]
            elif num == 9:
                run[now_dig][num] = run[now_dig-1][num-1] + run[now_dig-1][num]
            else:
                run[now_dig][num] = run[now_dig-1][num-1] + run[now_dig-1][num] + run[now_dig-1][num+1]
            if num != 0 and k - run[now_dig][num] > 0:
                k -= run[now_dig][num]
            elif num != 0:
                flag = 1
                # print(k, now_dig, num)
                ans += num*pow(10, now_dig-1)
                while now_dig > 1:
                    now_dig -= 1
                    if num == 0:
                        now_num = 0
                        end = 1
                    elif num == 9:
                        now_num = 8
                        end = 9
                    else:
                        now_num = num - 1
                        end = num + 1
                    while k - run[now_dig][now_num] > 0 and now_num <= end:
                        k -= run[now_dig][now_num]
                        now_num += 1
                    ans += now_num*pow(10, now_dig-1)
                    num = now_num
                break
        # print(now_dig, run[now_dig])

    print(ans)

Submission status: Accepted

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

cnt = 9
keta = 0
dp_num = 0
while True:
    num = 2
    current_base_num_str = dp[keta][dp_num][-1]
    current_base_num_int = int(current_base_num_str)
    break_flag = False
    for i in range(-1,num):
        if current_base_num_int + i > 9 or current_base_num_int + i < 0:
            continue
        dp[keta+1].append(dp[keta][dp_num] + str(current_base_num_int + i))
        cnt += 1
        if cnt >= K:
            break_flag = True
            break
    if break_flag:
        break
    if dp_num < len(dp[keta])-1:
        dp_num += 1
    else:
        dp_num = 0
        keta += 1
        dp.append([])
if K < 10:
    print(K)
else:
    if len(dp[keta+1]) == 0:
        print(dp[keta][-1])
    else:
        print(dp[keta+1][-1])

Submission status: Accepted

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

STEP = [-1,0,1]

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

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

    l = [x for x in range(1,10)]
    c = 9

    while True:
        nxt = []
        for x in l:
            tail = int(str(x)[-1])
            for diff in STEP:
                if tail + diff >= 0 and tail + diff < 10:
                    c += 1
                    nxt.append(int(str(x) + str(tail + diff)))
                    if c == K:
                        print(nxt[-1])
                        exit()
        l = nxt



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
"""
NTC here
"""
import sys
inp = sys.stdin.readline
def input(): return inp().strip()
# flush= sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**26)
 
def iin(): return int(input())
 
 
def lin(): return list(map(int, input().split()))
 
 
# range = xrange
# input = raw_input
 
def main():
    T = 1
    while T:
        T-=1
        k = iin()
        ans = [[0 for i in range(10)] for j in range(10)]
        for i in range(10):
            ans[0][i]=1
        for i in range(1, 10):
            for j in range(10):
                sm = ans[i-1][j]
                if j-1>=0:
                    sm+=ans[i-1][j-1]
                if j+1<10:
                    sm+=ans[i-1][j+1]
                ans[i][j] = sm
        # print(*ans, sep = '\n')
        br = 0
        i1, j1 = 0, 1
        for i in range(10):
            if br:break
            for j in range(1, 10):
                # print(i, j, k)
                if k<=ans[i][j]:
                    i1, j1 = i, j
                    br = 1
                    break
                else:
                    k-=ans[i][j]
        # print(i1, j1)
        sol = [str(j1)]
        for i in range(i1-1, -1, -1):
            chk = ([j1-1] if j1-1>=0 else []) + [j1] + ([j1+1] if j1+1<10 else [])
            for j in chk:
                if k<=ans[i][j]:
                    sol.append(str(j))
                    j1 = j
                    break
                else:
                    k-=ans[i][j]
        print(''.join(sol))





 
 
 
 
main()
 
# threading.Thread(target=main).start()

Submission status: Accepted

Solution code:
from collections import deque
def main():
    q=deque()
    for i in range(1,10):
        q.append((str(i)))
    Ans=[]
    while q:
        s=q.popleft()
        if int(s)>3234566667:
            continue
        Ans.append(int(s))
        d=int(s[-1])
        if d==0:
            q.append(s+'0')
            q.append(s+'1')
        elif d==9:
            q.append(s+'8')
            q.append(s+'9')
        else:
            V=[d-1,d,d+1]
            for v in V:
                q.append(s+str(v))
    Ans.sort()
    #print(len(Ans))
    k=int(input())
    print(Ans[k-1])
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
K=int(input())
l=[]
for i in range(10):
    r=[]
    if (i-1)<0:
        pass
    else:
        r.append(str(i-1))
    r.append(str(i))
    if (i+1)>9:
        pass
    else:
        r.append(str(i+1))
    l.append(r)
lst=[]
count=0
for i in range(1,10):
    lst.append(str(i))
    count+=1
queue=lst[0]
tmp=0
while(1):
    queue=lst[tmp]
    s=queue[-1]
    num=int(s)
    for i in range(len(l[num])):
        s=queue
        s=s+l[num][i]
        lst.append(s)
        count+=1
    tmp+=1
    if count>=K:
        break
print(lst[K-1])

Submission status: Accepted

Solution code:
k = int(input())
len_map = dict()
cur = [i for i in range(1,10)] # cur list
total = cur
counter = 9
cur_digit_len = 1
while counter < 10**5:
    tmp = []
    for sample in cur:
        sample_str = str(sample)
        if int(sample_str[-1]) > 0:
            tmp.append(int(sample_str + str(int(sample_str[-1])-1)))
        tmp.append(int(sample_str + sample_str[-1]))
        if int(sample_str[-1]) < 9:
            tmp.append(int(sample_str + str(int(sample_str[-1])+1)))
    total.extend(tmp)
    counter += len(tmp)
    cur = tmp
print(total[k-1])