Problem:


Score : 400 points

Problem Statement

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

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

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

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

Constraints

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer.

Sample Input 1

15

Sample Output 1

23

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

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

Thus, the answer is 23.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

13

Sample Output 3

21

Sample Input 4

100000

Sample Output 4

3234566667

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



Sample input:
15


Sample output:
23

Submission status: Accepted

Solution code:
K = int(input())
from collections import deque

queue = deque()
for i in range(1, 10):
    queue.appendleft(i)

for _ in range(K-1):
    p = queue.pop()
    if p%10!=0:
        queue.appendleft(p*10+p%10-1)
    queue.appendleft(p*10+p%10)
    if p%10!=9:
        queue.appendleft(p*10+p%10+1)

print(queue.pop())

Submission status: Accepted

Solution code:
import sys
from _collections import deque

K = int(input())
c = 9
A = [1,2,3,4,5,6,7,8,9]
q = deque(A)

if K <= 9:
    print(K)
else:
    while(True):
        a = q.popleft()
        if a % 10 == 0:
            c += 1
            if c == K:
                print(a*10)
                sys.exit()
            q.append(a*10)
            c += 1
            if c == K:
                print(a*10+1)
                sys.exit()
            q.append(a*10+1)
        elif a % 10 == 9:
            c += 1
            if c == K:
                print(a*10+9-1)
                sys.exit()
            q.append(a*10+9-1)
            c += 1
            if c == K:
                print(a*10+9)
                sys.exit()
            q.append(a*10+9)
        else:
            c += 1
            if c == K:
                print(a*10+a%10-1)
                sys.exit()
            q.append(a*10+a%10-1)
            c += 1
            if c == K:
                print(a*10+a%10)
                sys.exit()
            q.append(a*10+a%10)
            c += 1
            if c == K:
                print(a*10+a%10+1)
                sys.exit()
            q.append(a*10+a%10+1)

Submission status: Accepted

Solution code:
X = []
for a in range(1, 10):
    X.append(a)
    for b in range(10):
        if abs(b-a) > 1: continue
        X.append(a * 10 + b)
        for c in range(10):
            if abs(c-b) > 1: continue
            X.append(a * 10 ** 2 + b * 10 + c)
            for d in range(10):
                if abs(d-c) > 1: continue
                X.append(a * 10 ** 3 + b * 10 ** 2 + c * 10 + d)
                for e in range(10):
                    if abs(e-d) > 1: continue
                    X.append(a * 10 ** 4 + b * 10 ** 3 + c * 10 ** 2 + d * 10 + e)
                    for f in range(10):
                        if abs(f-e) > 1: continue
                        X.append(a * 10 ** 5 + b * 10 ** 4 + c * 10 ** 3 + d * 10 ** 2 + e * 10 + f)
                        for g in range(10):
                            if abs(g-f) > 1: continue
                            X.append(a * 10 ** 6 + b * 10 ** 5 + c * 10 ** 4 + d * 10 ** 3 + e * 10 ** 2 + f * 10 + g)
                            for h in range(10):
                                if abs(h-g) > 1: continue
                                X.append(a * 10 ** 7 + b * 10 ** 6 + c * 10 ** 5 + d * 10 ** 4 + e * 10 ** 3 + f * 10 ** 2 + g * 10 + h)
                                for i in range(10):
                                    if abs(i-h) > 1: continue
                                    X.append(a * 10 ** 8 + b * 10 ** 7 + c * 10 ** 6 + d * 10 ** 5 + e * 10 ** 4 + f * 10 ** 3 + g * 10 ** 2 + h * 10 + i)
                                    for j in range(10):
                                        if abs(j-i) > 1: continue
                                        X.append(a * 10 ** 9 + b * 10 ** 8 + c * 10 ** 7 + d * 10 ** 6 + e * 10 ** 5 + f * 10 ** 4 + g * 10 ** 3 + h * 10 ** 2 + i * 10 + j)

print(sorted(X)[int(input()) - 1])

Submission status: Accepted

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

     runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     count = 0
     while(len(runrun) < k):
          target = runrun[count]
          num = target % 10
          if num != 0:
               runrun.append(target * 10 + num - 1)
          runrun.append(target * 10 + num)
          if num != 9:
               runrun.append(target * 10 + num + 1)

          count += 1

     print(runrun[k-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

k = ni()
que = deque()
for i in range(1, 10):
    que.append(i)
ct = 0
for i in range(k):
    x = que.popleft()
    if x % 10 != 0:
        que.append(10*x+x%10-1)
    que.append(10*x+x%10)
    if x % 10 != 9:
        que.append(10*x+x%10+1)
print(x)

Submission status: Accepted

Solution code:
# solution
k=int(input())

from collections import deque
todo = deque([i for i in range(1, 10)])
count = 0

while len(todo) > 0:
    value = todo.popleft()
    value_digit1 = value % 10
    count += 1
    if count == k:
        print(value)
        break
    if value_digit1==0:
        todo.append(10*value)
        todo.append(10*value+1)
    elif value_digit1==9:
        todo.append(10*value+8)
        todo.append(10*value+9)
    else:
        todo.append(10*value+value_digit1-1)
        todo.append(10*value+value_digit1)
        todo.append(10*value+value_digit1+1)

Submission status: Accepted

Solution code:
import queue

K = int(input())

q=queue.Queue()
for i in range(1,10):
    q.put(i)

for _ in range(K):
    x = q.get(0)
    #print(x)
    if x % 10 != 0:
        q.put(x*10 + x%10 - 1)
    q.put(x*10 + x%10)
    if x % 10 != 9:
        q.put(x*10 + x%10 + 1)
print(x)

Submission status: Accepted

Solution code:
a = []

def dfs(n):
    if n > 3234566667:
        return

    a.append(n)
    for i in range(10):
        if abs(n%10 - i) <= 1:
            dfs(n*10+i)

for i in range(1, 10):
    dfs(i)

k = int(input())
a = sorted(a)
print(a[k-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

tree = deque([[-1, i] for i in range(1, 10)])
i = 0
cnt = 9

while cnt <= K:
    n = tree[i][1]
    if n > 0:
        tree.append([i, n - 1])
        cnt += 1
    tree.append([i, n])
    cnt += 1
    if n < 9:
        tree.append([i, n + 1])
        cnt += 1
    i += 1

ans = ""
j = K - 1

while True:
    j, b = tree[j]
    ans = str(b) + ans
    if j == -1:
        break

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

q = deque(range(1,10))
K = int(input())

for i in range(K):
    x = q.popleft()
    r =  x % 10
    if r != 0:
        q.append((10 * x) + (r - 1))
    q.append((10 * x) + r)
    if r != 9:
        q.append((10 * x) + (r + 1))

print(x)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

q = deque(range(1, 10))
for _ in range(k):
    x = q.popleft()
    if x % 10 != 0:
        q.append(x*10 + x%10 - 1)
    q.append(x*10 + x%10)
    if x % 10 != 9:
        q.append(x*10 + x%10 + 1)

print(x)

Submission status: Accepted

Solution code:
from collections import deque
K=int(input())
lun=deque([1,2,3,4,5,6,7,8,9])
for i in range(K):
    x=lun.popleft()
    if x%10!=0:
        lun.append(10*x+x%10-1)
    lun.append(10*x+x%10)
    if x%10!=9:
        lun.append(10*x+x%10+1)
print(x)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

list = deque(range(1,10))
i = 0
for i in range(K):
    v = list.popleft()

    t = v%10

    if t != 0:
        list.append(10*v + (t-1))

    list.append(10*v + t)

    if t != 9:
        list.append(10*v + (t+1))


print(v)

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())

que = deque(range(1, 10))
for _ in range(K):
    x = que.popleft()
    target = x%10
    num = x*10 + target
    if target != 0:
        que.append(num-1)
    que.append(num)
    if target != 9:
        que.append(num+1)
print(x)

Submission status: Accepted

Solution code:
def lower(upper):
    if upper==9:
        return [8,9]
    elif upper==0:
        return [0,1]
    else:
        return [upper-1,upper,upper+1]

def numerize(a):
    return sum([a[i]*(10**i) for i in range(len(a))])

def getRunruns(digit):
    if digit==1:
        return [(i,) for i in range(10)]
    elif digit==2:
        return [(k,i) for i in range(1,10) for k in lower(i)]
    else:
        runruns=getRunruns(2)
        for i in range(digit-2):
            runruns=[(k,)+i for i in runruns for k in lower(i[0])]
        return runruns

A1=[(i,) for i in range(10)]
A2=[(k,i) for i in range(1,10) for k in lower(i)]
A=A1+A2
Aprev=A2
K=int(input())
while len(A)<K+1:
    Aprev=[(k,)+i for i in Aprev for k in lower(i[0])]
    A+=Aprev
print(numerize(A[K]))

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
q = deque(list(range(1,10)))
x = 0
for i in range(1, K+1):
    x = q.popleft()
    xs = str(x)
    if xs[-1] != '0':
        add_n = int(xs + str(int(xs[-1]) - 1))
        q.append(add_n)
    add_n = int(xs + str(int(xs[-1])))
    q.append(add_n)
    if xs[-1] != '9':
        add_n = int(xs + str(int(xs[-1]) + 1))
        q.append(add_n)
print(x)

Submission status: Accepted

Solution code:
from collections import deque

K=int(input())
# BFS
M=0
L=9
tmp=deque([1,2,3,4,5,6,7,8,9])
while L<K:
    k=str(tmp.popleft())
    if int(k[-1])-1>=0:
        tmp.append(int(k+str(int(k[-1])-1)))
        L+=1
    tmp.append(int(k+k[-1]))
    L+=1
    if int(k[-1])+1<10:
        tmp.append(int(k+str(int(k[-1])+1)))
        L+=1
    M+=1# 取り出した数

print(tmp[K-1-M])

Submission status: Accepted

Solution code:
import queue

K = int(input())
L = queue.Queue()

for i in range(1,10):
  L.put(i)
for i in range(K-1):
  x = L.get()
  p = 10*x
  m = x%10
  if m != 0:
    L.put(p+m-1)
  L.put(p+m)
  if x%10 != 9:
    L.put(p+m+1)
print(L.get())

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
q = deque(list(range(1, 10)))
for _ in range(k-1):
	d = q.popleft()
	if d%10 > 0:
		q.append(d*10 + d%10 - 1)
	q.append(d*10 + d%10)
	if d%10 < 9:
		q.append(d*10 + d%10 + 1)
print(q.popleft())

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

ans = deque([i for i in range(1, 10)])

for i in range(k):
    x = ans.popleft()
    modx = x%10
    if modx != 0:
        ans.append(x*10 + modx - 1)
    ans.append(x*10 + modx)
    if modx != 9:
        ans.append(x*10 + modx + 1)
print(x)

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())


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

count = 100000

while K > 0:
    a = q.popleft()

    if count > 0:
        if a % 10 == 0:
            q.append(10 * a)
            q.append(10 * a + 1)
            count -= 2
        elif a % 10 == 9:
            q.append(10*a + 8)
            q.append(10*a + 9)
            count -= 2
        else:
            b = a % 10
            q.append(10*a + b-1)
            q.append(10*a + b)
            q.append(10*a + b+1)
            count -= 3
    K -= 1
print(a)

Submission status: Accepted

Solution code:
def d_lunlun_number():
    from collections import deque
    K = int(input())

    queue = deque(range(1, 10))
    ans = -1
    for _ in range(K):
        ans = queue.popleft()
        lsd = ans % 10  # least significant digit
        if lsd != 0:
            queue.append(10 * ans + (lsd - 1))
        queue.append(10 * ans + lsd)
        if ans % 10 != 9:
            queue.append(10 * ans + (lsd + 1))
    return ans

print(d_lunlun_number())

Submission status: Accepted

Solution code:
k=int(input())
t=[2]+[3]*8+[2]
g=[[1]+[0for i in range(9)]for j in range(100)]
def f(x,y):
    if g[x][y]!=0:
        return g[x][y]
    else:
        p=0
        for i in range(x-1,x+2):
            if 0<=i<10:
                p+=f(i,y-1)
        g[x][y]=p
        return p
c=0
for i in range(10):
    for j in range(1,10):
        if c+f(j,i)>=k:
            p=str(j)
            po=j
            for h in range(i-1,-1,-1):
                for w in range(po-1,po+2):
                    if 0<=w<10:
                        if c+f(w,h)>=k:
                            p+=str(w)
                            po=w
                            break
                        c+=f(w,h)
            print(p)
            exit()
        c+=f(j,i)

Submission status: Accepted

Solution code:
from queue import Queue

k = int(input())

q = Queue()
for i in range(1, 10):
    q.put(i)

for _ in range(k):
    x = q.get()
    if x % 10 != 0:
        q.put(x*10 + x%10 - 1)
    q.put(x*10 + x%10)
    if x % 10 != 9:
        q.put(x*10 + x%10 + 1)

print(x)

Submission status: Accepted

Solution code:
k = int(input())

a = ["1","2","3","4","5","6","7","8","9"]
i = 0
while len(a)<=k:
  b = a[i]
  c = int(b[-1])
  i += 1
  for j in range(-1,2):
    if 0<=c+j<10:
      a.append(b+str(c+j))

print(a[k-1])

Submission status: Accepted

Solution code:
k=int(input())
cand=[[1,2,3,4,5,6,7,8,9]]
for _ in range(9):
  tmp=[]
  for val in cand[-1]:
    if val%10!=0:
      tmp.append(val*10+(val%10-1))
    tmp.append(val*10+(val%10))
    if val%10!=9:
      tmp.append(val*10+(val%10+1))
  cand.append(tmp)
ans=[]
for i in range(len(cand)):
  for val in cand[i]:
    ans.append(val)
ans=sorted(ans)
print(ans[k-1])

Submission status: Accepted

Solution code:
def main():
    from collections import deque

    K = int(input())
    q = deque(range(1, 10))
    for _ in range(K):
        x = q.popleft()
        lastdigit = x%10
        base = x*10 + lastdigit
        if lastdigit != 0:
            q.append(base-1)
        q.append(base)
        if lastdigit != 9:
            q.append(base+1)
    print(x)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
d = deque([1,2,3,4,5,6,7,8,9])

for i in range(k):
    x = d.popleft()
    if x % 10 != 0:
        d.append(10 * x + x % 10 - 1)

    d.append(10 * x + x % 10)
    
    if x % 10 != 9:
        d.append(10 * x + x % 10 + 1)

print(x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

k=ii()
ans=0
arr=deque([1,2,3,4,5,6,7,8,9])
while k>ans:
    n=int(arr.popleft())
    if n%10==9:
        arr.append(n*10 + n%10 -1)
        arr.append(n*10 + n%10 )
    elif n%10==0:
        arr.append(n*10 + n%10)
        arr.append(n*10 + n%10+1)
    else:
        arr.append(n*10 + n%10 -1)
        arr.append(n*10 + n%10)
        arr.append(n*10 + n%10 +1)
    ans+=1
print(n)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    k=int(input())
    if k<=9:
        return k
    q=deque()
    for i in range(1,10):
        q.append(i)
    Ans=list(range(1,10))
    cnt=9
    while cnt<k:
        s=q.popleft()
        d=s%10
        s*=10
        if d==0:
            q.append(s)
            q.append(s+1)
            Ans.append(s)
            Ans.append(s+1)
            cnt+=2
        elif d==9:
            q.append(s+8)
            q.append(s+9)
            Ans.append(s+8)
            Ans.append(s+9)
            cnt+=2
        else:
            V=[d-1,d,d+1]
            for v in V:
                q.append(s+v)
                Ans.append(s+v)
            cnt+=3
    return Ans[k-1]
    
if __name__=='__main__':
    print(main())

Submission status: Accepted

Solution code:
K = int(input())

def nextrun(A):
    bflag = 1
    for i in range(len(A)-1):
        if A[-i-1] != 9 and A[-i-1] <= A[-i-2]:
            A[-i-1] += 1
            for k in range(i):
                A[-i-1+k+1] = max(A[-i-1+k] - 1,0)
            bflag = 0
            return A
    #一番大きい位まで進んだとき
    if bflag:
        if A[0] != 9:
            A[0] += 1
            for k in range(len(A)-1):
                A[-i-1-1+k+1] = max(A[-i-1-1+k] - 1,0)    
        else:
            B = [0]*(len(A)+1)
            B[0] = 1
            A = B
        return A
            
A = [0]
for i in range(K):
    A = nextrun(A)
print(''.join(map(str, A)))

Submission status: Accepted

Solution code:
import queue

k = int(input())

q = queue.Queue()
for i in range(1,10):
    q.put(i)

for i in range(k):
    x = q.get()

    p = 10 * x  
    m = x % 10
    if not m == 0:
        q.put(p + m - 1)

    q.put(p + m)

    if not m == 9:
        q.put(p + m + 1)
    
print(x)

Submission status: Accepted

Solution code:
K = int(input())
ans = [0]
def f(n):
    tmp = str(n)
    if int(n) > 3234566667:
        return
    else:
        ans.append(int(n))
    f(str(tmp)+tmp[-1])
    if int(tmp[-1])-1 >= 0:
        f(str(tmp)+str(int(tmp[-1])-1))
    if int(tmp[-1])+1 <= 9:
        f(str(tmp)+str(int(tmp[-1])+1))
for i in range(1,10):
    f(i)
ans.sort()
print(ans[K])

Submission status: Accepted

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

K = int(input())
q = queue.Queue()
for i in range(1,10):
    q.put(i)

i = 1
while True:
    r = q.get()
    if ( r % 10 != 0 ):
        q.put(10 * r + int(str(r)[-1]) -1)
    q.put(10*r + int(str(r)[-1]))
    if ( r % 10 != 9 ):
        q.put(10 * r + int(str(r)[-1]) + 1)

    if (i == K):
        print(r)
        break
    i += 1

Submission status: Accepted

Solution code:
import queue
k = int(input())

q = queue.Queue()
for i in range(1, 10):
    q.put(i)

for i in range(k):
    x = q.get()
    if (x % 10) > 0:
        q.put((10 * x) + (x % 10) - 1)
    q.put(10 * x + (x % 10))
    if (x % 10) < 9:
        q.put((10 * x) + (x % 10) + 1)
print(x)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    K = int(input())
    q = deque([1,2,3,4,5,6,7,8,9])
    for _ in range(K - 1):
        n = q.popleft()
        # print(n)
        if n % 10 == 0:
            q.append(n * 10)
            q.append(n * 10 + 1)
        elif n % 10 == 9:
            q.append(n * 10 + 8)
            q.append(n * 10 + 9)
        else:
            k = n % 10
            q.append(n * 10 + k - 1)
            q.append(n * 10 + k)
            q.append(n * 10 + k + 1)
    print(q[0])


    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
lunlun = [[1,2,3,4,5,6,7,8,9],[],[],[],[],[],[],[],[],[],[]]
for i in range(1,10):
    for x in lunlun[i-1]:
        unit_digit = x % 10
        if unit_digit == 0:
            lunlun[i].append(x*10)
            lunlun[i].append(x*10 + 1)
        elif unit_digit == 9:
            lunlun[i].append(x*10 + 9)
            lunlun[i].append(x*10+8)
        else:
            lunlun[i].append(x*10+unit_digit)
            lunlun[i].append(x*10+unit_digit - 1)
            lunlun[i].append(x*10+unit_digit+1)
        
temp = []
for row in lunlun:
    temp = temp + row
temp.sort()
k = int(input())
print(temp[k-1])

Submission status: Accepted

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

from collections import deque

k = int(input())

que = deque(reversed([i for i in range(1, 10)]))

x = -1
for _ in range(k):
    # print(f"loop: {_}")
    # print(f"que: {que}")
    x = que.pop()
    # print(f"x: {x}\n")
    if x % 10 != 0:
        que.appendleft(x * 10 + x % 10 - 1)
    que.appendleft(x * 10 + x % 10)
    if x % 10 != 9:
        que.appendleft(x * 10 + x % 10 + 1)

print(x)

Submission status: Accepted

Solution code:
import queue
q = queue.Queue()
for i in range(9):
    q.put(i+1)
    
N = int(input())
for _ in range(N):
    x = q.get()
    y = x%10
    if x%10 != 0:
        q.put(10*x + y-1)
    q.put(10*x + y)
    if x%10 != 9:
        q.put(10*x + y+1)
#     print(_, x)
        
print(x)

Submission status: Accepted

Solution code:
k = int(input())
ok = 10**18
ng = 0
while ok-ng>1:
    mid = (ok+ng)//2
    mx = list(map(int, list(str(mid))))
    n = len(mx)
    dp = [[[0]*2 for i in range(10)] for j in range(n+1)]
    for i in range(1, mx[0]):
        dp[1][i][0] = 1

    dp[1][mx[0]][1] = 1
    for i in range(1, n):
        for j in range(10):
            for d in range(10):
                if abs(j-d)<=1:
                    dp[i+1][d][0]+=dp[i][j][0]
            for d in range(mx[i]):
               if abs(j-d)<=1:
                   dp[i+1][d][0]+=dp[i][j][1]
            d = mx[i]
            if abs(j-d)<=1:
                dp[i+1][d][1]+=dp[i][j][1]
        for d in range(1, 10):
            dp[i+1][d][0]+=1
    res = 0
    for d in range(10):
        res+=dp[n][d][0]+dp[n][d][1]
    if res>=k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
from collections import deque
import sys

K = int(input())
q = deque()
if K < 10:
    print(K)
    sys.exit()

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

counta = 9
while K > counta:
    x = q.popleft()
    
    if x % 10 != 0:
        q.append(10 * x + (x % 10) - 1)
        counta += 1
        if K == counta:
            break
    if True:
        q.append(10 * x + (x%10))
        counta += 1
        if K == counta:
            break
    if x % 10 != 9:
        q.append(10 * x + (x%10) + 1)
        counta += 1
        if K == counta:
            break
print(q.pop())

Submission status: Accepted

Solution code:
from collections import deque
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


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

    queue = deque([])
    for i in range(1,10):
        queue.append(i)
    
    for i in range(K):
        x = queue.popleft()
        r = x % 10
        if r != 0:
            queue.append(10*x + r - 1)
        queue.append(10*x + r)
        if x % 10 != 9:
            queue.append(10*x + r + 1)
    
    print(x)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
dic_ref = {k:[k-1,k,k+1] for k in range(10)}
dic_ref = {str(k):''.join([str(x) for x in v if -1<x<10]) for k,v in dic_ref.items()}
k = int(input())
lst = list('123456789')

def generate(lst):
    res = []
    for i in lst:
        for j in dic_ref[i[-1]]:
            res.append(i + j)
    return res
            
while True:
    if k <= len(lst):
        print(int(lst[k-1]))
        break
    else:
        k -= len(lst)
        lst = generate(lst)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

k = inp()
if k < 10:
    print(k)
    quit()

q = deque()
for i in range(9):
    q.append(i+1)
cnt = 10
while True:
    x = q.popleft()
    xx = int(str(x)[-1])
    for i in [-1,0,1]:
        if 0 <= xx+i < 10:
            tmp = x * 10 + xx+i
            if cnt == k:
                print(tmp)
                quit()
            q.append(tmp)
            cnt += 1

Submission status: Accepted

Solution code:
import sys
from collections import deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

K = int(read())

cnt = 0

que = deque([i for i in range(1, 10)])

while len(que) != 0:
    acc = que.popleft()
    cnt += 1

    if cnt == K:
        ans = acc
        break
    acc_ = acc % 10
    if acc_ != 0:
        que.append(acc * 10 + acc_ - 1)
    que.append(acc * 10 + acc_)
    if acc_ != 9:
        que.append(acc * 10 + acc_ + 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

K = ir()
A = deque([x for x in range(1, 10)])
count = 0
while True:
    cur = A.popleft()
    count += 1
    if count == K:
        answer = cur
        break
    next = 10 * cur + (cur % 10)
    if cur % 10 != 0:
        A.append(next-1)
    A.append(next)
    if cur % 10 != 9:
        A.append(next+1)

print(answer)

Submission status: Accepted

Solution code:
import queue
k = int(input())
q = queue.Queue()
for i in range(1,10):
    q.put(i)
for i in range(k):
    x = q.get()

    if x%10 != 0:
        q.put(10*x+x%10-1)
    q.put(10*x+x%10)
    if x%10 != 9:
        q.put(10*x+x%10+1)
print(x)

Submission status: Accepted

Solution code:
import numpy as np

k = int(input())


# ルンルン数で無くても二分探索を怖れない
def check(n):
    digits = []
    while n:
        n, m = divmod(n, 10)
        digits.append(m)
    digits.reverse()

    dp = np.zeros(10, dtype=np.int64)
    dp[1:digits[0]] = 1
    edge = digits[0]
    for d in digits[1:]:
        odp = dp.copy()
        dp[:-1] += odp[1:]
        dp[1:] += odp[:-1]
        dp[1:] += 1
        if edge != -1:
            if edge - 1 > d:
                edge = -1
            elif edge + 1 >= d:
                dp[max(0, edge - 1):d] += 1
                edge = d
            else:
                dp[max(0, edge - 1):edge + 2] += 1
                edge = -1
    result = dp.sum()
    if edge != -1:
        result += 1
    return result >= k


l = 0
r = 3234566667
while l + 1 < r:
    m = (l + r) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)

Submission status: Accepted

Solution code:
#coding:utf-8
from collections import deque
K=int(input())
L=deque([1,2,3,4,5,6,7,8,9])
cnt=0
x=0
for _ in range(K):
	cnt+=1
	x=L.popleft()
	if x%10 !=0:
		L.append(10*x+x%10-1)
	L.append(10*x+x%10)
	if x%10!=9:
		L.append(10*x+x%10+1)

print(x)

Submission status: Accepted

Solution code:
def main():
    k = int(input())
    lun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    cnt = 0
    
    while(len(lun) < k):
        target = lun[cnt]
        mod = target % 10
        if mod != 0:
            lun.append(target*10 + mod - 1)
            
        lun.append(target*10 + mod)
        
        if mod != 9:
            lun.append(target*10 + mod + 1)
        cnt += 1
        
    print(lun[k-1])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import heapq
def main():

    input = stdin.readline

    K = int(input())

    h = []

    for i in range(1,10):
        h.append(i)
    
    for i in range(K):
        ans = h[i]

        if ans % 10 != 0:
            h.append(ans * 10 + (ans % 10 - 1))
        h.append(ans*10 + (ans%10))
        if ans % 10 != 9:
            h.append(ans * 10 + (ans % 10 + 1))
    
    print(ans)

    # for i in range(1,10):
    #     heapq.heappush(h,i)
    
    # for i in range(K):
    #     ans = heapq.heappop(h)

    #     if ans % 10 != 0:
    #         heapq.heappush(h,ans * 10 + (ans % 10 - 1))
    #     heapq.heappush(h,ans*10 + (ans%10))
    #     if ans % 10 != 9:
    #         heapq.heappush(h,ans * 10 + (ans % 10 + 1))
    
    # print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def resolve():
    K = int(input())
    from collections import deque
    cnt = 0
    q = deque()
    for i in range(1, 10):
        q.append(i)
    while q:
        num = q.popleft()
        cnt += 1
        if cnt == K:
            ans = num
            break
        mod10 = num % 10
        if mod10 != 0:
            q.append(10*num + mod10 - 1)
        q.append(10*num+mod10)
        if mod10 != 9:
            q.append(10*num + mod10 + 1)
    print(ans)

resolve()

Submission status: Accepted

Solution code:
#161_D
import heapq
que = [i for i in range(1, 10)]
cnt = 0
k = int(input())

for i in range(k):
    x = heapq.heappop(que)
    if (x % 10) > 0:
        heapq.heappush(que, x * 10 + (x % 10) - 1)
    if (x % 10) < 9:
        heapq.heappush(que, x * 10 + (x % 10) + 1)
    heapq.heappush(que, x * 10 + (x % 10))
    
print(x)

Submission status: Accepted

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

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

     runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     count = 0
     while(len(runrun) < k):
          target = runrun[count]
          runrun.extend(make(target))
          count += 1
          # print(runrun)

     print(runrun[k-1])

def make(n):
     num = n % 10
     if num == 0:
          return [n * 10 + num, n * 10 + num + 1]
     elif num == 9:
          return [n * 10 + num - 1, n * 10 + num]
     else:
          return [n * 10 + num - 1, n * 10 + num, n * 10 + num + 1]

if __name__ == "__main__":
    main()

Submission status: Accepted

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

start = 0
end = 9
while k > len(X):
    for i in range(end-start):
        n = str(X[start+i])
        # print(n)
        if int(n[-1])-1 >= 0:
            X.append(int(n+str(int(n[-1])-1)))
        X.append(int(n+str(n[-1])))
        if int(n[-1])+1 <= 9:
            X.append(int(n+str(int(n[-1])+1)))
    start = end
    end = len(X)
    # print(X)
print(X[k-1])