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:
from collections import deque

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

for _ in range(n):
  ans = queue.popleft()
  x = ans % 10
  if x != 0 :
    queue.append(ans * 10 + x - 1)
  queue.append(ans * 10 + x)
  if x != 9 :
    queue.append(ans * 10 + x + 1)
    
print(ans)

Submission status: Accepted

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

if K <= 10:
    print(K)

else:
    cnt = 9
    l = deque(list(range(1,10)))
    while True:
        a = l.popleft()
        a1 = a% 10
        if a1 != 0:
            a2 = a*10 + a1 - 1
            cnt += 1
            if cnt == K:
                print(a2)
                break
            l.append(a2)
        
        a2 = a*10 + a1
        cnt += 1
        if cnt == K:
            print(a2)
            break
        l.append(a2)

        if a1 != 9:
            a2 = a*10 + a1 + 1
            cnt += 1
            if cnt == K:
                print(a2)
                break
            l.append(a2)

Submission status: Accepted

Solution code:
k = int(input())

ans = 1

def next(n):
    nStr = list(map(int, list(str(n))))

    r = len(nStr)-1
    while r > 0:
        if nStr[r] <= nStr[r-1] and not (nStr[r-1] == 9 and nStr[r] == 9):
            break
        r -= 1

    if r == 0 and nStr[0] == 9:
        nStr = [1] + [0] * len(nStr)
    else:
        extra = len(nStr)-1-r
        nStr = nStr[:r] + [nStr[r]+1]

        for _ in range(extra):
            nStr.append(max(0, nStr[-1]-1))

    return int("".join(map(str, nStr)))

for i in range(k-1):
    ans = next(ans)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
K=int(input())
lunlun=[]
q=deque(list(range(1,10)))
while 1:
    r=q.popleft()
    lunlun.append(r)
    n=str(r)[-1]
    if n!='0':
        q.append(r*10+int(n)-1)
    q.append(r*10+int(n))
    if n!='9':
        q.append(r*10+int(n)+1)
    if len(lunlun)>K:
        break
print(lunlun[K-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

count = 0

while count != K:
    x = d.popleft()
    a = (10 * x) + (x % 10)
    if x % 10 != 0:
        d.append(a - 1)

    d.append(a)

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

    count += 1

print(x)

Submission status: Accepted

Solution code:
def dfs(cnt, num, top):
    if cnt == 10:
        return
    v.add(int(num))
    if top == 0:
        dfs(cnt+1, "0"+num, top)
        dfs(cnt+1, "1"+num, top+1)
    elif top == 9:
        dfs(cnt+1, "8"+num, top-1)
        dfs(cnt+1, "9"+num, top)
    else:
        dfs(cnt+1, str(top-1)+num, top-1)
        dfs(cnt+1, str(top)+num, top)
        dfs(cnt+1, str(top+1)+num, top+1)


k = int(input())
v = set()
for i in range(10):
    dfs(0, str(i), i)
v = list(v)
v.sort()
v.pop(0)
print(v[k-1])

Submission status: Accepted

Solution code:
K = int(input())

from collections import deque
q = deque(list(range(1, 10)))

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

Submission status: Accepted

Solution code:
L=[]

def make_lunlun(A):
    
    # print(A)
   
    if not 0<A<10**10 :
        return
    
    global L
    # print(A)
    
    L.append(A)
    
    if(A%10 != 9):
        make_lunlun(A*10 + (A%10)+1)

    
    if(A!=0):
        make_lunlun(A*10+(A%10))

    
    if(A%10 != 0):
        make_lunlun(A*10 +(A%10)- 1)

    
k=int(input())


for i in range(10):
    make_lunlun(i)
  
L=list(set(L))
L.sort()

print(L[k-1])

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    lunlun = [i for i in range(10)]
    def make(s,keta):
        lst = []
        end = int(s[-1])
        if end == 0:
            lst = [s+"0",s+"1"]
        elif end == 9:
            lst = [s+"8",s+"9"]
        else:
            lst = [s+str(end+i) for i in range(-1,2)]
        if keta == 1:
            for lun in lst:
                lunlun.append(int(lun))
        else:
            for lun in lst:
                make(lun,keta-1)
            
    for keta in range(1,10):
        for i in range(1,10):
            make(str(i),keta)

    k = I()
    ans = lunlun[k]
    print(ans) 
                
        

main()

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()
    r = x%10
    y = 10*x+r
    if r != 0: q.put(y-1)
    q.put(y)
    if r != 9: q.put(y+1)

print(x)

Submission status: Accepted

Solution code:
import sys
k = int(input())
lst = [[0]*10 for i in range(10)]
for i in range(10):
  lst[0][i] = 1
l_sum = [9]  


for i in range(1,10):
  s = 0
  for j in range(10):
    if j == 0:
      lst[i][j] = lst[i-1][j] + lst[i-1][j+1]
    elif j == 9:
      lst[i][j] = lst[i-1][j] + lst[i-1][j-1] 
    else:
      lst[i][j] = lst[i-1][j-1] + lst[i-1][j] + lst[i-1][j+1] 
      
    if j !=0:
      s += lst[i][j]
  l_sum.append(s+l_sum[-1])
    

#表を逆から辿っていく、さらに手直し
i = 0
if k < l_sum[0]:
  print(k)
  sys.exit()
else:
  while True:
    if k < l_sum[i]:
      break
    i += 1
  k = k - l_sum[i-1]
   
  ans = []
  for j in reversed(range(0, i+1)):
    
    if j == i:
      p = 1
      while True:
        if k - lst[j][p] <= 0:
          ans.append(p)
          break
        else:
          k -= lst[j][p]
          p += 1
          
    else:
      if p == 0:
        if k <= lst[j][p]:
          ans.append(p)
        else:
          k -= lst[j][p]
          p += 1
          ans.append(p)
          
      elif p == 9:
        if k <= lst[j][p-1]:
          p = p-1
          ans.append(p)
        else:
          k -= lst[j][p-1]
          ans.append(p)
          
      else:
        if k <= lst[j][p-1]:
          p = p-1
          ans.append(p)
        else:
          k -= lst[j][p-1]
          if k <= lst[j][p]:
            ans.append(p)
          else:
            k -= lst[j][p]
            p = p+1
            ans.append(p)
              
l_s = [str(q) for q in ans]
print(''.join(l_s))

Submission status: Accepted

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

q = deque()
for i in range(1, 10):
    q.append(i)
cnt = 0
while True:
    a = q.popleft()
    cnt += 1
    if cnt == k:
        print(a)
        exit()
    b = a % 10
    for i in (-1, 0, 1):
        if 0 <= b + i <= 9:
            q.append(a*10 + b+i)

Submission status: Accepted

Solution code:
import bisect

k = int(input())

def runrun(n):
    str_n = str(n)
    for i in range(len(str_n)-1):
        if abs(int(str_n[i]) - int(str_n[i+1])) > 1:
            return False
    return True

def build_runrun(d):
    r = ["0","1","2","3","4","5","6","7","8","9"]
    ans = []
    for i in r:
        if i == "0":
            continue
        queue = [[i,1,i]]
        while queue != []:
            q = queue.pop(0)
            if q[1] > d:
                continue
            if q[1] == d:
                bisect.insort(ans,int(q[2]))
                continue

            queue.append([q[0],q[1]+1,q[2]+q[0]])

            low = int(q[0])-1
            if low >= 0:
                queue.append([str(low),q[1]+1,q[2]+str(low)])
            high = int(q[0])+1
            if high < 10:
                queue.append([str(high),q[1]+1,q[2]+str(high)])

    return ans

run = []
d = 1
while len(run) < k:
    run.extend(build_runrun(d))
    d+=1

print(run[k-1])

Submission status: Accepted

Solution code:
def lu(n):
  L.append(n)
  a=n%10
  if len(str(n))>11:
    return 1
  if a==0:
    lu(n*10+1)
    lu(n*10)
  elif a==9:
    lu(n*10+9)
    lu(n*10+8)
  else:
    lu(n*10+1+a)
    lu(n*10+a-1)
    lu(n*10+a)
L=list()
lu(1)
lu(2)
lu(3)
lu(4)
lu(5)
lu(6)
lu(7)
lu(8)
lu(9)
L=sorted(set(L))
k=int(input())
print(L[k-1])

Submission status: Accepted

Solution code:
k = int(input())

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

count = 0
while True:
    count += 1
    if count == k:
        print(d.popleft())
        exit()
    t = d.popleft()
    r = t % 10
    if r != 0:
        d.append(10*t + r - 1)
    d.append(10*t + r)
    if r != 9:
        d.append(10*t + r + 1)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc161/tasks/abc161_d

import sys
# sys.setrecursionlimit(100000)
import heapq


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = int(input())
    if n < 10:
        print(n)
        return
    cnt = 0
    hq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    while cnt < n:
        i = heapq.heappop(hq)
        cnt += 1
        if cnt == n:
            print(i)
            return
        r = int(str(i)[::-1][0])
        heapq.heappush(hq, int(str(i) + str(r)))
        if r != 9:
            heapq.heappush(hq, int(str(i) + str(r + 1)))
        if r != 0:
            heapq.heappush(hq, int(str(i) + str(r - 1)))
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def is_good(mid, key):
    S = list(map(int, str(mid)))
    N = len(S)
    dp = [[[0] * 11 for _ in range(2)] for _ in range(N + 1)]
    dp[1][1][10] = 1
    for k in range(1, S[0]):
        dp[1][1][k] = 1
    dp[1][0][S[0]] = 1
    for i in range(1, N):
        for k in range(1, 11):
            dp[i + 1][1][k] += dp[i][0][10] + dp[i][1][10]
        for is_less in range(2):
            for k in range(10):
                for l in range(k - 1, k + 2):
                    if not 0 <= l <= 9 or (not is_less and l > S[i]):
                        continue
                    dp[i + 1][is_less or l < S[i]][l] += dp[i][is_less][k]
    return sum(dp[N][0][k] + dp[N][1][k] for k in range(10)) >= key


def binary_search(bad, good, key):
    while good - bad > 1:
        mid = (bad + good) // 2
        if is_good(mid, key):
            good = mid
        else:
            bad = mid
    return good


K = int(input())
print(binary_search(0, 3234566667, K))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)


def dfs(v):
    if v > 3234566667:
        return
    ans.append(v)
    d = v % 10
    if d - 1 >= 0:
        dfs(v * 10 + d - 1)
    dfs(v * 10 + d)
    if d + 1 < 10:
        dfs(v * 10 + d + 1)


K = int(input())
ans = []
[dfs(i) for i in range(1, 10)]
print(sorted(ans)[K - 1])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)


def dfs(v):
    ans.append(v)
    if v > 1_000_000_000:
        return
    for d in range(10):
        if abs(d - v % 10) <= 1:
            nv = v * 10 + d
            dfs(nv)


K = int(input())
ans = []
[dfs(i) for i in range(1, 10)]
print(sorted(ans)[K - 1])

Submission status: Accepted

Solution code:
from queue import Queue as Q
k = int(input())
q = Q()
[q.put(i) for i in range(1, 10)]

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:
#!/usr/bin/env python
# coding: utf-8

# In[12]:


from collections import deque


# In[1]:


K = int(input())


# In[15]:


q = deque(list(range(1,10)))
for i in range(K-1):
    x = q.popleft()
    if x%10 != 0:
        y = x*10 + x%10 - 1
        q.append(y)
    y = x*10 + x%10
    q.append(y)
    
    if x%10 != 9:
        y = x*10 + x%10 + 1
        q.append(y)
    
ans = q.popleft()
print(ans)


# In[ ]:

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

k=int(input())

from queue import Queue
que=Queue()
for i in range(1,10):
    que.put(str(i))
cnt=0
while True:
    a=que.get()
    cnt+=1
    #print(a)
    if cnt==k:
        print(a)
        sys.exit()
    if a[-1]=="0":
        que.put(a+"0")
        que.put(a+"1")
    elif a[-1]=="9":
        que.put(a+"8")
        que.put(a+"9")
    else:
        #ac=int(a[-1])
        que.put(a+chr(ord(a[-1])-1))
        que.put(a+a[-1])
        que.put(a+chr(ord(a[-1])+1))

Submission status: Accepted

Solution code:
K = int(input())
a = []

def DFS(n):
    if n > 3234566667:
        return
    a.append(n)
    l = n % 10
    if l == 0:
        DFS(10 * n)
        DFS(10 * n + 1)
    elif l == 9:
        DFS(10 * n + 9)
        DFS(10 * n + 8)
    else:
        DFS(10 * n + l)
        DFS(10 * n + l + 1)
        DFS(10 * n + l - 1)

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

a = sorted(a)
print(a[K-1])

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    k = i_input()
    q = deque([1,2,3,4,5,6,7,8,9])
    for _ in range(k):
        ans = x = q.popleft()
        x0 = x%10
        if x0 >= 1:
            q.append(x*10 + x0 - 1)
        q.append(x*10 + x0)
        if x0 <= 8:
            q.append(x*10 + x0 + 1)
    print(ans)


if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    k = int(input())
    l = list(range(1, 10))
    Q = deque(l)
    for _ in range(k):
        q = Q.popleft()
        # 基準-1
        if q % 10 != 0:
            Q.append(10*q+q%10-1)
        # 基準
        Q.append(10*q+q%10)
        # 基準 + 1
        if q % 10 != 9:
            Q.append(10*q+q%10+1)
    print(q)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K = int(input())

def list2int(digits):
    return int("".join(map(str, digits)))

def int2list(n):
    return list(map(int, str(n)))

def search(digits):
    ret = []
    v = digits[-1]
    for d in [-1, 0, 1]:
        if 0 <= v+d <= 9:
            ret.append(list2int(digits + [v+d]))
    return(ret)

result = list(range(1, 9+1))

i = 0
while len(result) < K:
    digits = int2list(result[i])
    result.extend(search(digits))
    i += 1

print(result[K-1])

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
S = [i for i in range(1,10)]
S = deque(S)
for i in range(1,K+1):
    Lun = S.popleft()
    Lu = Lun%10
    if Lu !=0:
        S.append(10*Lun+Lu-1)
    S.append(Lun*10+Lu)
    if Lu !=9:
        S.append(10*Lun+Lu+1)
print(Lun)

Submission status: Accepted

Solution code:
K = int(input())

A = [0 for d in range(20)]
A[0] = 1
dit_max = 0


for ct in range(2,K+1):
  dit_now = 0
  while dit_max > dit_now and (A[dit_now] == A[dit_now+1]+1 or A[dit_now] == 9):
    dit_now += 1
  if dit_max > dit_now:
    A[dit_now] += 1
  elif dit_max == dit_now:
    if A[dit_now] == 9:
      dit_max += 1
      dit_now += 1
    A[dit_now] += 1
  for d in range(dit_now-1,-1,-1):
      A[d] = max(A[d+1] - 1,0)
  #if ct > 30:
    #print(ct, A)
      
ans = 0
for i in range(20):
  ans += A[i] * 10**i
print(ans)

Submission status: Accepted

Solution code:
import queue
k=int(input())
q=queue.Queue()
for i in range(1,10):
    q.put(i)
lunlun=list(range(1,10))
cnt=9

while cnt<=k:
    v=q.get()
    last=v%10
    if last!=0:
        new=v*10+last-1
        q.put(new)
        lunlun.append(new)
        cnt+=1
    new=v*10+last
    q.put(new)
    lunlun.append(new)
    cnt+=1
    if last!=9:
        new=v*10+last+1
        q.put(new)
        lunlun.append(new)
        cnt+=1
print(lunlun[k-1])

Submission status: Accepted

Solution code:
#D - Lunlun Number
import sys
sys.setrecursionlimit(10**6+1)
K = int(input())

ans = []
def dfs(A):
    if len(A)>=2:
        A_str = [str(i) for i in A] 
        A_str = ''.join(A_str)
        ans.append(int(A_str))
    if len(A) == 10:
        return
    if len(A) >= 1:
        #前の値が0,9のときは範囲が違う   
        if A[-1] == 9:
            sta = 8
            fin = 9+1
        elif A[-1] == 0:
            sta = 0
            fin = 1+1
        else:
            sta = A[-1] - 1
            fin = A[-1] + 1 + 1
        for v in range(sta,fin):
            A.append(v)
            dfs(A)
            A.pop()
    else:
        for v in range(1,9+1):
            A.append(v)
            dfs(A)
            A.pop()
dfs([])
ans = sorted(ans,reverse = False)
if K<=9:
    print(K)
else:
    print(ans[K-10])

Submission status: Accepted

Solution code:
k = int(input())

def rec(d, n, array):
    array.append(n)

    if d == 10:
        return
    
    for i in [-1, 0, 1]:
        add = n % 10 + i
        if 0 <= add <= 9:
            rec(d + 1, 10 * n + add, array)


array = []
for i in range(1, 10):
    rec(1, i, array)

s_array = sorted(array)
ans = s_array[k - 1]
print(ans)

Submission status: Accepted

Solution code:
K = int(input())
ls = []
def rec(digit, ini):
    ls.append(ini)
    if digit == 10: #最大10けたなので(sample4)
        return
    deltas = []
    if ini % 10 == 0:
        deltas = [0, 1]
    elif ini % 10 == 9:
        deltas = [-1, 0]
    else:
        deltas = [-1, 0, 1]
    for delta in deltas:
        new = ini * 10 + ini % 10 + delta
        rec(digit+1, new)

for ini in range(1, 10):
    rec(1, ini)
print(sorted(ls)[K-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
d=deque([1,2,3,4,5,6,7,8,9])
num=[1,2,3,4,5,6,7,8,9]
while d:
  now=d.popleft()
  hitoketa=now%10
  for i in [-1,0,1]:
    if 0<=hitoketa+i<=9:
      nxt=now*10+hitoketa+i
      if nxt<=3234566667:
        #print(nxt)
        num.append(nxt)
        d.append(nxt)
num.sort()
print(num[k-1])

Submission status: Accepted

Solution code:
k = int(input())
lunlun = []
def dfs(A):
    if len(A) > 10:
        return 
    else:
        num = int(A[-1])
        lunlun.append(int("".join(A)))
        if num == 0:
            for i in range(0, 2):
                A.append(str(i))
                dfs(A)
                A.pop()
        elif num == 9:
            for i in range(8, 10):
                A.append(str(i))
                dfs(A)
                A.pop()
        else:
            for i in range(num-1, num+2):
                A.append(str(i))
                dfs(A)
                A.pop()

for i in range(1, 10):
    dfs([str(i)])
lunlun.sort()
print(lunlun[k-1])

Submission status: Accepted

Solution code:
k = int(input())
lunlun = []
def dfs(A):
    if len(A) > 10:
        return 
    else:
        num = A[-1]
        lunlun.append(int("".join(A)))
        if num == "0":
            for i in range(0, 2):
                A.append(str(i))
                dfs(A)
                A.pop()
        elif num == "9":
            for i in range(8, 10):
                A.append(str(i))
                dfs(A)
                A.pop()
        else:
            for i in range(int(num)-1, int(num)+2):
                A.append(str(i))
                dfs(A)
                A.pop()

for i in range(1, 10):
    dfs([str(i)])
lunlun.sort()
print(lunlun[k-1])

Submission status: Accepted

Solution code:
k = int(input())

import queue

que = queue.Queue()

for i in range(1, 10):
    que.put(i)

for i in range(1, k + 1):
    ans = que.get()
    keta1 = ans % 10
    if keta1 == 0:
        append_list = [ans * 10, ans * 10 + 1]
    elif keta1 == 9:
        append_list = [ans * 10 + 8, ans * 10 + 9]
    else:
        append_list = [ans * 10 + keta1 - 1, ans * 10 + keta1, ans * 10 + keta1 + 1]
    for item in append_list:
        que.put(item)
print(ans)

Submission status: Accepted

Solution code:
k = int(input())

import queue

que = queue.Queue()

for i in range(1, 10):
    que.put(i)

for i in range(1, k + 1):
    ans = que.get()
    keta1 = ans % 10
    if keta1 == 0:
        append_list = [ans * 10, ans * 10 + 1]
    elif keta1 == 9:
        append_list = [ans * 10 + 8, ans * 10 + 9]
    else:
        append_list = [ans * 10 + keta1 - 1, ans * 10 + keta1, ans * 10 + keta1 + 1]
    for ite in append_list:
        que.put(ite)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

Q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

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

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

ans = Q.popleft()

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
d=deque()
for i in range(1,10):
    d.append(i)
for i in range(k-1):
    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(d.popleft())

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
from collections import deque

def main():
    K = int(input())
    # cnt = 0
    # dq = deque(['1','2','3','4','5','6','7','8','9'])
    # while cnt < K:
    #     cnt += 1
    #     d = dq.popleft()
    #     a = int(d[-1])
    #     if a == 0:
    #         dq.append(d+str(0))
    #         dq.append(d+str(1))
    #     elif a == 9:
    #         dq.append(d+str(8))
    #         dq.append(d+str(9))
    #     else:
    #         for i in range(a-1, a+2):
    #             dq.append(d+str(i))
    # print(d)

    runrun_lst = []
    def rec(num_of_digit, runrun_val):
        runrun_lst.append(runrun_val)
        if num_of_digit == 10: return
        for i in range(-1, 2):
            add = (runrun_val%10) + i
            if 0 <= add <= 9: rec(num_of_digit+1, runrun_val*10+add)

    for v in range(1, 10):
        rec(1, v)
    runrun_lst.sort()
    print(runrun_lst[K-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
num=[]

def dfs(lun):
  #print(lun)
  num.append(lun)
  if lun>3234566667:
    return
  now=lun%10
  for i in [-1,0,1]:
    if 0<=now+i<=9:
      dfs(lun*10+now+i)

for i in range(1,10):
  dfs(i)
num.sort()
print(num[k-1])
#print(num[0:k])

Submission status: Accepted

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

Submission status: Accepted

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

def solver(d, v, a):
  a.append(v)
  if d == 10:
    return

  for i in range(-1, 2):
    add = (v % 10) + i;
    if add < 0 or 9 < add:
      continue
    solver(d + 1, v * 10 + add, a)

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

  a = []
  for i in range(1, 10):
    solver(1, i, a)
  a.sort();

  print(a[k - 1])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
K = int(input())
A = [i for i in range(1, 10)]
if K <= 9:
  print(A[K-1])
else:
  K -= 9
  f = 1
  while f:
    B = []
    for a in A:
      k = a % 10
      if k != 0:
        B.append(a * 10 + k - 1)
        K -= 1
      if K == 0:
        print(B[-1])
        f = 0
        break
      B.append(a * 10 + k)
      K -= 1
      if K == 0:
        print(B[-1])
        f = 0
        break
      if k != 9:
        B.append(a * 10 + k + 1)
        K -= 1
      if K == 0:
        print(B[-1])
        f = 0
        break
    A = B

Submission status: Accepted

Solution code:
from collections import deque

def main():
    K = int(input())
    q = deque()
    for i in range(1,10,1):
        q.append(i)
    list = []
    while (len(list) <= 100002):
        v = q.popleft()
        list.append(v)
        amari = v%10
        if amari != 0 and amari != 9:
            q.append((v*10)+amari-1)
            q.append((v*10)+amari)
            q.append((v*10)+amari+1)
        elif amari == 0:
            q.append((v*10)+amari)
            q.append((v*10)+amari+1)
        else:
            q.append((v*10)+amari-1)
            q.append((v*10)+amari)

    return list[K-1]

print(main())

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
q = deque([i for i in range(1, 10)])
for _ in range(K - 1):
    # 13print(q)
    num = q.popleft()
    for i in range(-1,2):
        if 0 <= int(str(num)[-1]) + i <= 9:
            q.append(num * 10 + int(str(num)[-1]) + i)
print(q[0])

Submission status: Accepted

Solution code:
from collections import deque
d = deque(range(1,10))
k = int(input())

for _ in range(k):
    ans = d.popleft()
    mod = ans % 10
    if mod != 0:
        d.append(ans * 10 + mod - 1)
    d.append(ans * 10 + mod)
    if mod != 9:
        d.append(ans * 10 + mod + 1)

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    K = int(input())
    lunluns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    count = 9
    pointer = 0
    while K > count:
        lunnum = lunluns[pointer]
        lunlast = int(str(lunnum)[-1])
        if lunlast == 0:
            for i in [0, 1]:
                lunluns.append(int(str(lunnum)+str(lunlast+i)))
                count += 1
        elif lunlast == 9:
            for i in [-1, 0]:
                lunluns.append(int(str(lunnum)+str(lunlast+i)))
                count += 1
        else:
            for i in [-1, 0, 1]:
                lunluns.append(int(str(lunnum)+str(lunlast+i)))
                count += 1
        pointer += 1
    print(lunluns[K-1])

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(1,k):
    v=d.popleft()
    s=v%10
    if s>0:
        d.append(10*v+s-1)
    d.append(10*v+s)
    if s<9:
        d.append(10*v+s+1)
    
print(d[0])

Submission status: Accepted

Solution code:
from collections import deque

def main():
  N=int(input())
  for n in range(N):
    x=ans.popleft()
    if x%10!=0:
      ans.append(10*x+(x%10)-1) # x equal y-1
    ans.append(10*x+(x%10)) # x equal y
    if x%10!=9:
      ans.append(10*x+(x%10)+1) # x equal y+1
  print(x)
  
if __name__=='__main__':
  ans=deque([1,2,3,4,5,6,7,8,9])
  main()

Submission status: Accepted

Solution code:
from collections import deque

k=int(input())

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

b=deque(a)

while b:
  v=b.popleft()
  if v%10==0:
    f=v*10+1
    if f<=3234566667:
      
      b.append(f)
      a.append(f)
    g=v*10
    if g<=3234566667:
      b.append(g)
      a.append(g)
    
  elif v%10==9:
    f=v*10+8
    g=v*10+9
    if f<=3234566667:
      
      b.append(f)
      a.append(f)
    if g<=3234566667:
      b.append(g)
      a.append(g)
    
  else:
    f=v*10+(v%10)-1
    g=v*10+(v%10)
    h=v*10+(v%10)+1
    if f<=3234566667:
      b.append(f)
      a.append(f)
    if g<=3234566667:
      b.append(g)
      a.append(g)
    if h<=3234566667:
      b.append(h)
      a.append(h)
      
a.sort()

print(a[k-1])

Submission status: Accepted

Solution code:
from collections import deque

K=int(input())
q=deque([i for i in range(1,10)])
for _ in range(K-1):
  x=deque.popleft(q)
  a=x%10
  if a!=0 and a!=9:
    deque.append(q,x*10+a-1)
    deque.append(q,x*10+a)
    deque.append(q,x*10+a+1)
  elif a==0:
    deque.append(q,x*10)
    deque.append(q,x*10+1)
  else:
    deque.append(q,x*10+8)
    deque.append(q,x*10+9)
print(deque.popleft(q))

Submission status: Accepted

Solution code:
from collections import deque

K=int(input())
if K<=9:
  print(K)
  exit()
q=deque([i for i in range(1,10)])
for _ in range(K-1):
  x=deque.popleft(q)
  a=x%10
  if a!=0 and a!=9:
    deque.append(q,x*10+a-1)
    deque.append(q,x*10+a)
    deque.append(q,x*10+a+1)
  elif a==0:
    deque.append(q,x*10)
    deque.append(q,x*10+1)
  else:
    deque.append(q,x*10+8)
    deque.append(q,x*10+9)
print(deque.popleft(q))

Submission status: Accepted

Solution code:
K=int(input())

if K<=9:
  print(K)
else:
  p=1
  dp,old=[[1]*10],[0,1]
  n=9
  while K>n:
    old=dp[p-1]
    tmp=[0]*10
    for i in range(1,9):
      tmp[i]=old[i-1]+old[i]+old[i+1]
    tmp[9]=old[8]+old[9]
    tmp[0]=old[0]+old[1]
    dp.append(tmp)
    p+=1
    n+=sum(tmp[1:])

  ans=0
  n-=sum(tmp[1:])
  K-=n
  c=2
  for i in range(p-1,-1,-1):
    if c!=0:
      c-=1
    while K>dp[i][c]:
      K-=dp[i][c]
      c+=1
    ans+=c*10**i
  print(ans)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

q = deque()
for i in range(1,10):
    q.append(i)
ans=0
cnt=0
while cnt<K:
    cnt+=1
    current = q.popleft()

    dn = [-1,0,1]
    for i in dn:
        if current%10+i<0 or current%10+i>9:
            continue
        q.append(current*10+current%10+i)
else:
    ans=current
    
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

q = deque()
for i in range(1,10):
    q.append(i)
ans=0
if K>=10:
    cnt = 9
    while len(q)>0:
        current = q.popleft()

        dn = [-1,0,1]
        for i in dn:
            if current%10+i<0 or current%10+i>9 or cnt>=K:
                continue
            q.append(current*10+current%10+i)
            cnt+=1
    else:
        ans=current

else:
    ans = K
    
print(ans)