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

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


dp = [[0]*10 for _ in range(10)]    # i の最大値は　3234566667の10桁よりi = 9
i = 0
flg = False

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

S = 8
while True:
    i += 1
    for k in range(10):
        if k==9:
            dp[i][k] = dp[i-1][k] + dp[i-1][k-1]
        elif k == 0:
            dp[i][k] = dp[i - 1][k + 1] + dp[i - 1][k]
        else:
            dp[i][k] = dp[i - 1][k + 1] + dp[i - 1][k] + dp[i - 1][k - 1]
        if k != 0:
            S += dp[i][k]
        if S >= K-1:
            flg = True
            break
    if flg:
        break
i_max, k_max = i, k
i_max -= 1
res = [k_max]
for i in range(i_max, -1, -1):
    for k in reversed(range(k_max-1,k_max+2)):
        if k > 9 or k < 0:
            continue
        if S - dp[i][k] >= K-1:
            S -= dp[i][k]
        else:
            break
    k_max = k
    res.append(k)

print(*res, sep="")

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

k = INT()
q = Queue()

for i in range(1,10):
    q.put(i)
for i in range(k):
    x = q.get()
    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 )
print(x)

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

k = INT()
s = list('00000000000')

for i in range(k):
    for j in range(len(s)):
        if s[j] != '9' and ( int("".join(s[j+1:])) == 0 or int(s[j]) < int(s[j+1]) + 1 ):
            s[j] = str(int(s[j]) + 1)
        else:
            continue

        while j > 0:
            j -= 1
            s[j] = str(max(0, int(s[j+1])-1))
        break

ans = int("".join(reversed(s)))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
S = []
def add(a):
    if a > 3234566667:
        return
    x = a % 10
    if x != 0:
        S.append(a * 10 + x - 1)
        add(a * 10 + x - 1)
    S.append(a * 10 + x)
    add(a * 10 + x)
    if x != 9:
        S.append(a * 10 + x + 1)
        add(a * 10 + x + 1)
for i in range(9):
    S.append(i+1)
    add(i+1)
S.sort()
print(S[int(input())-1])

Submission status: Accepted

Solution code:
k=int(input())
l=[i for i in range(1,10)]
for i in range(k):
    r=l.pop(0)
    rr=r%10
    if rr!=0:
        l.append(10*r+rr-1)
    l.append(10*r+rr)
    if rr!=9:
        l.append(10*r+rr+1)
print(r)

Submission status: Accepted

Solution code:
import sys
import queue


def solve(k):
    q = queue.Queue()
    for i in range(1, 10):
        q.put(i)
    for i in range(k):
        n = q.get()
        if i == k - 1:
            return n
        if n % 10 == 0:
            q.put(n * 10)
            q.put(n * 10 + 1)
        elif n % 10 == 9:
            q.put(n * 10 + 8)
            q.put(n * 10 + 9)
        else:
            l = n % 10
            q.put(n * 10 + l - 1)
            q.put(n * 10 + l)
            q.put(n * 10 + l + 1)


def main():
    input = sys.stdin.buffer.readline
    k = int(input())
    print(solve(k))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

K = int(input())

L = [1,2,3,4,5,6,7,8,9]
Q = collections.deque(L)
count = 0 

while count < K-1:
    V = Q.popleft()
    count+=1
    if V%10 == 0:
        Q.append(10*V)
        Q.append(10*V+1)
    elif V%10 == 9:
        Q.append(10*V+8)
        Q.append(10*V+9)
    else:
        Q.append(10*V+(V%10)-1)
        Q.append(10*V+(V%10))
        Q.append(10*V+(V%10)+1)

print(Q.popleft())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

Lunlun = []
K = int(input())

def dfs(i,before):
    if i == 10:
        return
    Lunlun.append(before)
    x = before%10
    for d in (-1,0,1):
        y = x + d
        if y < 0 or y >= 10:
            continue
        dfs(i + 1,before*10 + y)

for i in range(1,10):
    dfs(0,i)
Lunlun.sort()
ans = Lunlun[K - 1]
print(ans)

Submission status: Accepted

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

queue = deque([[1],[2],[3],[4],[5],[6],[7],[8],[9]]) # 初期化_ここでは正の一桁整数として'1'～'9'を設置
ptns = [] # パターン候補の器_初期化

while queue: # queueが空になるまでループ
    tmp = queue.popleft() # パターンの候補を popleft
    if len(ptns) < n: # ptnsの要素数が'n'個未満ならば append
        ptns.append(tmp)
    else:
        break
 # 以下、tmpに各々tmp[-1]-1、tmp[-1]、tmp[-1]+1をappendするための条件
    if tmp[-1] != 0:
        queue.append(tmp + [tmp[-1] -1])

    queue.append(tmp + [tmp[-1]])

    if tmp[-1] != 9:
        queue.append(tmp + [tmp[-1] +1])

# リスト = map(str, リスト) ← intのリストからstrのmapオブジェクトへ変換
print(''.join(map(str, ptns[-1])))

Submission status: Accepted

Solution code:
def main():
    k = int(input())
    hp = [i for i in range(k+4)]
    r, w = 1, 10
    while w <= k:
        n = hp[r]
        r += 1
        nm = n % 10
        val = n * 10 + nm
        
        if nm != 0:
            hp[w] = val - 1
            w += 1
        hp[w] = val
        w += 1
        if nm != 9:
            hp[w] = val + 1
            w += 1

    print(hp[k])

main()

Submission status: Accepted

Solution code:
def main():
    k = int(input())
    hp = list(range(1, 10))
    for i in range(k-1):
        n = hp.pop(0)
        nm = n % 10
        val = n * 10 + nm
        
        if nm != 0:
            hp.append(val - 1)
        hp.append(val)
        if nm != 9:
            hp.append(val + 1)
    print(hp[0])

main()

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
q = deque()
for i in range(1, 10):
    q.append(i)
i = 0
run = []
while i < K:
    i += 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)
    run.append(x)

print(run[K - 1])

Submission status: Accepted

Solution code:
def incr_lunlun(num):
    num[0] += 1
    if len(num) == 1:
        if num[0] == 10:
            num.append(1)
            num[0] = 0
    
    elif num[0] > num[1] + 1 or num[0] == 10:
        suffix = incr_lunlun(num[1:])
        digit = max(0, suffix[0] - 1)
        num = [digit] + list(suffix)

    return num


def main():
    k = int(input())
    num = [1]
    for i in range(k-1): 
        num = incr_lunlun(num)

    print(int(''.join(str(i) for i in reversed(num))))



main()

Submission status: Accepted

Solution code:
import queue

k=int(input())

q = queue.Queue()


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


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

print(a)

Submission status: Accepted

Solution code:
K = int(input())
numbers = set([])
q = set([1, 2, 3, 4, 5, 6, 7, 8, 9])
# print(f'{q=}')

while len(numbers) <= 100000:  # 10**8:
    # print('test')
    qq = set([])
    for i in q:
        # print(f'{i=}')
        if i % 10 != 0:
            n = i * 10 + (i % 10) - 1
            qq.add(n)
        if i % 10 != 9:
            n = i * 10 + (i % 10) + 1
            qq.add(n)
        n = i * 10 + (i % 10)
        qq.add(n)
    numbers |= q
    # print(f'{numbers=}')
    # print(f'{len(numbers)=}')
    q = qq

numbers = sorted(map(int, numbers))
# print(f'{numbers[:30]=}')
ans = numbers[K - 1]
print(ans)

Submission status: Accepted

Solution code:
K = int(input())
numbers = set([])
q = set(list(map(str, [1, 2, 3, 4, 5, 6, 7, 8, 9])))
# print(f'{q=}')

while len(numbers) <= 100000:  # 10**8:
    # print('test')
    qq = set([])
    for i in q:
        # print(f'{i=}')
        if len(i) == 1:
            if i == '0':
                n = i + '0'
                qq.add(n)
                n = i + '1'
                qq.add(n)
            elif i == '9':
                n = i + '9'
                qq.add(n)
                n = i + '8'
                qq.add(n)
            else:
                v = int(i)
                n = i + str(v - 1)
                qq.add(n)
                n = i + str(v)
                qq.add(n)
                n = i + str(v + 1)
                qq.add(n)
        else:
            if i[-1] == '0':
                n = i + '0'
                qq.add(n)
                n = i + '1'
                qq.add(n)
            elif i[-1] == '9':
                n = i + '9'
                qq.add(n)
                n = i + '8'
                qq.add(n)
            else:
                v = int(i[-1])
                n = i + str(v - 1)
                qq.add(n)
                n = i + str(v)
                qq.add(n)
                n = i + str(v + 1)
                qq.add(n)
    # print(f'{qq=}')
    numbers |= q
    # print(f'{numbers=}')
    # print(f'{len(numbers)=}')
    q = qq

numbers = sorted(map(int, numbers))
# print(f'{numbers[:30]=}')
ans = numbers[K - 1]
print(ans)

Submission status: Accepted

Solution code:
def resolve():
	from collections import deque
	K = int(input())
	q = deque(str(i) for i in range(1, 10))
	cnt = 9
	if K < 10:
		print(K); return
	while True:
		tmp = q.popleft()
		las = int(tmp[-1])
		for i in range(las-1, las+2):
			if 0<=i<=9:
				q.append(tmp + str(i))
				cnt += 1
				if cnt==K:
					print(q.pop()); return
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K = int(input())

C = [[0]*10 for _ in range(10)]
C[0] = [1]*10
D = {0: [0, 1], 1: [0, 1, 2], 2: [1, 2, 3], 3: [2, 3, 4], 4: [3, 4, 5], 5: [4, 5, 6], 6: [5, 6, 7], 7: [6, 7, 8], 8: [7, 8, 9], 9: [8, 9]}

for i in range(1, 10):
  for j in range(10):
    if j == 0:
      C[i][j] = C[i-1][j] + C[i-1][j+1]
    elif j == 9:
      C[i][j] = C[i-1][j-1] + C[i-1][j]
    else:
      C[i][j] = C[i-1][j-1] + C[i-1][j] + C[i-1][j+1]

ans = []
temp = K
Flag = True

for i in range(10):
  if Flag:
    for j in range(1, 10):
      temp -= C[i][j]
      if temp <= 0:
        temp += C[i][j]
        r = i
        ans.append(j)
        Flag = False
        break
  else:
    break

def f(x, r):
  temp = x
  r -= 1
  for j in D[ans[-1]]:
    temp -= C[r][j]
    if temp <= 0:
      temp += C[r][j]
      ans.append(j)
      break
  return temp, r

while r >= 1:
  temp, r = f(temp, r)

print("".join([str(i) for i in ans]))

Submission status: Accepted

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    k = int(input())
    from collections import deque
    que = deque(range(1, 10))
    for i in range(k):
        now = que.popleft()
        r = now%10
        nx = now*10
        if r == 0:
            for j in [0, 1]:
                que.append(nx+r+j)
        elif r == 9:
            for j in [-1, 0]:
                que.append(nx+r+j)
        else:
            for j in [-1, 0, 1]:
                que.append(nx+r+j)
    print(now)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
ans=[]
# q = deque([[1],[2],[3],[4],[5],[6],[7],[8],[9]])
q = deque([1,2,3,4,5,6,7,8,9])
while q:
  a = q.popleft()
  ans.append(a)
  if len(ans) > k:
    break
  tmp = int(str(a)[-1])
  if tmp-1 >= 0:
    q.append(10*a + tmp-1)
  q.append(10*a + tmp)
  if tmp+1 <= 9:
    q.append(10*a + tmp+1)
print(ans[k-1])

Submission status: Accepted

Solution code:
k = int(input())

i = 0

ans = []

def rec(n):
    ans.append(n)
    if n >= 10000000000:
        return
    for j in range(-1, 2, 1):
        add = n % 10 + j
        if 0 <= add <= 9:
            rec(10 * n + add)
for i in range(1, 10):
    rec(i)
ans.sort()
print(ans[k - 1])

Submission status: Accepted

Solution code:
def nextLunlun(l):
  l[-1]+=1
  for i in range(len(l)-1):
    if abs(l[-i-1]-l[-i-2])>=2 or l[-i-1]==10:
      l[-i-2]+=1
      l[-i-1]=0

  if l[0]>=10:
    l.insert(0,1)
    l[1]=0
    
  for i in range(len(l)-1):
    if abs(l[i]-l[i+1])>=2:
      l[i+1]=max(0,l[i]-1)
  
  return l

l=[0]
n=int(input())

for i in range(n):
  nextLunlun(l)
for num in l:
  print(num,end='')
print()

Submission status: Accepted

Solution code:
k=int(input())

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

while True:
  if len(que)>=k:
    break
  k-=len(que)
  for q in que[:]:
    que.remove(q)
    lq=int(str(q)[-1])
    for r in (lq-1,lq,lq+1):
        if 0<=r<=9:
            que.append(int(str(q)+str(r)))
 
  if len(que)>=k:
    break
 
que.sort()
print(que[k-1])

Submission status: Accepted

Solution code:
K=int(input())
import queue
q = queue.Queue()
for i in range(1,10):
  q.put(i)
for i in range(K-1):
  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(q.get())

Submission status: Accepted

Solution code:
k = int(input())

digit_len = 1

def df(num, depth):
    if len(str(num)) == depth:
        return [num]

    df_result = []
    tmp_num = int(str(num)[-1])
    tmp = [tmp_num]
    if tmp_num-1>=0:
        tmp.append(tmp_num-1)
    if tmp_num+1<10:
        tmp.append(tmp_num+1)
    for i in tmp:
        df_result.extend(df(int(str(num)+str(i)), depth))
    return df_result

num_list = []
while 1:
    tmp = []
    for i in range(1,10):
        tmp.extend(df(i, digit_len))
    num_list.extend(sorted(tmp))
    if len(num_list)>=k:
        break
    digit_len+=1

print(num_list[k-1])

Submission status: Accepted

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

k, q = int(input()), deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
for i in range(1, 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(q.popleft())

Submission status: Accepted

Solution code:
k=int(input())

if k<=9:
    print(k)
    exit(0)

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

i=0
while len(ans)<k:
    v=ans[i]

    mod=v%10

    if mod==0:
        ans.append(10*v+mod)
        ans.append(10*v+mod+1)
    elif mod==9:
        ans.append(10*v+mod-1)
        ans.append(10*v+mod)
    else:
        ans.append(10*v+mod-1)
        ans.append(10*v+mod)
        ans.append(10*v+mod+1)

    i+=1

print(ans[k-1])

Submission status: Accepted

Solution code:
k=int(input())

if k<=9:
    print(k)
    exit(0)

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

i=0
while len(ans)<k:
    v=str(ans[i])
    n=len(v)
    #最後の桁
    v_last=int(v[-1])

    if v_last==0:
        ans.append(int(v+'0'))
        ans.append(int(v+'1'))
    elif v_last==9:
        ans.append(int(v+'8'))
        ans.append(int(v+'9'))
    else:
        ans.append(int(v+str(v_last-1)))
        ans.append(int(v+str(v_last)))
        ans.append(int(v+str(v_last+1)))
    i+=1

print(ans[k-1])

Submission status: Accepted

Solution code:
k=int(input())
cnt=0
queue=['1','2','3','4','5','6','7','8','9']
while len(queue)>0:
  if cnt==k:
    print(queue[-1][:-1])
    exit()
  now=queue.pop(0)
  if now[-1]=='9':
    queue.append(now+'8')
    queue.append(now+'9')
  elif now[-1]=='0':
    queue.append(now+'0')
    queue.append(now+'1')
  else:
    queue.append(now+str(int(now[-1])-1))
    queue.append(now+str(int(now[-1])))
    queue.append(now+str(int(now[-1])+1))
  cnt+=1

Submission status: Accepted

Solution code:
def make(i):
    if int(i) > 3234566667:  return
    lun.append(int(i))
    if int(i[-1]) - 1 >= 0:  make(i + str(int(i[-1]) - 1))
    make(i + i[-1])
    if int(i[-1]) + 1 <= 9:  make(i + str(int(i[-1]) + 1))

lun = []
for i in range(1, 10):  make(str(i))
lun = sorted(lun)
print(lun[int(input()) - 1])

Submission status: Accepted

Solution code:
K = int(input())

def make(i):
    if int(i) > 3234566667:  return
    lun.append(int(i))
    if i[-1] == "0":
        temp = i + "0"
        make(temp)
        temp = i + "1"
        make(temp)
    elif i[-1] == "9":
        temp = i + "8"
        make(temp)
        temp = i + "9"
        make(temp) 
    else:
        temp = i + str(int(i[-1]) - 1)
        make(temp)
        temp = i + i[-1]
        make(temp)   
        temp = i + str(int(i[-1]) + 1)
        make(temp)
        
lun = []
for i in range(1, 10):
    make(str(i))
lun = sorted(lun)
ans = lun[K - 1]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K = int(input())
# 10桁までやれば十分
runrun_table = [[0 for _ in range(10)] for _ in range(10)]
# i桁のルンルン数の種類 <= 3**(i-1)*9
for i in range(10):
    runrun_table[0][i] = 1
for keta in range(1, 10):
    for i in range(10):
        if i == 0:
            runrun_table[keta][i] = runrun_table[keta - 1][i] + \
                                    runrun_table[keta - 1][i + 1]
        elif i == 9:
            runrun_table[keta][i] = runrun_table[keta - 1][i - 1] + \
                                    runrun_table[keta - 1][i]
        else:
            runrun_table[keta][i] = runrun_table[keta - 1][i - 1] + \
                                    runrun_table[keta - 1][i] + \
                                    runrun_table[keta - 1][i + 1]

keta = 0
ans = ''
while sum(runrun_table[keta][1:]) < K:
    K -= sum(runrun_table[keta][1:])
    keta += 1

for piv in range(1, 10):
    if runrun_table[keta][piv] >= K:
        ans += str(piv)
        keta -= 1
        break
    K -= runrun_table[keta][piv]

while keta >= 0:
    if piv == 0:
        piv_range = [0, 1]
    elif piv == 9:
        piv_range = [8, 9]
    else:
        piv_range = range(piv-1, piv+2)
    for piv in piv_range:
        if runrun_table[keta][piv] >= K:
            ans += str(piv)
            keta -= 1
            break
        K -= runrun_table[keta][piv]

print(ans)

Submission status: Accepted

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

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

def next_n(n):
    if n == 0:
        return [0, 1]
    elif n == 9:
        return [8, 9]
    else:
        return [n-1, n, n+1]

for _ in range(K-1):
    now = q.popleft()
    for next_ in next_n(now%10):
        q.append(now*10 + next_)

print(q[0])

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

def next_num(n):
    if n == 0:
        return [0, 1]
    elif n == 9:
        return [8, 9]
    else:
        return [n-1, n, n+1]

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

for _ in range(K-1):
    now = heappop(queue)
    for next_i in next_num(now%10):
        heappush(queue, now*10 + next_i)

print(queue[0])

Submission status: Accepted

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

k=int(input())

def dfs(keta,num):
  lunlun.append(int(num))
  if keta==10:
    return

  min_v=max(0,int(num[-1])-1)
  max_v=min(9,int(num[-1])+1)

  for i in range(min_v,max_v+1):
    dfs(keta+1,num+str(i))

lunlun=[]
for i in range(1,10):
  dfs(0,str(i))

lunlun.sort()
print(lunlun[k-1])

Submission status: Accepted

Solution code:
k = int(input())
L = []

def lunlun(d,v,L):
    L.append(v)
    if d == 10:
        return
    for i in range(-1,2):
        t = v%10 + i
        #print(v)
        if 0 <= t <=9:
            lunlun(d+1,v*10+t,L)
#lunlun(1,1,L)
for v in range(1,10):
    lunlun(1,v,L)
print(sorted(L)[k-1])

Submission status: Accepted

Solution code:
K = int(input())
L = [i for i in range(1, 10)]
cnt = 9
i = 0

while K > cnt:
  x = L[i]
  r = x % 10
  if r != 0:
    L.append(10*x + r - 1)
    cnt += 1
  L.append(10*x + r)
  cnt += 1
  if r != 9:
    L.append(10*x + r + 1)
    cnt += 1
  i += 1

print(L[K-1])

Submission status: Accepted

Solution code:
from itertools import chain

l = [[] for _ in range(11)]
l[0] = list(map(str, range(1, 10)))
for i in range(10):
    for x in l[i]:
        last = int(x[-1])
        for m in {max(0, last-1), last, min(9 ,last+1)}:
            m = str(m)
            l[i+1].append(x+m)

q = list(map(int, chain(*l)))
q.sort()
# print(len(q))
K = int(input())

print(q[K-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

ans = []

queue = deque(range(1, 10))

while len(ans) < K:
    n = queue.popleft()
    ans.append(n)
    n_str = str(n)
    p = int(n_str[-1])
    if p - 1 >= 0:
        queue.append(int(n_str+str(p-1)))
    queue.append(int(n_str+str(p)))
    if p + 1 <= 9:
        queue.append(int(n_str+str(p+1)))

print(ans[-1])

Submission status: Accepted

Solution code:
from collections import deque
import sys
K = int(input())
q = deque([1,2,3,4,5,6,7,8,9])
num = 0
if K<=9:
    print(q[K-1])
    sys.exit()
for i in range(10**5):
    p = q.popleft()
    num += 1
    if num == K:
        print(p)
    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)

Submission status: Accepted

Solution code:
import sys
from collections import deque
K = int(input())
q = deque([])
for i in range(1, 10):
    q.append(str(i))
ans = 0
while ans != K:
    l = q.popleft()
    ans += 1
    if ans == K:
        print(l)
        sys.exit()
    if l[-1] == '0':
        q.append(l + '0')
        q.append(l + '1')
    elif l[-1] == '9':
        q.append(l + '8')
        q.append(l + '9')
    else:
        q.append(l + str(int(l[-1]) - 1))
        q.append(l + str(int(l[-1])))
        q.append(l + str(int(l[-1]) + 1))

Submission status: Accepted

Solution code:
k=int(input())

q=["1","2","3","4","5","6","7","8","9"]
x=9
for i in q:
    if x>100000:
        break
    x+=1
    a=i[-1]
    for j in ([-1,0,1]):
        bb=int(a)+j
        if bb<10 and bb>=0:
            q.append(i+str(bb))


print(q[k-1])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, 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, insort, insort_left
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(str, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
from decimal import *
 
K = INT()

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

for i in range(K):
    n = q.popleft()
    r = n%10

    if r != 0:
        q.append(10*n + r-1)

    q.append(10*n + r)

    if r != 9:
        q.append(10*n + r+1)

print(n)

Submission status: Accepted

Solution code:
#create date: 2020-06-29 13:35

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    k = ni()
    q = deque(map(str, range(1, 10)))
    for i in range(k):
        n = q.popleft()
        last_n = n[-1]
        for diff in range(-1, 2):
            next_n = int(last_n) + diff
            if next_n >= 0 and next_n <= 9:
                q.append(n+str(next_n))
    print(n)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, 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, insort, insort_left
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(str, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
from decimal import *
 
K = INT()


n = [-1]*11
cnt = 0

def DFS(n):
    global cnt
    for i in range(1, 11):
        if n[-i] == 9:
            continue
        elif n[-i-1] != -1 and n[-i] == n[-i-1]+1:
            continue
        else:
            if n[-i] == -1:
                n[-i] = 1
            else:
                n[-i] += 1

            for j in range(i-1, 0, -1):
                n[-j] = max(0, n[-j-1] - 1)
            break
    cnt += 1
    if cnt == K:
        print(*n[bisect(n, -1):], sep = "")
        exit()
    DFS(n)


DFS(n)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, 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, insort, insort_left
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(str, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
from decimal import *
 
K = INT()

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

n = [-1]*11
n[-1] = 9
cnt = 9


def DFS(n):
    global cnt
    for i in range(1, 11):
        if n[-i] == 9:
            continue
        elif n[-i-1] != -1 and n[-i] == n[-i-1]+1:
            continue
        else:
            if n[-i] == -1:
                n[-i] = 1
            else:
                n[-i] += 1

            for j in range(i-1, 0, -1):
                n[-j] = max(0, n[-j-1] - 1)
            break
    cnt += 1
    if cnt == K:
        print(*n[bisect(n, -1):], sep = "")
        exit()
    DFS(n)


DFS(n)

Submission status: Accepted

Solution code:
def f(k):
    import itertools

    N = [[str(i) for i in range(10)]]
    n = 0
    while n < k:
        T = []
        U = [n[0] for n in N[-1]]
        anchor = 0
        for i in range(len(U) - 1):
            if U[i] != U[i + 1]:
                T.append((anchor, i + 1))
                anchor = i + 1
        else:
            T.append((anchor, len(U)))
        M = []
        for i in range(10):
            for d in (-1, 0, 1):
                if 0 <= i + d < len(T):
                    for j in range(*T[i + d]):
                        M.append("{}{}".format(i, N[-1][j]))
        N[-1] = [n for n in N[-1] if not n.startswith("0")]
        n += len(N[-1])
        N.append(M)
    N = list(itertools.chain.from_iterable(N))
    return N[k - 1]


K = int(input())
print(f(K))

Submission status: Accepted

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

print(l[K-1])

Submission status: Accepted

Solution code:
def dfs(lls, curr_num, lim):
    if curr_num > lim: return
    lls.append(curr_num)
    last_num = int(str(curr_num)[-1])
    if last_num > 0:
        dfs(lls, curr_num*10+last_num-1, lim)
    if last_num < 9:
        dfs(lls, curr_num*10+last_num+1, lim)
    dfs(lls, curr_num*10+last_num, lim)


def main():
    k = int(input())
    lls = []
    for i in range(1,10):
        dfs(lls, i, 3234566668)

    lls.sort()
    print(lls[k-1])
    


if __name__ == "__main__":
    main()