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())

lst = [1,2,3,4,5,6,7,8,9]
count = 0

for i in range(k):
    num = lst[count]
    if num%10!=0:
        lst.append(num*10+num%10-1)
    lst.append(num*10+num%10)
    if num%10!=9:
        lst.append(num*10+num%10+1)
    count += 1

print(lst[k-1])

Submission status: Accepted

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

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

c = 0
while not q.empty():
  c += 1
  x = q.get()
  if c == k:
    print(x)
    break
  y = x%10
  if y != 0:
    q.put(10*x+y-1)
  q.put(10*x+y)
  if y != 9:
    q.put(10*x+y+1)

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
q = deque()
for i in range(1, 10):
    q.append(i)
for _ in range(k):
    p = q.popleft()
    r = p % 10
    if r != 0:
        q.append(10 * p + r - 1)
    q.append(10 * p + r)
    if r != 9:
        q.append(10 * p + r + 1)
print(p)

Submission status: Accepted

Solution code:
from collections import deque

K=int(input())
q=deque()
for i in range(1,10):
    q.append(str(i))

while K>0:
    n=q.popleft()
    t=int(n[-1])
    K-=1

    for i in range(max(0,t-1),min(9,t+1)+1):
        q.append(n+str(i))

print(n)

Submission status: Accepted

Solution code:
k=int(input())
unta=[[],[],[],[],[],[],[],[],[],[],[],[]]
unta[1]=["1","2","3","4","5","6","7","8","9"]
for keta in range(2,12):
	for i in range(len(unta[keta-1])):
		if unta[keta-1][i][keta-2]=="0":
			unta[keta].append(unta[keta-1][i]+"0")
			unta[keta].append(unta[keta-1][i]+"1")
		elif unta[keta-1][i][keta-2]=="9":
			unta[keta].append(unta[keta-1][i]+"8")
			unta[keta].append(unta[keta-1][i]+"9")
		else:
			unta[keta].append(unta[keta-1][i]+str(int(unta[keta-1][i][keta-2])-1))
			unta[keta].append(unta[keta-1][i]+unta[keta-1][i][keta-2])
			unta[keta].append(unta[keta-1][i]+str(int(unta[keta-1][i][keta-2])+1))
unchi=[]
for i in range(11):
	unchi+=unta[i]
print(unchi[k-1])

Submission status: Accepted

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

Submission status: Accepted

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

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

while num<k:
    i = q.get()
    l = i%10
    if l!=0:
        q.put(i*10+l-1)
    q.put(i*10+l)
    if l!=9:
        q.put(i*10+l+1)
    num += 1

print(i)

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
count = 0
q = deque(range(1,10))

while count < k:
    l = q.popleft()
    resid = l % 10
    if resid != 0: q.append(l*10 + resid - 1)

    q.append(l*10 + resid)
    
    if resid != 9: q.append(l*10 + resid + 1)
    
    count += 1

print(l)

Submission status: Accepted

Solution code:
from collections import deque
import sys

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))

K = read_int()[0]

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

def solve():
    for _ in range(K - 1):
        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))
    return q.popleft()

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def dfs(n):
    if n > 3234566667:
        return
    ans.append(n)
    if n % 10 != 0:
        dfs(n * 10 + (n % 10) - 1)
    dfs(n * 10 + (n % 10))
    if n % 10 != 9:
        dfs(n * 10 + (n % 10) + 1)

N = int(input())
ans = []
for i in range(1, 10):
    dfs(i)
ans.sort()
print(ans[N - 1])

Submission status: Accepted

Solution code:
# coding: utf-8
K = int(input())
st_lib = '0123456789'

memory = []
def search(s):
    if len(s) == 11:
        memory.append(int(s))
        return
    last_s = int(s[-1])
    if s == '0' * len(s):
        patterns = st_lib
    else:
        patterns = st_lib[max([last_s-1, 0]):last_s+2]
    for next in patterns:
        search(s+next)

if __name__ == '__main__':
    search('0')
    memory = sorted(memory)
    print(memory[K])

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

k = ni()

def bfs():
    q = deque()
    for n in range(1, 10):
        q.append(n)
    i = 1
    while len(q):
        p = q.popleft()
        if i == k:
            return p
        i += 1
        if p % 10 != 0:
            q.append(p * 10 + (p % 10 - 1))
        q.append(p * 10 + p % 10)
        if p % 10 != 9:
            q.append(p * 10 + (p % 10 + 1))

print(bfs())

Submission status: Accepted

Solution code:
import copy
def lunlun_check(i,j):
    if abs(i-j) > 1:
        return False
    return True

k = int(input())
ret_list = []
lunlun_list = []
cnt = 0
cnt_pre = 0
digit = 1
while k > (cnt-1):
    cnt_pre = cnt
    tmp_list = []
    ret_list.clear()
    if not lunlun_list:
        for i in range(10):
            tmp_list.append(str(i))
            ret_list.append(i)
    else:
        for i in range(10):
            for data in lunlun_list:
                if lunlun_check(i, int(data[0])):
                    tmp_list.append(str(i)+data)
                    if len(str(int(str(i)+data))) == digit:
                        ret_list.append(int(str(i)+data))
    lunlun_list = tmp_list.copy()
    cnt += len(ret_list)
    digit += 1
print(int( ret_list[k- cnt_pre] ))

Submission status: Accepted

Solution code:
K=int(input())
lists=[]
for i in range(1,10):
    lists.append(i)
if K<=9:
    print (K)
else:
    for i in range(K):
        if lists[i]%10==0:
            lists.append(lists[i]*10+lists[i]%10)
            lists.append(lists[i]*10+lists[i]%10+1)
        elif lists[i]%10==9:
            lists.append(lists[i]*10+lists[i]%10-1)
            lists.append(lists[i]*10+lists[i]%10)
        else:
            lists.append(lists[i]*10+lists[i]%10-1)
            lists.append(lists[i]*10+lists[i]%10)
            lists.append(lists[i]*10+lists[i]%10+1)
    print (lists[K-1])

Submission status: Accepted

Solution code:
from collections import deque
a=int(input())
list1=deque([1,2,3,4,5,6,7,8,9])
i=1
while(i<=a) :
  #print (list1)
  if i!=a :
    k=list1.popleft()
    k=str(k)
    if int(k[-1])==0 :
      list1.append(int(str(k)+'0'))
      list1.append(int(str(k)+'1'))
      i+=1
    elif int(k[-1])==9 :
      list1.append(int(str(k)+'8'))
      list1.append(int(str(k)+'9'))
      i+=1
    else :
      list1.append(int(str(k)+str(int(k[-1])-1)))
      list1.append(int(str(k)+str(int(k[-1]))))
      list1.append(int(str(k)+str(int(k[-1])+1)))
      i+=1
  else :
    print(list1[0])
    break

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

  while q:
    a=q.popleft()
    n-=1

    if n==0:
      return a

    _a=a%10
    for i in range(max(0,_a-1),min(10,_a+2)):
      b=int(str(a)+str(i))
      q.append(b)

# main()
print(main())

Submission status: Accepted

Solution code:
from collections import deque


def main():
    k = int(input())
    queue = deque([i for i in range(1, 10)])
    pop_time = 0
    now = 1
    while pop_time < k:
        now = queue.popleft()
        if now % 10 != 0:
            queue.append(10 * now + now % 10 - 1)
        queue.append(10 * now + now % 10)
        if now % 10 != 9:
            queue.append(10 * now + now % 10 + 1)
        pop_time += 1
    print(now)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
K=int(input())
cnt=0
dp=[0]*(10**6)
piv=0
dig=[0]*10000
d=0
cnt=float("inf")
zure=0
befnum=0
i=0
buf=""
cntall=0
ans=[]
"""なんだこの
while i<2*(10**5):
    if i+1<10:
        dp[i]=i+1
        dig[d]=dig[d]+1
    else:
        if cnt>=dig[d-1]:
            i=i+zure
            zure=0
            cnt=0
            befnum=dig[d]
            d=d+1
        #print(i,befnum)
        buf=str(dp[i-befnum])
        piv=buf[len(buf)-1]
        #print(buf, piv,i-befnum)
        #print(dp,dig,zure,i,dig[i],dp[i-befnum],befnum)
        if int(piv)==0:
            dp[i+zure]=dp[i-befnum]*10
            dp[i+1+zure]=dp[i - befnum] * 10+1
            dig[d]=dig[d]+2
            zure=zure+1
        elif int(piv)==9:
            dp[i + zure] = dp[i - befnum] * 10+8
            dp[i + 1 + zure] = dp[i - befnum] * 10+9
            dig[d] = dig[d] + 2
            zure = zure + 1
        else:
            dp[i+zure]=dp[i-befnum]*10+int(piv)-1
            dp[i+1+zure]=dp[i - befnum] * 10+int(piv)
            dp[i+2+zure] = dp[i - befnum] * 10 + int(piv)+1
            dig[d] = dig[d] + 3
            zure=zure+2
        cnt=cnt+1
    i=i+1
    #if i%20000==0:
        #print(i)
    #print(dp)
    #input()
print(dp[K-1])
"""
#dequeでやればめっちゃ楽だった…
d=deque()
piv=0
num=0
for i in range(9):
    d.append(i+1)
#print(d)
i=0
while i<K:
    num=d.popleft()
    ans.append(num)
    piv=str(num)
    if piv[len(piv)-1]=="0":
        d.append(num*10)
        d.append(num*10+1)
    elif piv[len(piv)-1]=="9":
        d.append(num*10+8)
        d.append(num * 10 + 9)
    else:
        d.append(num*10+int(piv[len(piv)-1])-1)
        d.append(num*10+int(piv[len(piv)-1]))
        d.append(num * 10 + int(piv[len(piv) - 1])+1)
    i=i+1
    #print(d,ans)
    #input()
print(ans[K-1])

Submission status: Accepted

Solution code:
K=int(input())
A=[1,2,3,4,5,6,7,8,9]+[0]*K
i=9
j=0
while i<K:
    if A[j]%10!=0 and A[j]%10!=9:
        A[i]=10*A[j]+A[j]%10-1;i+=1
        A[i]=10*A[j]+A[j]%10;i+=1
        A[i]=10*A[j]+A[j]%10+1;i+=1
    elif A[j]%10==0:
        A[i]=10*A[j]+A[j]%10;i+=1
        A[i]=10*A[j]+A[j]%10+1;i+=1
    else:
        A[i]=10*A[j]+A[j]%10-1;i+=1
        A[i]=10*A[j]+A[j]%10;i+=1
    j+=1
print(A[K-1])

Submission status: Accepted

Solution code:
k=int(input())

q=[1,2,3,4,5,6,7,8,9]
c=0
for i in range(k):
    num=q[c]
    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)
    c+=1
print(q[k-1])

Submission status: Accepted

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

k = int(input())

cnt = 0
while k > cnt:
  x = d.popleft()
  cnt += 1  
  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)
print(x)

Submission status: Accepted

Solution code:
import queue

k = 0

def format_input(filename = None):
	global k
	if filename == None:
		k = int(input())

	elif filename == '__random__':
		from random import randint as rng
		k = rng(1, 10**5)
		print(k)

def get_answer():
	q = queue.Queue()
	[q.put(i) for i in range(1, 10)]
	i = 0
	while i < k:
		answer = q.get()
		child = answer * 10 + answer % 10
		if child % 10 != 0:
			q.put(child - 1)
		q.put(child)
		if child % 10 != 9:
			q.put(child + 1)
		i += 1
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Accepted

Solution code:
def solve(n):
	if n<=9:
		return n
	q = [0]
	for i in range(1,10):
		q.append(i)
	now = 1
	cnt = 9
	while 1:
		u = q[now]
		now += 1
		if u%10!=0:
			t = u*10 + u%10 - 1
			cnt += 1
			if cnt==n:
				return t
			q.append(t)
		t = u*10 + u%10
		cnt += 1
		if cnt==n:
			return t
		q.append(t)
		if u%10 !=9:
			t = u*10 + u%10 + 1
			cnt += 1
			if cnt==n:
				return t
			q.append(t)

print(solve(int(input())))

Submission status: Accepted

Solution code:
from collections import deque

q=deque()

N=int(input())

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

for _ in range(N-1):
  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(q.popleft())

Submission status: Accepted

Solution code:
K=int(input())
num1=[[1,2,3,4,5,6,7,8,9]]
num2=[]
sm=0
for j in range(10):
    li=[]
    for k in range(len(num1[j])):
        if num1[j][k]%10!=0:
            li.append(num1[j][k]*10+num1[j][k]%10-1)
        li.append(num1[j][k]*10+num1[j][k]%10)
        if num1[j][k]%10!=9:
            li.append(num1[j][k]*10+num1[j][k]%10+1)
    li.sort()
    num1.append(li)
for j in range(len(num1)):
    sm+=len(num1[j])
    num2+=num1[j]
print(num2[K-1])

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:input()

"""========main code==============="""

x=ii()
lol=[1,2,3,4,5,6,7,8,9]
ans=9
if(x>9):
    for i in lol:
        k=str(i)
        a=int(k[len(k)-1])
        if(a-1>=0):
            lol.append(k+str(a-1))
            ans+=1
            if(ans==x):
                print(lol[x-1])
                break
        lol.append(k+str(a))
        ans+=1
        if(ans==x):
            print(lol[x-1])
            break
        if(a+1<=9):
            lol.append(k+str(a+1))
            ans+=1    
            if(ans==x):
                print(lol[x-1])
                break
else:
    print(lol[x-1])

Submission status: Accepted

Solution code:
import queue
K=int(input())
q = queue.Queue()

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

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

print(q.get())

Submission status: Accepted

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

Submission status: Accepted

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

def main():
    K = int(input())
    q = deque()
    for i in range(1, 10):
        if K == 1:
            print(i)
            exit()
        K -= 1
        q.append(i)
    while q:
        v = q.popleft()
        sv = int(str(v)[-1])
        for i in (-1, 0, 1):
            if 0 <= sv + i < 10:
                if K == 1:
                    print(v * 10 + sv + i)
                    exit()
                K -= 1
                q.append(v * 10 + sv + i)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
K = int(input())
l = [i + 1 for i in range(0, 9)]
heapq.heapify(l)
count = 1
ans = 0
while count < K:
    x = heapq.heappop(l)
    l_digit = x % 10
    if l_digit != 0:
        heapq.heappush(l, 10 * x + l_digit - 1)
    heapq.heappush(l, 10 * x + l_digit)
    if l_digit != 9:
        heapq.heappush(l, 10 * x + l_digit + 1)
    count += 1
print(heapq.heappop(l))

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):
    v = q.popleft()

    if v % 10 != 0:
        q.append(10 * v + v % 10 - 1)

    q.append(10 * v + v % 10)

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

print(v)

Submission status: Accepted

Solution code:
from collections import deque


K = int(input())

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

for _ in range(K-1):
    x = d.popleft()
    # x の1桁目を見る
    mod = x % 10
    if mod != 0:
        d.append(10 * x + mod - 1)
    d.append(10 * x + mod)
    if mod != 9:
        d.append(10 * x + mod + 1)

ans = d.popleft()
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

K=int(input())

def bfs(k):
    queue = deque()
    for i in range(1, 10):#1~9までをqueueに追加しておく
        queue.append(i)
    cnt = 1
    
    while queue:
        x = queue.popleft()#左から取り出すと、自動的に小さい順から取り出せる
        if cnt == k:
            return x
        cnt += 1 #これまでのルンルン数の数
        last = x%10 #末尾の数字
        if last > 0:
            queue.append(x*10+last-1)#x-1⇒x⇒x+1の順にを末尾に追加すると順番になる。0と9に注意
        queue.append(x*10+last)
        if last < 9:
            queue.append(x*10+last+1)
            
print(bfs(K))

Submission status: Accepted

Solution code:
maxn = 100005

def solve(n):
	if n<=9:
		return n
	q = [0 for i in range(maxn)]
	front = 1
	rear = 0
	for i in range(1,10):
		rear += 1
		q[rear] = i
	cnt = 9
	while 1:
		u = q[front]
		front += 1
		if u%10 != 0:
			t = u*10 + u%10 -1
			rear += 1
			q[rear] = t
			cnt += 1
			if cnt==n:
				return t
		t = u*10 + u%10
		rear += 1
		q[rear] = t
		cnt += 1
		if cnt==n:
			return t;
		if u%10 != 9:
			t = u*10 + u%10 + 1
			rear += 1
			q[rear] = t
			cnt += 1
			if cnt==n:
				return t

print(solve(int(input())))

Submission status: Accepted

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

q = queue.Queue()

ret = K
number_of_operations = 9
for i in range( 1, number_of_operations + 1 ):
  q.put( i )

while number_of_operations < K:
  i = q.get()
  k = i % 10 
  if k != 0:
    ret = 10 * i + k - 1
    q.put( ret )
    number_of_operations += 1
    if number_of_operations == K:
      break
  ret = 10 * i + k
  q.put( ret )
  number_of_operations += 1
  if number_of_operations == K:
    break

  if k != 9:
    ret = 10 * i + k + 1
    q.put( ret )
    number_of_operations += 1

print( ret )

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

print(x)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K = INT()

q = list(range(1, 10))
q = deque(q)

for _ in range(K):
	x = q.popleft()
	r = x%10
	if r > 0:
		q.append(10*x+(r-1))
	q.append(10*x+r)
	if r < 9:
		q.append(10*x+(r+1))
print(x)

Submission status: Accepted

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

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

Submission status: Accepted

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

K = int(input())

d = []
d.append([1] * 10)

for i in range(1, 10):
    m = []
    if i != 9:
        for j in range(10):
            if not j:
                m.append(d[i - 1][j] + d[i - 1][j + 1])
            elif j == 9:
                m.append(d[i - 1][j - 1] + d[i - 1][j])
            else:
                m.append(d[i - 1][j - 1] + d[i - 1][j] + d[i - 1][j + 1])
    else:
        for j in range(4):
            if not j:
                m.append(d[i - 1][j] + d[i - 1][j + 1])
            elif j == 9:
                m.append(d[i - 1][j - 1] + d[i - 1][j])
            else:
                m.append(d[i - 1][j - 1] + d[i - 1][j] + d[i - 1][j + 1])
    d.append(m)

n = 0
for i, x in enumerate(d):
    for j, y in enumerate(x):
        if not j:
            continue
        else:
            if n + y >= K:
                break
            else:
                n += y
    else:
        continue
    break

ans = []
am = K - n
ans = str(j)
for x in reversed(range(i)):
    if j != 0 and j != 9:
        if am <= d[x][j - 1]:
            ans += str(j - 1)
            j -= 1
        elif am <= d[x][j - 1] + d[x][j]:
            ans += str(j)
            am -= d[x][j-1]
        else:
            ans += str(j + 1)
            am -= d[x][j-1] + d[x][j]
            j += 1
    elif j == 9:
        if am <= d[x][j - 1]:
            ans += str(j - 1)
            j -= 1
        else:
            ans += str(j)
            am -= d[x][j-1]
    else:
        if am <= d[x][j]:
            ans += str(j)
        else:
            ans += str(j + 1)
            am -= d[x][j]
            j += 1

print(ans)

Submission status: Accepted

Solution code:
import queue

K = int(input())

q = queue.Queue()

q.put(1)
q.put(2)
q.put(3)
q.put(4)
q.put(5)
q.put(6)
q.put(7)
q.put(8)
q.put(9)
x=0
while K>0:
    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)
    K-=1

print(x)

Submission status: Accepted

Solution code:
K = int(input())

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

for i in range(K - 1):
    N = queue.pop(0)
    if i < K // 2.5:
        if N % 10 == 0:
            queue.append(N * 10)
            queue.append(N * 10 + 1)
        elif N % 10 == 9:
            queue.append(N * 10 + 8)
            queue.append(N * 10 + 9)
        else:
            queue.append(N * 10 + (N % 10 - 1))
            queue.append(N * 10 + N % 10)
            queue.append(N * 10 + (N % 10 + 1))

print(queue.pop(0))

Submission status: Accepted

Solution code:
k=int(input())
queue=[i for i in range(1,10)]
if k <10:
    print(k)
else:
    l=0
    while l+9 < k:
        x=queue.pop(0)
        if x%10 != 0:
            queue.append(10*x+x%10-1)
            l+=1
        if l+9==k:
            break
        queue.append(10*x+x%10)
        l+=1
        if l+9==k:
            break
        if x%10 != 9:
            queue.append(10*x+x%10+1)
            l+=1
    print(queue[-1])

Submission status: Accepted

Solution code:
K = int(input())

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

for i in range(K - 1):
    N = queue.pop(0)
    if i < K // 2:
        if N % 10 == 0:
            queue.append(N * 10)
            queue.append(N * 10 + 1)
        elif N % 10 == 9:
            queue.append(N * 10 + 8)
            queue.append(N * 10 + 9)
        else:
            queue.append(N * 10 + (N % 10 - 1))
            queue.append(N * 10 + N % 10)
            queue.append(N * 10 + (N % 10 + 1))

print(queue.pop(0))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
q = deque([[1],[2],[3],[4],[5],[6],[7],[8],[9]])
cnt = 0
while cnt != K:
    nums = q.popleft()
    last = nums[-1]
    if last == 9:
        tmp = nums.copy()
        tmp.append(8)
        q.append(tmp)

        tmp = nums.copy()
        tmp.append(9)
        q.append(tmp)
    elif last == 0:
        tmp = nums.copy()
        tmp.append(0)
        q.append(tmp)

        tmp = nums.copy()
        tmp.append(1)
        q.append(tmp)
    else:
        tmp = nums.copy()
        tmp.append(last-1)
        q.append(tmp)

        tmp = nums.copy()
        tmp.append(last)
        q.append(tmp)

        tmp = nums.copy()
        tmp.append(last+1)
        q.append(tmp)

    cnt += 1
ans = 0
l = len(nums)
for i in range(l):
    ans += nums[i]*10**(l-i-1)
print(ans)

Submission status: Accepted

Solution code:
K=int(input())
A=[1,2,3,4,5,6,7,8,9]+[0]*10*K
i=9
j=0
while i<K:
    if A[j]%10!=0 and A[j]%10!=9:
        A[i]=10*A[j]+A[j]%10-1;i+=1
        A[i]=10*A[j]+A[j]%10;i+=1
        A[i]=10*A[j]+A[j]%10+1;i+=1
    elif A[j]%10==0:
        A[i]=10*A[j]+A[j]%10;i+=1
        A[i]=10*A[j]+A[j]%10+1;i+=1
    else:
        A[i]=10*A[j]+A[j]%10-1;i+=1
        A[i]=10*A[j]+A[j]%10;i+=1
    j+=1
print(A[K-1])

Submission status: Accepted

Solution code:
# 桁DPと思い込んで終了しました
# BFSでいける、というtwを見かけてなるほどとなった
# これは絶対を走査するときわざわざ0から9まで見ているのと、せっかくbfsなのにソートするようにしているので微妙な例だと思われ

from collections import deque
k = int(input())
arr = set()
for i in range(1, 10):
    arr.add(i)

for i in range(1, 10):
    tmp_arr = deque()
    tmp_arr.append(str(i))
    while len(tmp_arr) > 0:
        cur = tmp_arr.popleft()
        arr.add(int(cur))
        if len(cur) == len("3234566667"):
            next
        target = int(cur[-1])
        for i in range(0, 10):
            if abs(target - i) <= 1:
                next_num = cur + str(i)
                if int(next_num) > 3234566667:
                    continue
                tmp_arr.append(next_num)
arr = sorted(arr)
print(arr[k - 1])

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

K = I()
que = deque([1,2,3,4,5,6,7,8,9])
lst = [1,2,3,4,5,6,7,8,9]
cnt = 9
while cnt < K:
    s = que.popleft()
    t = int(str(s)[-1])
    for i in range(max(0,t-1),min(10,t+2)):
        cnt += 1
        lst.append(int(str(s)+str(i)))
        que.append(int(str(s)+str(i)))
print(lst[K-1])

Submission status: Accepted

Solution code:
import queue
k=int(input())
q=queue.Queue()
for i in range(1,10):
  q.put(i)
c=0
while c<k:
  a=q.get()
  c+=1
  if c==k:
    print(a)
  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)

Submission status: Accepted

Solution code:
from collections import deque

K=int(input())

todo=deque(list(map(str,range(1,10))))

count=0

while todo:
    num=todo.popleft()
    count+=1

    if count==K:
        print(num)
        exit()
    
    base=int(num[-1])
    n1=base-1
    if n1!=-1:
        todo.append(num+str(n1))
    
    n2=base
    todo.append(num+str(n2))

    n3=base+1

    if n3!=10:
        todo.append(num+str(n3))

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):
    v = que.popleft()
    if v%10!=0:
        que.append(10*v+v%10-1)
    que.append(10*v+v%10)
    if v%10!=9:
        que.append(10*v+v%10+1)
print(v)

Submission status: Accepted

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

for _ in range(k-1):
    d = q.popleft()

    if d%10 > 0:
        q.append(d*10 + d%10 - 1)

    q.append(d*10 + d%10)
    
    if d%10 < 9:
        q.append(d*10 + d%10 + 1)

print(q.popleft())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def main(argv):
    k = int(sys.stdin.readline().rstrip("\n"))
    if k < 10:
        return print(k)
    d = {i: [i] for i in range(10)}

    counter = 9
    n = 1
    while counter < k:
        next_d = {}
        candidates = d[0]
        candidates.extend(d[1])
        next_d[0] = sorted([c for c in set(candidates)])
        for i in range(1, 10):
            candidates = d[i - 1]
            candidates.extend(d[i])
            candidates.extend(d.get(i + 1, []))
            next_d[i] = sorted([i * (10 ** n) + c for c in set(candidates)])
            n_candidates = len(next_d[i])
            if (counter + n_candidates) >= k:
                print(next_d[i][k - counter - 1])
                counter += n_candidates
                break
            counter += n_candidates
        d = next_d
        n += 1
    return 0


if __name__ == "__main__":
    sys.exit(main(sys.argv))

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
Q = deque(range(1, 10))
for _ in range(k):
  x = Q.popleft()
  y = x % 10
  z = 10*x + y
  if y != 0:
    Q += [z-1]
  Q += [z]
  if y != 9:
    Q += [z+1]
print(x)

Submission status: Accepted

Solution code:
K=int(input())
from collections import deque
def bfs(k):
    queue = deque()
    for i in range(1, 10):
        queue.append(i)
    cnt = 1
    while queue:
        x = queue.popleft()
        if cnt == k:
            return x
        cnt += 1
        last = x%10
        if last > 0:
            queue.append(x*10+last-1)
        queue.append(x*10+last)
        if last < 9:
            queue.append(x*10+last+1)
print(bfs(K))