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:
# ABC161D
def f(k):
    if 1 <= k <= 9:
        print(k)
    else:
        nxt = [[0,1], [0,1,2], [1,2,3], [2,3,4], [3,4,5], [4,5,6], [5,6,7], [6,7,8], [7,8,9], [8,9]]
        cum_npi = [0, 9, 35, 110, 327, 956, 2782, 8089, 23527, 68468, 199368]
        for length, begin in enumerate(cum_npi):
            if k < begin:
                found = cum_npi[length - 1]
                break
        begin = 10 ** (length - 1)
        length, begin, found
        k -= found
        x = [[]] * (length + 1)
        x[1] = list(range(1, 10))
        x

        terminate = False
        i = 1
        while True:
            #print(f"a) i = {i}  x = {x}")
            if len(x[i]): # len(x[i])
                digit = x[i][0]
                if i < length: # i, length
                    i += 1
                    x[i] = nxt[digit].copy()
                    #print(f"x) digit = {digit}  nxt[digit] = {nxt[digit]}  i = {i}  x[i] = {x[i]}")
                    #print(f"b) i = {i}  x = {x}")
                    if i == length: # i, length
                        while len(x[i]): # i, x[i]
                            k -= 1
                            #print(f"c) i = {i}  x = {x}, k = {k}")
                            if k == 0:
                                x.pop(0)
                                #print("answer =", x)
                                ans = "".join([str(j.pop(0)) for j in x])
                                print(ans)
                                terminate = True
                                break
                            else:
                                x[i].pop(0)
                            #print(f"d) i = {i}  x = {x}")
                        else:
                            #print(f"e) i = {i}  x = {x}")
                            while len(x[i]) == 0:
                                i -= 1
                                x[i].pop(0)
                        if terminate:
                            break

f(int(input()))

Submission status: Accepted

Solution code:
# D - Lunlun Number

from collections import deque

k = int(input())

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

for _ in range(k):
    ans = d.popleft()
    keta1 = ans%10
    for i in [-1, 0, 1]:
        if keta1+i>=0 and keta1+i<=9:
            d.append(ans*10+keta1+i)

print(ans)

Submission status: Accepted

Solution code:
import sys
import queue
I=input()
K=int(I)
Q=queue.Queue()
for _ in range(1,10):
    Q.put(_)
x=0
for _ 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:
from collections import deque

K = int(input())
queue = deque([i for i in range(1,10)])

while K != 0:
  if K <= len(queue):
    print(queue[K-1])
    exit(0)

  K -= 1
  num = queue.popleft()

  o = int(str(num)[-1])
  for n in [o-1, o, o+1]:
    if n == -1 or n == 10: continue
    queue.append( int(str(num)+str(n)) )

Submission status: Accepted

Solution code:
K = int(input())
queue = []
for i in range(1, 10):
  queue.append(i)

while K != 0:
  if K <= len(queue):
    print(queue[K-1])
    exit(0)

  K -= 1
  num = queue.pop(0)

  if K == 0:
    print(num)
    exit(0)

  o = int(str(num)[-1])
  for n in [o-1, o, o+1]:
    if n == -1 or n == 10: continue
    queue.append( int(str(num)+str(n)) )

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

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
D = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

if K <= 9:
  print(D[K])
else:
  start = 1
  K -= 9
  while True:
    d = D[start]
    start += 1
    ichi = d % 10
    if ichi == 0:
      if K == 1:
        print(d * 10 + 0)
        break
      elif K == 2:
        print(d * 10 + 1)
        break
      else:
        D.append(d * 10 + 0)
        D.append(d * 10 + 1)
        K -= 2
    elif ichi == 9:
      if K == 1:
        print(d * 10 + 8)
        break
      elif K == 2:
        print(d * 10 + 9)
        break
      else:
        D.append(d * 10 + 8)
        D.append(d * 10 + 9)
        K -= 2
    else:
      if K == 1:
        print(d * 10 + ichi - 1)
        break
      elif K == 2:
        print(d * 10 + ichi)
        break
      elif K == 3:
        print(d * 10 + ichi + 1)
        break
      else:
        D.append(d * 10 + ichi - 1)
        D.append(d * 10 + ichi)
        D.append(d * 10 + ichi + 1)
        K -= 3

Submission status: Accepted

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

def bfs():
    q = deque([1,2,3,4,5,6,7,8,9])
    cnt = 0
    while q:
        num = q.popleft()
        cnt += 1
        if cnt == k:
            return num
        else:
            if str(num)[-1] == "0":
                q.append(num*10)
                q.append(num*10+1)
            elif str(num)[-1] == "9":
                q.append(num*10+8)
                q.append(num*10+9)
            else:
                q.append(num*10+int(str(num)[-1])-1)
                q.append(num*10+int(str(num)[-1]))
                q.append(num*10+int(str(num)[-1])+1)


print(bfs())

Submission status: Accepted

Solution code:
a = [1,2,3,4,5,6,7,8,9,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000]
import heapq
heapq.heapify(a)
cnt = 18
c = 1
while True:
  if cnt > 10**5:
    break
  for i in a:
    if len(str(i)) == c:
      m = i//10**(c-1)
      if i//10**(c-1) == 1:
        heapq.heappush(a,i+10**c*(i//10**(c-1)))
        heapq.heappush(a,i+10**c*(i//10**(c-1)+1))
        cnt += 2
        for j in range(10-c):
          heapq.heappush(a,i+10**c*(10**(j+1)))
          cnt += 1
      elif i//10**(c-1) == 9:
        heapq.heappush(a,i+10**c*(i//10**(c-1)-1))
        heapq.heappush(a,i+10**c*(i//10**(c-1)))
        cnt += 2
      else:
        heapq.heappush(a,i+10**c*(i//10**(c-1)-1))
        heapq.heappush(a,i+10**c*(i//10**(c-1)))
        heapq.heappush(a,i+10**c*(i//10**(c-1)+1))
        cnt += 3
  c += 1

k = int(input())
#a = set(a)
#a = list(a)
for i in range(k-1):
  heapq.heappop(a)
print(heapq.heappop(a))

Submission status: Accepted

Solution code:
def pat(K,count,keta,num):
    #print(str(num)+":"+str(count)+":"+str(keta))
    if count == -1:
        return -1
    elif keta == 1:
        if count == K-1:
            print(num)
            return -1
        else:
            return (count+1)
    else:
        if (int(num[-1])) -1 >= 0:
            count = pat(K,count,keta-1,num+str(int(num[-1])-1))
        count = pat(K,count,keta-1,num+num[-1])
        if (int(num[-1])+1) <= 9:
            count = pat(K,count,keta-1,num+str(int(num[-1])+1))
            
    return count


K = int(input())
count = 0
ans = list()
keta = 0

while True:
    keta += 1
    for i in range(1,10):
        count = pat(K,count,keta,str(i))
        #print(count)
        if count  == -1:
            break
    if count == -1:
        break

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

if 1 <= k and k <= 9:
    print(k)
    exit()

d = deque([i for i in range(1, 10)])
k -= 9
while k > 0:
    num = d.popleft()
    if num % 10 != 0:
        new = 10*num + (num%10) - 1
        d.append(new)
        k -= 1
        if k == 0: break
    new = 10*num + (num%10)
    d.append(new)
    k -= 1
    if k == 0: break
    if num % 10 != 9:
        new = 10*num + (num%10) + 1
        d.append(new)
        k -= 1
        if k == 0: break

print(new)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

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

Submission status: Accepted

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

q = deque([str(i) for i in range(1, 10)])
cnt = 0
while True:
    if cnt == K-1:
        print(q.popleft())
        sys.exit()
    cnt += 1
    x = q.popleft()
    b = int(x[-1])
    if b > 0:
        q.append(x+str(b-1))
    q.append(x+str(b))
    if b < 9:
        q.append(x+str(b+1))

Submission status: Accepted

Solution code:
import collections
# from queue import Queue
k = int(input())
q = collections.deque()
Lunlun = []
for i in range(1, 10):
    q.append(i)
while True:
    if len(Lunlun) >= 10**5:
        break
    now = q.popleft()
    Lunlun.append(now)
    for i in range(-1, 2):
        if (now % 10) + i < 0 or 9 < (now % 10) + i:
            continue
        q.append(now*10 + (now % 10) + i)

print(Lunlun[k-1])

Submission status: Accepted

Solution code:
from queue import Queue
k = int(input())
q = Queue()
Lunlun = []
for i in range(1, 10):
    q.put(i)
while True:
    if len(Lunlun) >= 10**5:
        break
    now = q.get()
    Lunlun.append(now)
    for i in range(-1, 2):
        if (now % 10) + i < 0 or 9 < (now % 10) + i:
            continue
        q.put(now*10 + (now % 10) + i)

print(Lunlun[k-1])

Submission status: Accepted

Solution code:
import heapq
import sys

def solve(k):
    if k < 10:
        return k
    
    heap = [1,2,3,4,5,6,7,8,9]
    heapq.heapify(heap)

    for i in range(k-1):
        lunlun = heapq.heappop(heap)
        lastDigit = lunlun  % 10
        # print lunlun
        heapq.heappush(heap, (lunlun*10) + lastDigit)

        if lastDigit == 0:
            newlunlun = (lunlun * 10) + 1
            heapq.heappush(heap, newlunlun)    
        elif lastDigit == 9:
            newlunlun = (lunlun * 10) + 8
            heapq.heappush(heap, newlunlun)  
        else:
            newlunlun1 = (lunlun * 10) + lastDigit + 1
            newlunlun2 = (lunlun * 10) + lastDigit - 1
            heapq.heappush(heap, newlunlun1)
            heapq.heappush(heap, newlunlun2)

    return heapq.heappop(heap)

k = input()
# k = 100000
print(solve(int(k)))

Submission status: Accepted

Solution code:
from collections import Counter, deque
# from copy import copy, deepcopy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# from operator import xor
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    K=int(input())
    d=deque(['1','2','3','4','5','6','7','8','9'])
    for i in range(K):
        dd=d.popleft()
        if i==K-1:
            print(dd)
        else:
            ddd=dd[-1]
            if int(ddd)==0:
                d.append(dd+str(int(ddd)))
                d.append(dd+str(int(ddd)+1))
            if 1<=int(dd[-1])<=8:
                d.append(dd+str(int(ddd)-1))
                d.append(dd+str(int(ddd)))
                d.append(dd+str(int(ddd)+1))
            if int(dd[-1])==9:
                d.append(dd+str(int(ddd)-1))
                d.append(dd+str(int(ddd)))


resolve()

Submission status: Accepted

Solution code:
from collections import deque


k = int(input())

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

for _ in range(k):
    num = queue.popleft()
    x = num % 10

    if x != 0:
        queue.append(num*10 + x-1)

    queue.append(num*10 + x)

    if x != 9:
        queue.append(num*10 + x+1)

print(num)

Submission status: Accepted

Solution code:
from collections import deque


k = int(input())

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

for _ in range(k):
    num = queue.popleft()
    a = num // 10
    b = num % 10

    if b != 0:
        queue.append(num*10 + b-1)

    queue.append(num*10 + b)
    
    if b != 9:
        queue.append(num*10 + b+1)

print(num)

Submission status: Accepted

Solution code:
k=int(input())
lun=[1,2,3,4,5,6,7,8,9]
for i in range(10**5+1):
    if len(lun)>=k:
        break
    di=lun[i]%10
    for j in range(max(0,di-1),min(9,di+1)+1):
        lun.append(lun[i]*10+j)
print(lun[k-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
k = int(input())
l = list(range(1,10))
x = 0

while True:
    a = l.pop(0)
    x += 1
    
    if x >= k:
        print(a)
        exit()
    if k > 10000 and x > k/2:
        continue
    
    if a%10 == 0:
        b = int(str(a) + "0")
        l.append(b)
        
        b = int(str(a) + "1")
        l.append(b)
        
            
    elif a%10 == 9:
        b = int(str(a) + "8")
        l.append(b)
        
        b = int(str(a) + "9")
        l.append(b)
        
        
    else:
        b = int(str(a) + str((a%10)-1))
        l.append(b)
        
        b = int(str(a) + str(a%10))
        l.append(b)
        
        b = int(str(a) + str((a%10)+1))
        l.append(b)
        
        
        if x >= k:
            print(a)
            exit()

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
queue = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

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

Submission status: Accepted

Solution code:
k = int(input())
a = [[1] * 10]
ps = 0
s = 0
for i in range(10000):
  for j in range(1, 10):
    ps = s
    s += a[i][j]
    if s >= k:
      break
  else:
    a.append([a[i][j-1] + a[i][j] + a[i][j+1] if j != 0 and j != 9 else a[i][0] + a[i][1] if j == 0 else a[i][8] + a[i][9] for j in range(10)])
    continue
  break
n = i
ans = str(j)
for i in range(n - 1, -1, -1):
  k -= ps
  m = j
  s = 0
  for j in range(max(0, m - 1), min(10, m + 2)):
    ps = s
    s += a[i][j]
    if s >= k:
      break
  ans += str(j)
print(int(ans))

Submission status: Accepted

Solution code:
K = int(input())
cnt = 0
ans = 0
for i in range(0, 10):
    for j in range(0, 10):
        if (j <= i-2 or j >= i+2) and i != 0:
            continue
        for k in range(0, 10):
            if (k <= j-2 or k >= j+2) and i+j != 0:
                continue
            for l in range(0, 10):
                if (l <= k-2 or l >= k+2) and i+j+k != 0:
                    continue
                for m in range(0, 10):
                    if (m <= l-2 or m >= l+2) and i+j+k+l != 0:
                        continue
                    for n in range(0, 10):
                        if (n <= m-2 or n >= m+2) and i+j+k+l+m != 0:
                            continue
                        for o in range(0, 10):
                            if (o <= n-2 or o >= n+2) and i+j+k+l+m+n != 0:
                                continue
                            for p in range(0, 10):
                                if (p <= o-2 or p >= o+2) and i+j+k+l+m+n+o != 0:
                                    continue
                                for q in range(0, 10):
                                    if (q <= p-2 or q >= p+2) and i+j+k+l+m+n+o+p != 0:
                                        continue
                                    for r in range(0, 10):
                                        if ((r <= q-2 or r >= q+2) and i+j+k+l+m+n+o+p+q != 0) or i+j+k+l+m+n+o+p+q+r == 0:
                                            continue
                                        cnt += 1
                                        if cnt == K:
                                            ans = r + 10 * q + 100 * p + 1000 * o + 10000 * n + 100000 * m + 1000000 * l + 10000000 * k + 100000000 * j + 1000000000 * i
print(ans)

Submission status: Accepted

Solution code:
import heapq
k = int(input())
run_list = [i for i in range(1,10)]
heapq.heapify(run_list)
result = 0
for i in range(k):
  result = heapq.heappop(run_list)
  if result % 10 ==0:
    new_1 = result * 10
    new_2 = result * 10 + 1
    heapq.heappush(run_list, new_1)
    heapq.heappush(run_list, new_2)
  elif result % 10 ==9:
    new_1 = result * 10 + 8
    new_2 = result * 10 + 9
    heapq.heappush(run_list, new_1)
    heapq.heappush(run_list, new_2)
  else:
    new_1 = result * 10 + (result % 10)
    new_2 = result * 10 + (result % 10) + 1
    new_3 = result * 10 + (result % 10) - 1
    heapq.heappush(run_list, new_1)
    heapq.heappush(run_list, new_2)
    heapq.heappush(run_list, new_3)
print(result)

Submission status: Accepted

Solution code:
K = int(input())

from collections import deque

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

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

Submission status: Accepted

Solution code:
from collections import deque

def main():
    K = int(input())
    que = deque([i for i in range(1, 10)])

    while K:
        if K == 1:
            ans = que.popleft()
            break
        K -= 1
        v = que.popleft()
        for i in range(-1, 2, 1):
            a = v % 10 + i
            if a < 0 or a > 9:
                continue
            que.append(v * 10 + a)
            
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    K = int(input())
    que = deque([i for i in range(1, 10)])

    while K:
        if K == 1:
            ans = que.popleft()
            break
        K -= 1
        v = que.popleft()
        if v % 10 == 0:
            que.append(v * 10)
            que.append(v * 10 + 1)
        elif v % 10 == 9:
            que.append(v * 10 + 8)
            que.append(v * 10 + 9)
        else:
            que.append(v * 10 + (v % 10 - 1))
            que.append(v * 10 + (v % 10))
            que.append(v * 10 + (v % 10 + 1))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    K = int(input())
    que = deque(['1', '2', '3', '4', '5', '6', '7', '8', '9'])

    while K:
        if K == 1:
            ans = que.popleft()
            break
        K -= 1
        v = que.popleft()
        if v[-1] == '0':
            que.append(v + '0')
            que.append(v + '1')
        elif v[-1] == '9':
            que.append(v + '8')
            que.append(v + '9')
        else:
            que.append(v + str(int(v[-1]) - 1))
            que.append(v + str(int(v[-1])))
            que.append(v + str(int(v[-1]) + 1))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

while K:
    if K == 1:
        ans = que.popleft()
        break
    K -= 1
    v = que.popleft()
    if v[-1] == '0':
        que.append(v + '0')
        que.append(v + '1')
    elif v[-1] == '9':
        que.append(v + '8')
        que.append(v + '9')
    else:
        que.append(v + str(int(v[-1]) - 1))
        que.append(v + str(int(v[-1])))
        que.append(v + str(int(v[-1]) + 1))

print(ans)

Submission status: Accepted

Solution code:
#abc161d
from collections import deque
k=int(raw_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:
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

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

def main():
  """
  10,11,12 １の末尾に0,1,2を付けたもの！
  21,22,23 2の末尾に0,1,2を付けたもの！
  queueを使う！
  1,2,3,4,5,6,7,8,9,
  2,3,4,5,6,7,8,9,10,11,12
  3,4,5,6,7,8,9,10,11,12,21,22,23
  という風に、pushしていく
  """
  k = int(input())
  from collections import deque
  d = deque()
  # まず一桁のやつを最初にいれていく
  for i in range(1,10):
    d.append(i)
  #一桁ずつ増えていく感じで実装する
  
  #print(d)
  #exit()
  cnt = len(d)
  while True:
    if k <= cnt:
      print(d[k-1])
      exit()
    #k -= cnt # これで2桁目以上で、k番目ってのが出来るよ('ω')！！
    x = d.popleft()
    cnt -=1
    k -=1
    for i in range(-1,2,1):
      a = x % 10 + i
      if a < 0 or a > 9 :continue
      nx = x * 10 + a # くっつける
      d.append(nx)
      cnt += 1
      # これで列挙が出来る
    #print(d,len(d),cnt,k)
if __name__ == '__main__':
  main()

Submission status: Accepted

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

cnt = 0
q = deque()
for i in range(1, 10):
    q.append(i)
while cnt < K:
    num = q.popleft()
    cnt += 1
    if num%10 > 0:
        q.append(10*num+(num%10)-1)
    q.append(10*num+(num%10))
    if num%10 < 9:
        q.append(10*num+(num%10)+1)

print(num)

Submission status: Accepted

Solution code:


import collections


def solve():

    K = int(input())
    q = collections.deque()

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

    lunlun = 0

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

    print(lunlun)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque
que = deque([i for i in range(1,10)])
n = int(input())

for i in range(n):
    x = que.popleft()
    xl = [x%10-1, x%10,x%10 + 1]
    for j in xl:
        if j == -1 or j == 10:
            continue
        else:
            que.append(10*x+j)
        
print(x)

Submission status: Accepted

Solution code:
import queue
count=9
target=int(input())
q=queue.Queue()
for i in range(1,10):
    q.put(i)
if count>=target:
    print(target)

if count<target:
    while(1):
        a=q.get()
        if a%10!=0:
            q.put(a*10+a%10-1)
            count+=1
            if count==target:
                print(a*10+a%10-1)
                break
        q.put(a*10+a%10)
        count+=1
        if count==target:
            print(a*10+a%10)
            break
        if a%10!=9:
            q.put(a*10+a%10+1)
            count+=1
            if count==target:
                print(a*10+a%10+1)
                break

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

    result = []

    while len(result) <= n:
        x = q.popleft()
        result.append(x)
        m = x % 10
        if m == 0:
            q.append(x * 10 + m)
            q.append(x*10+ m +1)
        elif m == 9:
            q.append(x*10 + m - 1)
            q.append(x * 10 + m)
        else:
            q.append(x*10 + m - 1)
            q.append(x * 10 + m)
            q.append(x*10 + m + 1)

    print(result[n-1])


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

k = int(input())

ll = [x for x in range(1, 10)]
q = deque(ll)

cnt = 0

while True:
    n = q.popleft()
    mod = n % 10
    if mod == 0:
        q.append(n * 10 + mod)
        q.append(n * 10 + mod + 1)
    elif 1 <= mod <= 8:
        q.append(n * 10 + mod - 1)
        q.append(n * 10 + mod)
        q.append(n * 10 + mod + 1)
    else:  # mod==9
        q.append(n * 10 + mod - 1)
        q.append(n * 10 + mod)

    cnt += 1
    if cnt == k:
        print(n)
        exit(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(K: int):

    h = deque([])

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

    for i in range(K-1):
        s = h.popleft()
        for j in range(-1, 2):
            add = (s % 10)+j
            if 0 <= add <= 9:
                h.append(s*10+add)
    print(h.popleft())
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

K = input_int()

if K < 10:  # 1桁の数はすべてlun_lun
    print(K)
else:  # 桁数の小さいものからlun_lun数を生成し，queueに加えていく
    dq = deque([i for i in range(1, 10)])
    count = 0
    while True:
        x = dq.popleft()
        count += 1
        if count == K:
            print(x)
            exit()
        d = x % 10
        if d != 0:
            dq.append(10 * x + d - 1)
        dq.append(10 * x + d)
        if d != 9:
            dq.append(10 * x + d + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(K: int):

    X = set()

    def rec(keta, val):
        X.add(val)
        if keta == 10:
            return

        for j in range(-1, 2):
            add = (val % 10)+j
            if add >= 0 and add <= 9:
                rec(keta+1, val*10+add)

    for i in range(1, 10):
        rec(1, i)
    X = sorted(X)
    print(X[K-1])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
if K<10:
    print(K)
else:
    dq = deque([i for i in range(1, 10)])
    k = 10
    while k<=K:
        x = dq.popleft()
        d = x%10
        if d!=0:
            dq.append(10*x + (d-1))
            k += 1
        dq.append(10*x + d)
        k += 1
        if d!=9:
            dq.append(10*x + (d+1))
            k += 1
    print(dq[-(k-K)])

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):
    a = d.popleft()
    l = [a%10-1, a%10, a%10+1]
    for j in l:
        if j==-1 or j==10:
            continue
        d.append(a*10 + j)

print(a)

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
d = deque([1,2,3,4,5,6,7,8,9])

ans = []
while len(ans) < k:
    a = d.popleft()
    ans.append(a)
    l = [a%10-1, a%10, a%10+1]
    for i in l:
        if i==-1 or i==10:
            continue
        d.append(a*10 + i)

print(ans[k-1])

Submission status: Accepted

Solution code:
def abs(x):
    if x >= 0:
        return x;
    else:
        return -x;

def Next(v, n):
    list = [];
    for i in range(n - 1, -1, -1):
        if v[i] != 9 and (i == 0 or abs(v[i - 1] - (v[i] + 1)) <= 1):
            for j in range(i):
                list.append(v[j]);
            list.append(v[i] + 1);
            for j in range(i + 1, n):
                list.append(max(list[j - 1] - 1, 0));
            return list;
    list.append(1);
    for i in range(n):
        list.append(0);
    return list;

k = int(input());

curr = [];
curr.append(0);

for i in range(k):
    curr = Next(curr, len(curr));
    #print(curr);

for i in curr:
    print(i, end = "");

Submission status: Accepted

Solution code:
import queue

K = int(input())

q = queue.Queue()

for i in range(9):
  q.put(i+1)

for i in range(K-1):
  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(q.get())

Submission status: Accepted

Solution code:
K=int(input())
A=[1,2,3,4,5,6,7,8,9]
for _ in range(K-1):
    if K <= len(A): break
    K -= len(A)
    B=[]
    A,B=B,A
    for b in B:
        if b%10!=0: A.append(10*b+(b%10-1))
        A.append(10*b+b%10)
        if b%10!=9: A.append(10*b+(b%10+1))
print(A[K-1])

Submission status: Accepted

Solution code:
import sys
import heapq
k = int(input())
q = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 0
while q:
    cur = heapq.heappop(q)
    count += 1
    if (count == k):
        print(cur)
        sys.exit()
    else:
        if (cur % 10 != 0):
            heapq.heappush(q, (cur*10) + (cur%10) - 1)
        if (cur % 10 != 9):
            heapq.heappush(q, (cur * 10) + (cur % 10) + 1)
        heapq.heappush(q, (cur * 10) + (cur % 10))

Submission status: Accepted

Solution code:
from collections import deque
que = deque()
L = []
k = int(input())
for i in range(1, 10):
  L.append(str(i))
  que.append(str(i))
while len(L) < k:
  top = que.popleft()
  e = int(top[-1])
  for i in range(max(e-1, 0), min(e+2, 10)):
    x = top + str(i)
    L.append(x)
    que.append(x)
ans = L[k-1]
print(ans)