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())
List=[1,2,3,4,5,6,7,8,9]
N=0
M=9
while len(List)<K:
    for i in range(N,M):
        last_number=List[i]%10
        times10=10*List[i]
        if last_number!=0:
            List.append(times10+last_number-1)
        List.append(times10+last_number)
        if last_number!=9:
            List.append(times10+last_number+1)
    N=M
    M=len(List)
   

print(List[K-1])

Submission status: Accepted

Solution code:
import queue
q = queue.Queue()
K = int(input())
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:

count = 1

def cal(k, num, digit):
  global count
  if digit == 0:
    if count == k:
      print(num)
      exit()

    count += 1

  else:
    base = int(str(num)[-digit - 1])
    bottom = base - 1 if base > 0 else base
    head = base + 2 if base < 9 else base + 1

    for i in range(bottom, head):
      i = i * 10**(digit - 1) if digit > 1 else i
      cal(k, num + i, digit - 1)


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

  digit = 0
  while True:
    for i in range(1, 10):
      cal(k, i * 10**digit, digit)

    digit += 1

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

K = int(read())

pre_lis = []
for i in range(1,10):
    pre_lis.append(str(i))
    
ct = 9
if K <= 9:
    print(pre_lis[K-1])
else:
    new_lis = []
    flag = False
    while ct < K:
        for num in pre_lis:
            pre_num = int(num[-1])
            for i in range(10):
                if abs(pre_num-i) <= 1:
                    new_lis.append(num + str(i))
                    ct+=1
                    if ct == K:
                        print(new_lis[-1])
                        flag = True
                        break
            pre_lis = new_lis
            if flag:
                break
        if flag:
            break

Submission status: Accepted

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

for j in range(9):
    b = []
    for i in a[-1]:
        I = str(i)
        if I[-1] != '9':
            b.append(i*10 + int(I[-1])+1)
        b.append(i*10 + int(I[-1]))
        if I[-1] != '0':
            b.append(i*10 + int(I[-1])-1)
    a.append(b)
    A += b
ans = sorted(A)
print(ans[k-1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
l = [int(x) for x in range(1,10)]
lnln = deque(l)
Lnln = []
# print(lnln)
n = 10**5
for i in range(n):
    x = lnln.popleft()
    Lnln.append(x)
    a = x % 10
    
    if a!=0:
        lnln.append(x*10 + (a-1))
        
    lnln.append(x*10 + a)
        
    if a!=9:
        lnln.append(x*10 + (a+1))
        
print(Lnln[k-1])

Submission status: Accepted

Solution code:
k = int(input())

a = [str(i) for i in range(1,10)]

for i in range(40000):
    if a[i][-1] == '0':
        a.append(str(a[i])+'0')
        a.append(str(a[i])+'1')
    elif a[i][-1] == '9':
        a.append(str(a[i])+'8')
        a.append(str(a[i])+'9')
    elif a[i][-1] != '0' and a[i][-1] != '9':
        a.append(str(a[i]) + str(int(a[i][-1])-1))
        a.append(str(a[i]) + str(int(a[i][-1])))
        a.append(str(a[i]) + str(int(a[i][-1])+1))

print(a[k-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k = int(input())
if k <= 9:
    print(k)
    exit()
a = [i for i in range(1, 10)]
cnt = 9
idx = 0
while cnt < k:
    a_ = str(a[idx])
    t = a_[-1]
    if t == "0":
        l_ = [0, 1]
    elif t == "9":
        l_ = [8, 9]
    else:
        l_ = [int(t)-1, int(t), int(t)+1]
    for i in l_:
        a.append(int(a_ + str(i)))
    cnt += len(l_)
    idx += 1
print(a[-(cnt-k+1)])

Submission status: Accepted

Solution code:
import itertools
k = int(input())
lun = [[1,2,3,4,5,6,7,8,9]]
lun_flatten = [1,2,3,4,5,6,7,8,9]
def l(n):
    tmp = lun[n-2]
    ans = []
    for i in tmp:
        a = int(str(i)[-1])
        t = 10 * i + a
        if a != 0:
            ans.append(t - 1)
        ans.append(t)
        if a != 9:
            ans.append(t+1)
    lun.append(ans)

i = 2
while len(lun_flatten) < k:
    l(i)
    lun_flatten =  list(itertools.chain.from_iterable(lun))
    i += 1

print(lun_flatten[k-1])

Submission status: Accepted

Solution code:
from collections import deque

k=int(input())
d=deque(range(1,10))

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:
from collections import deque
K = int(input())
d = deque(range(1, 10))
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:
K=int(input())

from collections import deque

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

k=1
while True:
    a=d.popleft()
    if k==K:
        print(a)
        exit()
    else:
        k+=1
    r=a%10
    if 0<r<=9:
        temp = a * 10 + (r -1)
        d.append(temp)
    temp=a*10+r
    d.append(temp)
    if 0<=r<9:
        temp=a*10+(r+1)
        d.append(temp)

Submission status: Accepted

Solution code:
K=int(input())

from collections import deque

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

k=1
while True:
    a=d.popleft()
    if k==K:
        print(a)
        exit()
    else:
        k+=1
    r=a%10
    if r==0:
        for i in [0,1]:
            temp=a*10+i
            d.append(temp)
    elif r==9:
        for i in [8,9]:
            temp=a*10+i
            d.append(temp)
    else:
        for i in [-1,0,1]:
            temp=a*10+(r+i)
            d.append(temp)

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
q=deque(range(1,10))
for i in range(k):
    x=q.popleft()
    if x%10!=0:
        q.append(10*x+x%10-1)
    q.append(10*x+x%10)
    if x%10!=9:
        q.append(10*x+x%10+1)
print(x)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# input
N = int(input())

# check
c = [list(range(1, 10))]
for i in range(9):
    tmp = []
    append = tmp.append
    for val in c[-1]:
        if val % 10 != 0:
            append(val * 10 + (val % 10 - 1))
        append(val * 10 + (val % 10))
        if val % 10 != 9:
            append(val * 10 + (val % 10 + 1))
    c.append(tmp)

ans = []
set = ans.append
for i in range(len(c)):
    for val in c[i]:
        set(val)

ans.sort()
print(ans[N - 1])

Submission status: Accepted

Solution code:
K=int(input())

if K<=12:
    print(K)
    exit()

from collections import deque

d=deque(["2","3","4","5","6","7","8","9","10","11","12"])
num=[1,2,3,4,5,6,7,8,9,10,11,12]

while True:
    s=d.popleft()
    x=int(s[-1])
    if x==0:
        for i in ["0","1"]:
            temp=s+i
            d.append(temp)
            num.append(int(temp))

    elif x==9:
        for i in ["8","9"]:
            temp=s+i
            d.append(temp)
            num.append(int(temp))
    else:
        for j in [-1,0,1]:
            temp=s+str(x+j)
            d.append(temp)
            num.append(int(temp))
    if len(num)>=K:
        print(num[K-1])
        exit()

Submission status: Accepted

Solution code:
K=int(input())

if K<=12:
    print(K)
    exit()

k=12

from collections import deque

d=deque(["2","3","4","5","6","7","8","9","10","11","12"])

while True:
    s=d.popleft()
    x=int(s[-1])
    if x==0:
        for i in ["0","1"]:
            temp=s+i
            d.append(temp)
            k+=1
            if k==K:
                print(temp)
                exit()
    elif x==9:
        for i in ["8","9"]:
            temp=s+i
            d.append(temp)
            k+=1
            if k==K:
                print(temp)
                exit()
    else:
        for j in [-1,0,1]:
            temp=s+str(x+j)
            d.append(temp)
            k+=1
            if k==K:
                print(temp)
                exit()

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(1, int(1e5 + 1)):
    n = q.get()
    if i == k:
        print(n)
        exit()
    if n % 10 != 0:
        q.put(n * 10 + (n - 1) % 10)
    q.put(n * 10 + n % 10)
    if n % 10 != 9:
        q.put(n * 10 + (n + 1) % 10)

Submission status: Accepted

Solution code:
k = int(input())
if k < 10:
    print(k)
    exit()
l = list(range(1, 10))
for i in l:
    for j in range(max(i % 10 - 1, 0), min(i % 10 + 2, 10)):
        l += [i * 10 + j]
    if len(l) > k:
        break
print(l[k - 1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

def lunlun(n):
  d = deque(range(1, 10))
  
  for i in range(n):
    x = d.popleft()
    if x%10 != 0:
      d.append(x*10 + x%10 - 1)
    d.append(x*10 + x%10)
    if x%10 != 9:
      d.append(x*10 + x%10 + 1)
  
  return x

print(lunlun(k))

Submission status: Accepted

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

Q = deque([i for i in range(1, 10)])    #Queue
for i in range(k):
    inum = Q[0] #important number
    op = inum % 10  #one place
    Q.popleft()
    for j in [-1, 0, 1]:
        if 0 <= op+j and op+j <= 9:
            Q.append(inum*10+(op+j))
        else:
            pass

ans = inum
print(ans)

Submission status: Accepted

Solution code:
k = int(input())

B = [1, 2, 3, 4, 5, 6, 7, 8, 9] #Before list
while len(B) < k:
    k -= len(B)
    #次の桁に更新
    def update_next_digit(B:list)->list:
        N = []  #New list
        for i in range(len(B)):
            op = B[i] % 10  #one place   
            for j in [-1, 0, 1]:
                if 0 <= op+j and op+j <= 9:
                    N.append(B[i]*10+(op+j))
                else:
                    pass
        return N
    N = update_next_digit(B)
    B = N

ans = B[k-1]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    def dfs(depth, max_depth, num):
        if depth==max_depth:
            lunlun_temp.append(''.join([str(i) for i in num]))
        elif depth==0:
            for i in range(1, 10):
                dfs(depth+1, max_depth, num+[i])
        else:
            for i in range(3):
                if 0<=num[-1]-1+i<=9:
                    dfs(depth+1, max_depth, num+[num[-1]-1+i])

    lunlun = []

    i = 1
    while len(lunlun)<K:
        lunlun_temp = []
        dfs(0, i, [])
        lunlun += lunlun_temp
        i += 1

    print(lunlun[K-1])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
k = int(input())

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

cnt = 9
l = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]

def check():
    if cnt == k:
        print(memo[-1])
        exit()

while True:
    memo = []
    for i in l:
        if i[-1] == "0":
            memo.append(i+"0")
            cnt += 1
            check()

            memo.append(i+"1")
            cnt += 1
            check()

        elif i[-1] == "9":
            memo.append(i+"8")
            cnt += 1
            check()

            memo.append(i+"9")
            cnt += 1
            check()

        else:
            memo.append(i + str(int(i[-1])-1))
            cnt += 1
            check()

            memo.append(i + i[-1])
            cnt += 1
            check()

            memo.append(i + str(int(i[-1]) + 1))
            cnt += 1
            check()

    l = memo[:]

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import queue

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

a=0

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

print(a)

Submission status: Accepted

Solution code:
# import numpy as np


def solve():
    print(ll_no_dup[k-1])
    return






#a = [int(i) for i in input().split(" ")]




lunluns = [str(i) for i in range(1, 10)]

it = 0
count = 0
all_count = len(lunluns)
while count <= 10 ** 5:
    it = len(lunluns)
    last_count = all_count
    all_count = 0
    for i in range(it-last_count, it):
        last_val = int(lunluns[i][-1])
        if last_val > 0:
            lunluns.append(lunluns[i] + str(last_val - 1))
            count += 1
            all_count +=1
        lunluns.append(lunluns[i] + str(last_val))
        count += 1
        all_count +=1
        if last_val < 9:
            lunluns.append(lunluns[i] + str(last_val + 1))
            count += 1
            all_count +=1
        if count > 10 ** 5:
            break

ll_no_dup = [str(1)]
for i in range(1, len(lunluns)):
    if lunluns[i]!=lunluns[i-1]:
        ll_no_dup.append(lunluns[i])



k = int(input())
solve()

Submission status: Accepted

Solution code:
n=int(input())
ans=[0 for i in range(10**5+21)]
Q=[0,1,2,3]
def li(x):
  if x==0 : return [0,1]
  if x==9 : return [8,9]
  return [x-1,x,x+1]

now=0
for q in Q:
  W=[i for i in range(10)] if q==0 else li(q)
  for w in W:
    E=[i for i in range(10)] if [q,w]==[0,0] else li(w)
    for e in E:
      R=[i for i in range(10)] if [q,w,e]==[0,0,0] else li(e)
      for r in R:
        T=[i for i in range(10)] if [q,w,r,e]==[0,0,0,0] else li(r)
        for t in T:
          Y=[i for i in range(10)] if [q,w,e,r,t]==[0,0,0,0,0] else li(t)
          for y in Y:
            U=[i for i in range(10)] if [q,w,e,r,t,y]==[0,0,0,0,0,0] else li(y)
            for u in U:
              I=[i for i in range(10)] if [q,w,e,r,t,y,u]==[0,0,0,0,0,0,0] else li(u)
              for i in I:
                O=[i for i in range(10)] if [q,w,e,r,t,y,u,i]==[0,0,0,0,0,0,0,0] else li(i)
                for o in O:
                  P=[i for i in range(10)] if [q,w,e,r,t,y,u,i,o]==[0,0,0,0,0,0,0,0,0] else li(o)
                  for p in P:
                    
                    ans[now]= 10**9*q + 10**8*w + 10**7*e + 10**6*r + 10**5*t + 10**4*y + 1000*u + 100*i + 10*o + p
                    
                    if now>=10**5+2 : break
                    now+=1


print(ans[n])

Submission status: Accepted

Solution code:
n=int(input())
if n<=10 : 
  print(n)
  exit()
  
ans=[0 for i in range(10**5+21)]
Q=[0,1,2,3]
def li(x):
  if x==0 : return [0,1]
  if x==9 : return [8,9]
  return [x-1,x,x+1]

now=0
for q in Q:
  W=[i for i in range(10)] if q==0 else li(q)
  for w in W:
    E=[i for i in range(10)] if [q,w]==[0,0] else li(w)
    for e in E:
      R=[i for i in range(10)] if [q,w,e]==[0,0,0] else li(e)
      for r in R:
        T=[i for i in range(10)] if [q,w,r,e]==[0,0,0,0] else li(r)
        for t in T:
          Y=[i for i in range(10)] if [q,w,e,r,t]==[0,0,0,0,0] else li(t)
          for y in Y:
            U=[i for i in range(10)] if [q,w,e,r,t,y]==[0,0,0,0,0,0] else li(y)
            for u in U:
              I=[i for i in range(10)] if [q,w,e,r,t,y,u]==[0,0,0,0,0,0,0] else li(u)
              for i in I:
                O=[i for i in range(10)] if [q,w,e,r,t,y,u,i]==[0,0,0,0,0,0,0,0] else li(i)
                for o in O:
                  P=[i for i in range(10)] if [q,w,e,r,t,y,u,i,o]==[0,0,0,0,0,0,0,0,0,0] else li(o)
                  for p in P:
                    
                    ans[now]= 10**9*q + 10**8*w + 10**7*e + 10**6*r + 10**5*t + 10**4*y + 1000*u + 100*i + 10*o + p
                    
                    if now>=10**5+2 : break
                    now+=1

ans=list(set(ans))
n-=8
ans.sort()
print(ans[n])

Submission status: Accepted

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

q = 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:
k = int(input())
dp = [[0 for _ in range(10)] for __ in range(50)]
wa = [[0 for _ in range(10)] for __ in range(50)]

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

for j in range(10):
    dp[0][j] = 1
    wa[0][j] = j

isFinish =False
for i in range(1,15):
    for j in range(10):
        dp[i][j] = dp[i-1][j]
        if j > 0:
            dp[i][j] += dp[i-1][j-1]
        if j < 9:
            dp[i][j] += dp[i-1][j+1]
        if j == 0: continue
        if j == 1:
            wa[i][j] = wa[i-1][9] + dp[i][j]
        else:
            wa[i][j] = wa[i][j-1] + dp[i][j]
        if wa[i][j] >= k:
            keta = i
            num = j
            isFinish = True
            break
    if isFinish: break
ans = 0
k -= wa[keta][num-1] if num > 1 else wa[keta-1][9]
while keta+1:
    ans += num * pow(10,keta)
    if keta ==0:
        break

    for i  in range(3):
        nextnum = num + i-1
        if nextnum < 0 or nextnum > 9:
            continue
        k -= dp[keta-1][nextnum]
        if k <= 0:
            k += dp[keta-1][nextnum]
            num = nextnum
            break
    keta -= 1
print(ans)

Submission status: Accepted

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

from collections import deque

K = int(input())
cnt = 0
q = deque()

for i in range(1, 10):
    q.append((str(i), i))
    cnt += 1
    if cnt == K:
        print(str(i))
        exit()

while q:
    lun, num = q.popleft()
    
    for i in range(num - 1, num + 2):
        if  i < 0 or i > 9:
            continue
        temp = lun + str(i)
        q.append((temp, i))
        cnt += 1
        if cnt == K:
            print(temp)
            exit()

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
def bfs():
    q=deque([])
    for i in range(1,10):
        q.append(str(i))
    cnt=0
    while cnt<k:
        cnt+=1
        x=q.popleft()
        r=int(x[-1])
        if 1<=r:
            q.append(x+str(r-1))
        q.append(x+str(r))
        if r<=8:
            q.append(x+str(r+1))
    return x
print(bfs())

Submission status: Accepted

Solution code:
K = int(input())
counter = 0
level = 1
theList = []
PreLevelStart,PreLevelEnd = 0,0
while counter < K:
    levelStart = counter
    if level == 1:
        for i in range(1,10,1):
            theList.append(i)
            counter += 1
    else:
        for i in range(PreLevelStart,PreLevelEnd):
            if theList[i]%10 == 0:
                theList.append(theList[i]*10)
                counter+=1
                theList.append(theList[i]*10+1)
                counter+=1
            elif theList[i]%10 == 9:
                theList.append(theList[i]*10+8)
                counter+=1
                theList.append(theList[i]*10+9)
                counter+=1
            else:
                theList.append(theList[i]*10+theList[i]%10-1)
                counter+=1
                theList.append(theList[i]*10+theList[i]%10)
                counter+=1
                theList.append(theList[i]*10+theList[i]%10+1)
                counter+=1
    PreLevelStart = levelStart
    PreLevelEnd = counter
    level = level+1
print(theList[K-1])

Submission status: Accepted

Solution code:
from collections import deque
d = deque()

k = int(input())

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

print(x)

Submission status: Accepted

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

q = deque()
for i in range(1, 10):
    q.append((str(i), i))
    cnt += 1
    if cnt == k:
        print(str(i))
        exit()

while q:
    lun, num = q.popleft()

    for i in range(num - 1, num + 2):
        if i < 0 or i >9:continue
        temp = lun + str(i)
        q.append((temp, i))
        cnt += 1
        if cnt == k:
            print(temp)
            exit()

Submission status: Accepted

Solution code:
from collections import deque

def solve(k):
    v = []
    que = deque([x for x in range(1, 10)])
    while len(v) <= k:
        x = que.popleft()
        v.append(x)
        i = x % 10
        for j in range(max(0,i-1), min(10,i+2)):
            nx = 10*x + j
            que.append(nx)
    return sorted(v)[k-1]

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

Submission status: Accepted

Solution code:
k = int(input())

a = list()
b = list()
a2 = list()
for i in range(10):
    a.append(i)
b.extend(a)
a2.extend(a)
for i in range(10):
    a = list()
    dig = 10 ** i
    for c in a2:
        tmpc = c//dig
        min = tmpc - 1
        if min < 0:
            min = 0
        max = tmpc + 1
        if max > 9:
            max = 9
        for j in range(min,max+1):
            a.append(j*10*dig+c)
    b.extend(a)
    a2 = a
    #a2.append(0)
b=list(set(b))
b.sort()
print(b[k])

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
x = deque([1,2,3,4,5,6,7,8,9])
cnt = 0
while True:
    v = x.popleft()
    if cnt == K-1 :
        break
    cnt += 1
    if v % 10 == 0:
        v = v *10
        x.append(v)
        v = v + 1
        x.append(v)
    else:
        if v % 10 == 9 :
            v = v * 10 + (v%10) - 1
            x.append(v)
            v += 1
            x.append(v)
        else:
            v = v * 10 + (v%10) - 1
            x.append(v)
            v += 1
            x.append(v)
            v += 1
            x.append(v)
print(v)

Submission status: Accepted

Solution code:
K=int(input())
 
from collections import deque
query=deque()
 
for i in range(1,10):
    query.append(i)
cnt=0

while cnt<K:
    num=query.popleft()
    cnt +=1
    one=num%10
    if one == 0:
        query.append(num*10+one )
        query.append(num*10+(one+1))
    if one!=0 and one!=9:
        query.append(num*10+(one-1))
        query.append(num*10+one)
        query.append(num*10+(one+1))
    if one == 9:
        query.append(num*10+(one-1))
        query.append(num*10+one)

print(num)

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

def solve(K):
    stack = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
    for _ in range(K):
        num = stack.popleft()
        one_digit = num % 10
        if one_digit % 10 == 0:
            nexts = [num * 10, num * 10 + 1]
        elif one_digit % 10 == 9:
            nexts = [num * 10 + 8, num * 10 + 9]
        else:
            nexts = [num * 10 + one_digit - 1, num * 10 + one_digit, num * 10 + one_digit + 1]

        for n in nexts:
            stack.append(n)
    return num

if __name__ == '__main__':
    K = int(input())
    print(solve(K))

Submission status: Accepted

Solution code:
k = int(input())
queue = [1,2,3,4,5,6,7,8,9]
count = 0
for i in range(0,k-1):
    x = queue[i]
    if x % 10 != 0:
        queue.append( 10*x + pow(x,1,10) - 1)
    queue.append(10*x + pow(x,1,10))
    if x %10 != 9:
        queue.append(10*x + pow(x,1,10) + 1)
print(queue[k-1])

Submission status: Accepted

Solution code:
K=int(input())
queue=[1,2,3,4,5,6,7,8,9]
count=0
for i in range(K-1):
    t=queue[i]
    if t%10!=0:
        queue.append(t*10+pow(t,1,10)-1)
    queue.append(t*10+pow(t,1,10))
    if t%10!=9:
        queue.append(t*10+pow(t,1,10)+1)
print(queue[K-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
K = int(input())
if K <= 9:
	print(K)
	sys.exit()
q = deque(['1', '2','3','4','5','6','7','8','9'])
cnt = 0
while True:
	cp = q.popleft()
	cnt += 1
	if cnt == K:
		ans = int(cp)
		break
	r = int(cp[-1])
	for d in [-1,0,1]:
		dd = r + d
		if 0 <= dd < 10:
			q.append(cp + str(dd))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

lun = deque([])
for i in range(1,10):
    lun.append(i)

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:
import queue

K = int(input())
q = queue.Queue()
count=0

for i in range(1,10):
    q.put(i)
x=0
while True:
    count+=1
    x = q.get()

    if count==K:
        break

    xmod10 = x%10

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

    q.put(10*x + xmod10)

    if xmod10 != 9:
        q.put(10*x + xmod10 + 1)

print(x)

Submission status: Accepted

Solution code:
def main():
    k = int(input())
    if k <= 9:
        print(k)
        exit()
    count = 9
    l = [i for i in range(1,10)]
    while True:
        ins_l = []
        for x in l:
            y = x % 10
            if y != 0:
                z = x * 10 + y - 1
                ins_l.append(z)
                count += 1
                if count == k:
                    print(z)
                    exit()

            z = x * 10 + y
            ins_l.append(z)
            count += 1
            if count == k:
                print(z)
                exit()

            if y != 9:
                z = x * 10 + y + 1
                ins_l.append(z)
                count += 1
                if count == k:
                    print(z)
                    exit()
        l = ins_l

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
ans = 1
q = deque()
for i in range(1, 10):
    q.append(i)

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

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

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

print(x)

Submission status: Accepted

Solution code:
K = int(input())
a = ["1","2","3","4","5","6","7","8","9"]
for i in range(K):
    if  a[i][-1] == "9":
        a.append(a[i]+str(int(a[i][-1])-1))
        a.append(a[i]+str(int(a[i][-1])))
    elif a[i][-1] == "0":
        a.append(a[i]+str(int(a[i][-1])))
        a.append(a[i]+str(int(a[i][-1])+1))
    else:
        a.append(a[i]+str(int(a[i][-1])-1))
        a.append(a[i]+str(int(a[i][-1])))
        a.append(a[i]+str(int(a[i][-1])+1))
print(a[K-1])

Submission status: Accepted

Solution code:
K = int(input())
a = ["1","2","3","4","5","6","7","8","9"]
for i in range(K):
    if  a[i][-1] == "9":
        a.append(a[i]+str(int(a[i][-1])-1))
        a.append(a[i]+str(int(a[i][-1])))
    elif a[i][-1] == "0":
            a.append(a[i]+str(int(a[i][-1])))
            a.append(a[i]+str(int(a[i][-1])+1))
    else:
            a.append(a[i]+str(int(a[i][-1])-1))
            a.append(a[i]+str(int(a[i][-1])))
            a.append(a[i]+str(int(a[i][-1])+1))
print(a[K-1])

Submission status: Accepted

Solution code:
def solve(K):
    ref = [[['0'], ['1'], ['2'], ['3'], ['4'], ['5'], ['6'], ['7'], ['8'], ['9']]]
    if K < 10:
        return ref[0][K][0]

    rest = K - 9
    i = 0
    while True:
        i += 1
        ref.append([[] for _ in range(10)])
        for j in range(10):
            if j == 0:
                for r in ref[i-1][j] + ref[i-1][j+1]:
                    ref[i][j].append(str(j) + r)
            elif j == 9:
                for r in ref[i-1][j-1] + ref[i-1][j]:
                    ref[i][j].append(str(j) + r)
                    rest -= 1
                    if rest == 0:
                        return str(j) + r
            else:
                for r in ref[i-1][j-1] + ref[i-1][j] + ref[i-1][j+1]:
                    ref[i][j].append(str(j) + r)
                    rest -= 1
                    if rest == 0:
                        return str(j) + r

if __name__ == '__main__':
    K = int(input())
    print(solve(K))

Submission status: Accepted

Solution code:
k = int(input())
lundex = [1,2,3,4,5,6,7,8,9]
count = 9
for i in lundex:
    for j in range(0,10):
        new = str(i)+str(j)
        l = len(new)
        if abs(int(new[l-2])-int(new[l-1]))<=1:
            lundex.append(int(new))
            count += 1
        if count >= k:
            break
    if count >= k:
        break
print(lundex[k-1])

Submission status: Accepted

Solution code:
K = int(input())
dic = {i+1:[] for i in range(11)}

dic[1] = [str(i+1) for i in range(9)]

if K < 10:
    print(dic[1][K-1])
else:
    cnt = 9
    ans = -1
    for i, nums in dic.items():
        for n in nums:
            ds = n[-1]
            dd = int(ds)
            if dd > 0:
                dic[i+1].append(n + str(int(ds)-1))
                cnt += 1
            dic[i+1].append(n + str(int(ds)))
            cnt += 1
            if dd < 9:
                dic[i+1].append(n + str(int(ds)+1))
                cnt += 1
        if cnt >= K:
            ans = dic[i+1][K-cnt-1]
            break
    print(ans)