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:
# 20/05/10 cost:20min

def is_valid(num):
    if 1 <= num < 10:
        return True
    ns = map(int, str(num))
    n = len(ns)
    for i in xrange(n - 1):
        if abs(ns[i] - ns[i + 1]) > 1:
            return False
    return True

lunluns = []
for i in xrange(1, 10):
    if is_valid(i):
        lunluns.append(i)

d = {}

def dfs2(rem, pre, lt):
    if rem == 0:
        return 1
    key = (rem, pre, lt)
    if key in d:
        return d[key]

    res = 0
    if lt:
        for i in xrange(10):
            res += dfs2(rem - 1, i, lt and i == 0)
    else:
        for i in xrange(10):
            if abs(i - pre) <= 1:
                res += dfs2(rem - 1, i, False)
    d[key] = res
    return res

assert dfs2(1, -1, True) == 10
assert dfs2(1, 1, False) == 3

def dfs(cur, n, k, pre, lt, buf):
    if cur == n:
        return k == 1

    for i in xrange(10):
        if lt or abs(i - pre) <= 1:
            u = dfs2(n - cur - 1, i, lt and i == 0)
            if u < k:
                k -= u
            else:
                buf.append(i)
                assert dfs(cur + 1, n, k, i, lt and i == 0, buf)
                break
    return True

def solve(k):
    N = 500
    res = []
    assert dfs(0, N, k, -1, True, res)
    res = res[::-1]
    while res and res[-1] == 0:
        res.pop()
    if not res:
        res = [0]
    return ''.join(map(str, res[::-1]))

assert solve(3) == '2'
assert solve(1) == '0'
assert solve(2) == '1'
assert solve(4) == '3'

for i, num in enumerate(lunluns):
    assert solve(i + 2) == str(num)

if __name__ == '__main__':
    k = int(raw_input())
    k += 1
    print solve(k)

Submission status: Accepted

Solution code:
def is_valid(num):
    if 1 <= num < 10:
        return True
    ns = map(int, str(num))
    n = len(ns)
    for i in xrange(n - 1):
        if abs(ns[i] - ns[i + 1]) > 1:
            return False
    return True

lunluns = []
for i in xrange(1, 100000):
    if is_valid(i):
        lunluns.append(i)

d = {}

def dfs2(rem, pre):
    if rem == 0:
        return 1
    key = (rem, pre)
    if key in d:
        return d[key]

    res = 0
    if pre == -1:
        for i in xrange(10):
            res += dfs2(rem - 1, -1 if i == 0 else i)
    else:
        for i in xrange(10):
            if abs(i - pre) <= 1:
                res += dfs2(rem - 1, i)
    d[key] = res
    return res

assert dfs2(1, -1) == 10
assert dfs2(1, 1) == 3

def dfs(cur, n, k, pre, buf):
    if cur == n:
        return k == 1

    for i in xrange(10):
        if pre == -1 or abs(i - pre) <= 1:
            u = dfs2(n - cur - 1, -1 if pre == -1 and i == 0 else i)
            if u < k:
                k -= u
            else:
                buf.append(i)
                assert dfs(cur + 1, n, k, -1 if pre == -1 and i == 0 else i, buf)
                break
    return True

def solve(k):
    N = 500
    res = []
    assert dfs(0, N, k, -1, res)
    res = res[::-1]
    while res and res[-1] == 0:
        res.pop()
    if not res:
        res = [0]
    return ''.join(map(str, res[::-1]))

assert solve(3) == '2'
assert solve(1) == '0'
assert solve(2) == '1'
assert solve(4) == '3'

for i, num in enumerate(lunluns):
    assert solve(i + 2) == str(num)

if __name__ == '__main__':
    k = int(raw_input())
    k += 1
    print solve(k)

Submission status: Accepted

Solution code:
k = int(input())
r = [[i] for i in range(1,10)]

from collections import deque
que = deque(r)

if k < 10:
    print(k)
    exit()
while len(r) <= k:
    ri = que.popleft()
    for j in range(max(0, ri[-1]-1), min(9, ri[-1]+1)+1):
        rj = ri.copy()
        rj.append(j)
        r.append(rj)
        que.append(rj)
        #print(que)
#print(r[k-1])
print(''.join(map(str, r[k-1])))

Submission status: Accepted

Solution code:
k = int(input())

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

c = 0
while k>len(l):
    f = str(l[c])

    if int(f[-1])!=0:
        l.append(int(f)*10 + int(f[-1])-1)

    l.append(int(f)*10 + int(f[-1]))

    if int(f[-1])!=9:
        l.append(int(f)*10 + int(f[-1])+1)

    c += 1

print(l[k-1])

Submission status: Accepted

Solution code:
from queue import Queue

def main():
	K = int(input())
	count = 0
	ans = 0

	q = Queue()
	q.put(-1)


	while(not q.empty()):
		next_loop = True
		v = q.get()

		if(v == -1):
			for i in range(1, 10):
				q.put(i)
				count += 1

				if(count == K):
					ans = i
					next_loop = False
				
		else:
		
			for i in range(0, 10):
				d1 = v%10
				
				if(not (d1-1 <= i <= d1+1)):
					continue

				count += 1

				if(count == K):
					ans = v * 10 + i
					next_loop = False
					break

				q.put(v * 10 + i)
		
		if(not next_loop):
			break

	print(ans)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
K = 0
def recursive(d:int,value:int,lis:list):
    lis.append(value)
    if(d == 10):return
    for j in range(-1,2,1):
        add = value % 10 + j
        if(add >= 0 and add <= 9):
            recursive(d + 1,value * 10 + add,lis)
    

def main():
    global K
    K = int(input())
    lis = []
    for v in range(1,10):
        recursive(1,v,lis)
    lis.sort()
    print(lis[K - 1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K = int(input())

def calc_next(ar):
  res = []
  for val in ar:
    for j in range(-1, 2):
      add = (val % 10) + j
      if add >= 0 and add <= 9:
        res.append(val*10+add)
  return res

cur = []
all_ = []
# 1桁の場合
for v in range(1, 10):
  cur.append(v)
  all_.append(v)
  
# 10桁まで
for d in range(1, 10):
  # 次の桁を列挙
  cur = calc_next(cur)
  
  # allに格納
  for val in cur:
    all_.append(val)

#K番目
print(all_[K-1])

Submission status: Accepted

Solution code:
# inputを高速化する。
import sys
input = sys.stdin.readline

k = int(input())

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

def generator_lunlun(n):
    final = n % 10
    if final > 0:
        yield n * 10 + final - 1
    yield n * 10 + final
    if final < 9:
        yield n * 10 + final + 1
        
     
p = 0
while len(lunlun) < k:
    for result in generator_lunlun(lunlun[p]):
        lunlun.append(result)
    p += 1

print(lunlun[k-1])

Submission status: Accepted

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

q = deque([i for i in range(1,10)])
for i in range(1,k+1):
  x = q.popleft()
  if i == k:
    print(x)
    exit()
  
  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)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

def DFS(N, string, val, L):
	L.append(int(string))
	if N == 11:
		return
	else:
		if val == 0:
			DFS(N + 1, string + "0", 0, L)
			DFS(N + 1, string + "1", 1, L)
		elif val == 9:
			DFS(N + 1, string + "9", 9, L)
			DFS(N + 1, string + "8", 8, L)
		else:
			DFS(N + 1, string + str(val + 1), val + 1, L)
			DFS(N + 1, string + str(val), val, L)
			DFS(N + 1, string + str(val - 1), val - 1, L)

#処理内容
def main():
	K = int(input())
	L = []
	for i in range(10):
		DFS(0, str(i), i, L)

	L = sorted(list(set(L)))

	print(L[K])


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
num = deque()
for i in range(1,10):
    num.append(i)
while True:
    l = len(num)
    if l >= k:
        print(num[k-1])
        exit()
    else:
        k -= l
        for i in range(l):
            left = num.popleft()
            last = left%10
            add1,add2,add3 = 10*left+last-1,10*left+last,10*left+last+1
            if 0 < last < 9:
                num.append(add1)
                num.append(add2)
                num.append(add3)
            elif last == 0:
                num.append(add2)
                num.append(add3)
            else:
                num.append(add1)
                num.append(add2)

Submission status: Accepted

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

Sum = 0      
for i in range(10):
  Sum += len(List[i])
  if K<=Sum:
    print(List[i][K-(Sum-len(List[i]))-1])
    break

Submission status: Accepted

Solution code:
k=int(input())

from queue import Queue
q=Queue()

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

cnt=0

while 1:
  cnt+=1
  x=q.get()
  if cnt==k:
    print(x)
    exit()
  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)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限

K = int(input())

l = [1,2,3,4,5,6,7,8,9] #１桁のルンルン数
ln = [1,2,3,4,5,6,7,8,9] #既にわかっている分をセット。重複がいやなのでset

def dfs(i):
    n = int(str(i)[-1]) #1桁目を取る
    a,b,c = n-1, n, n+1 #差の絶対値が１未満、-1/+0/+1
    if a != -1:
        ln.append(i*10+a)
    ln.append(i*10+b)
    if c != 10:
        ln.append(i*10+c)
    
    if len(str(i)) <= 10:
        if a != -1:
            dfs(i*10 + a)
        dfs(i*10 + b)
        
        if c != 10:
            dfs(i*10 + c)

for i in l: #１桁のルンルン数を順番に再帰
    dfs(i)

print(sorted(ln)[K-1]) #0-indexを意識してリストのK-1番目を出す

Submission status: Accepted

Solution code:
K=int(input())

def dfs(d,val,all):
    all.append(val)
    if d==10:
        return
    add=0
    for i in range(-1,2):
        add=(val%10)+i
        if 0<=add<=9:
            dfs(d+1,val*10+add,all)
all=[]
for i in range(1,10):
    dfs(0,i,all)
print(sorted(all)[K-1])

Submission status: Accepted

Solution code:
K=int(input())
A=[1,2,3,4,5,6,7,8,9]
B=[]
C=[]
D=[]
E=[]
F=[]
G=[]
H=[]
I=[]
J=[]
def henkan(A):
    a=len(A)
    B=[]
    for i in range(a):
        if A[i]%10==0:
            B.append(10*A[i])
            B.append(10*A[i]+1)
        elif A[i]%10==9:
            B.append(10*A[i]+9)
            B.append(10*A[i]+8)
        else:
            x=A[i]%10
            B.append(10*A[i]+x)
            B.append(10*A[i]+x+1)
            B.append(10*A[i]+x-1)
    return B

B=henkan(A)
C=henkan(B)
D=henkan(C)
E=henkan(D)
F=henkan(E)
G=henkan(F)
H=henkan(G)
I=henkan(H)
J=henkan(I)
ans=A+B+C+D+E+F+G+H+I+J
ans=sorted(ans)

print(ans[K-1])

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
if K<10:
  print(K)
  exit()
  
q = deque([1,2,3,4,5,6,7,8,9])

cnt = 9
while q:
  n = q.popleft()
  r = n % 10
  n *= 10;
  for i in range(10):
    if abs(r - i) <= 1:
        q.append(n + i)
        cnt += 1
        if cnt == K:
          print(n+i)
          exit()

Submission status: Accepted

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

cnt = 0
while q:
  n = q.popleft()
  r = n % 10; n *= 10;
  for i in range(10):
    if abs(r - i) <= 1 or n == 0:
      if n + i != 0:
        q.append(n + i)
        cnt += 1
        if cnt == K:
          print(n+i)
          exit()

Submission status: Accepted

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

cnt = 0
ans = []
while q:
  a = q.popleft()
  r = a % 10
  a *= 10
  for i in range(10):
    if abs(r - i) <= 1 or a == 0:
      if cnt < K and a + i != 0:
        q.append(a + i)
        ans.append(a + i)
        cnt += 1

print(ans[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import queue

K = int(input())

q = queue.Queue()
ans = []
cnt = 0
for i in range(1,10):
    q.put(i)
    ans.append(i)
    cnt += 1

while cnt <= 10**5:
    n = q.get()
    m = n %10
    if m == 0:
        q.put(n*10+0)
        q.put(n*10+1)
        ans.append(n*10)
        ans.append(n*10+1)
        cnt += 1
    elif m == 9:
        q.put(n*10+8)
        q.put(n*10+9)
        ans.append(n*10+8)
        ans.append(n*10+9)
        cnt += 2
    else:
        q.put(n*10+m-1)
        q.put(n*10+m)
        q.put(n*10+m+1)
        ans.append(n*10+m-1)
        ans.append(n*10+m)
        ans.append(n*10+m+1)
        cnt += 3

print(ans[K-1])

Submission status: Accepted

Solution code:

def makeLunLun(num):
  lunlunNums = []
  m = num % 10 -1
  z = m + 1
  p = m + 2
  if m >= 0:
    lunlunNums.append(num * 10 + m)
  lunlunNums.append(num * 10 + z)
  if p <= 9:
    lunlunNums.append(num * 10 + p)
  return lunlunNums

K=int(input())

queue = [1,2,3,4,5,6,7,8,9]
i=0
while K > len(queue):
  lunluns = makeLunLun(queue[i])
  queue += lunluns
  i += 1
print(queue[K-1])

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
ans = 0
cnt = 9
start = 0
X = deque([[[9],[8],[7],[6],[5],[4],[3],[2],[1]]])
if K <= 9:
  print(K)
  exit()
for _ in range(10000):
    X.append(deque([]))
for i in range(1,10000):
    now_cnt = cnt
    for x in list(X[i-1]):
        for j in range(10,0,-1):
            if abs(x[len(x)-1]-j+1) <= 1:
                X[i].append(x+[j-1])
                cnt += 1
    if cnt >= K:
        X[i].reverse()
        lun = X[i][K-now_cnt-1]
        
        N = []
        
        for n in lun:
          N.append(str(n))
        
        print(''.join(N))
        exit()

Submission status: Accepted

Solution code:
k=int(input())
#n,k=map(int,input().split())
#pl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
from collections import deque
q=[i for i in range(1,10)]
q=deque(q)

for i in range(k):
    val=q.popleft()
    mod=val%10
    for add in range(max(mod-1,0),min(mod+1,9)+1):
        q.append(val*10+add)
print(val)

Submission status: Accepted

Solution code:

def p_num():
    global num
    ans = 0
    for i in range(12):
        ans += num[i] * (10 ** i)
    print(ans)


def fun(i, f):
    global k, num, n
    p = num[i + 1]
    for j in range(max(0, p - 1), ((f == 1) * 10) + ((f != 1) * min(10, p + 2))):
        num[i] = j
        if (i == 0):
            # p_num()
            n += 1
            if (k == n):
                p_num()
                exit()
        else:
            fun(i - 1, f and j == 0)


k = int(input())
num = [0] * 15
n = -1

fun(11, 1)

Submission status: Accepted

Solution code:

def calc_next(arr):
	res = []
	for val in arr:
		for j in range(-1, 2):
			add = (val % 10) + j
			if add >= 0 and add <= 9:
				res.append(val * 10 + add)
	return res

k = int(input())
cur = []
A = []

for v in range(1, 10):
	cur.append(v)
	A.append(v)

for d in range(1, 10):
	cur = calc_next(cur)
	for val in cur:
		A.append(val)

print(A[k - 1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k = int(input())

def dfs(d, val, A):
	A.append(val)

	if d == 10:
		return

	for i in range(-1, 2):
		add = (val % 10) + i
		if add >= 0 and add <= 9:
			dfs(d + 1, val * 10 + add, A)

A = []
for v in range(1, 10): # 呼び出し
	dfs(1, v, A)
A.sort()
print(A[k - 1])

Submission status: Accepted

Solution code:
x = int(input())

runrun=[[1,2,3,4,5,6,7,8,9],[]]
count=9
keta=2
end=False
ans=-1

if x<=9:
    ans=x
    end=True

while True:
    if end:
        break

    for ini in runrun[keta-2]:

        if ini%10==0:
            runrun[keta-1].append(ini*10)
            count+=1
            if count==x:
                end=True
                ans=ini*10
                break
            runrun[keta-1].append(ini*10+1)
            count+=1
            if count==x:
                end=True
                ans=ini*10+1
                break

        elif ini%10==9:
            runrun[keta-1].append(ini*10+8)
            count+=1
            if count==x:
                end=True
                ans=ini*10+8
                break
            runrun[keta-1].append(ini*10+9)
            count+=1
            if count==x:
                end=True
                ans=ini*10+9
                break

        else:
            runrun[keta-1].append(ini*10+ini%10-1)
            count+=1
            if count==x:
                end=True
                ans=ini*10+ini%10-1
                break
            runrun[keta-1].append(ini*10+ini%10)
            count+=1
            if count==x:
                end=True
                ans=ini*10+ini%10
                break
            runrun[keta-1].append(ini*10+ini%10+1)
            count+=1
            if count==x:
                end=True
                ans=ini*10+ini%10+1
                break

    keta +=1
    runrun.append([])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

q = deque(list(range(1, 10)))
ctr = 0
while ctr < K:
    val = q.popleft()
    ctr += 1
    for i in range(-1, 2):
        add = (val % 10) + i
        if 0 <= add <= 9:
            q.append(val * 10 + add)
            
print(val)

Submission status: Accepted

Solution code:
K = int(input())

def dfs(d, val, x):
    x.append(val)
    
    if d == 10:
        return
    
    for i in range(-1, 2):
        add = (val % 10) + i
        if 0 <= add <= 9:
            dfs(d + 1, val * 10 + add, x)

x = []
for i in range(1, 10):
    dfs(0, i, x)
print(sorted(x)[K - 1])

Submission status: Accepted

Solution code:
import collections

k = int(input())
q = collections.deque(list(range(1, 10)))
i = 0

while i < k:
    i += 1

    org = q.popleft()
    x = org % 10

    if x != 0:
        q.append(10 * org + x - 1)

    q.append( 10 * org + x)

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

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

K = int(input())

lunluns = collections.deque()
for i in range(1, 10):
    lunluns.append(str(i))

# lunluns = []
for i in range(K - 9):
    a = lunluns[i]
    if a[-1] == "9":
        for j in ["8", "9"]:
            lunluns.append(a + j)
    elif a[-1] == "0":
        for j in ["0", "1"]:
            lunluns.append(a + j)
    else:
        base = int(a[-1])
        for j in range(base - 1, base + 2):
            lunluns.append(a + str(j))

print(lunluns[K - 1])

Submission status: Accepted

Solution code:
k = int(input())

c = []


# for k in range(k + 1):
#     n = c[k]
#     m = n % 10
#     for i in range(-1, 2):
#         if 0 <= m + i <= 9:
#             c.append(n * 10 + m + i)

def lunlun(d, num):
    if d > 10:
        return

    c.append(num)

    m = num % 10
    for i in range(-1, 2):
        if 0 <= m + i <= 9:
            lunlun(d + 1, num * 10 + m + i)


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

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

Submission status: Accepted

Solution code:
k = int(input())

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


for k in range(k + 1):
    n = c[k]
    m = n % 10
    for i in range(-1, 2):
        if 0 <= m + i <= 9:
            c.append(n * 10 + m + i)


print(c[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:
def function(n):
  string = str(n)
  for i in range(len(string) - 1):
    error = int(string[i]) - int(string[i + 1])
    if error > 1:
      return i + 1, error
    elif error < -1:
      return i, abs(error)
  return -1, 0
 
k = int(input())
ans = []
n = 1
while len(ans) < k:
  m, error = function(n)
  if m == -1:
    ans.append(n)
    n += 1
  else:
    n = n + (error - 1) * (10 ** (len(str(n)) - m - 1)) - n % (10 ** (len(str(n)) - m - 1))
print(ans[-1])

Submission status: Accepted

Solution code:
def dfs(d, r):
    global l
    if d == 11:
        return
    l.append(int(r))
    for i in range(-1, 2):
        tmp = int(r[-1]) + i
        if 0 <= tmp <= 9:
            dfs(d + 1, r + str(tmp))


k = int(input())
l = []
for i in range(1, 10):
    dfs(1, str(i))
print(sorted(l)[k - 1])

Submission status: Accepted

Solution code:
def dfs(d, r):
    global l
    if d == 11:
        return
    l.append(int(r))
    for i in range(-1, 2):
        tmp = int(r[-1]) + i
        if 0 <= tmp <= 9:
            dfs(d + 1, r + str(tmp))


k = int(input())
l = []
for i in range(1, 10):
    dfs(0, str(i))
print(sorted(l)[k - 1])

Submission status: Accepted

Solution code:
cur = []

def recur(n):
    if n > 10 ** 10:
        return
    cur.append(n)
    for i in range(10):
        if abs(n % 10 - i) <= 1:
            recur(10 * n + i)

for i in range(1, 10):
    recur(i)
cur.sort()
n = int(input())
print((cur[n - 1]))

Submission status: Accepted

Solution code:
K = int(input())

# init
lst = [[i for i in range(1,10)]]
total=9

## 8: 7, 8, 9
## 9: 8, 9
## 0: 0, 1

while total < K:
    lst.append([])
    for i in lst[-2]:
        strnum = str(i)
        last = int(strnum[-1])
        
        lst[-1].append(strnum + str(last))
        if last <= 8:
            lst[-1].append(strnum + str(last+1))
        if last >= 1:
            lst[-1].append(strnum + str(last-1))
            
    total += len(lst[-1])

lst[-1].sort()
print(lst[-1][K-total-1])

Submission status: Accepted

Solution code:
K = int(input())

lunlun = set()

def dfs(A):
    # 終端条件 --- 10 重ループまで回したら処理して打ち切り
    if len(A) == 10:
        return
    for v in range(0, 10):
        if len(A) != 0:
            if abs(A[-1] - v) > 1:
                continue
        A.append(v)
        lunlun.add(int(''.join(list(map(str, A)))))
        dfs(A)
        A.pop() # これが結構ポイント

dfs([])

print(sorted(list(lunlun))[K])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def dfs(A, i):
    A.append(i)
    if len(str(i)) == 10:
        return A
    x = int(list(str(i))[-1])-1 if int(list(str(i))[-1]) > 0 else 0
    y = int(list(str(i))[-1])+2 if int(list(str(i))[-1]) < 9 else 10
    for v in range(x, y):
        i = i * 10 + v
        dfs(A, i)
        i = int(str(i)[:len(str(i))-1])

K = int(input())
B = []
for i in range(1, 10):
    A = []
    dfs(A,i)
    B = B + A
B.sort()
print(B[K-1])

Submission status: Accepted

Solution code:
K = int(input())
r = [[] for _ in range(10)]
r[0] = list(range(1,10))

for i in range(9):
  for a in r[i]:
    s = str(a)
    d = a%10
    for j in range(d-1, d+2):
      if not 0 <= j <= 9: continue
      r[i+1].append(int(s+str(j)))

for i in range(10):
  if K >= len(r[i]):
    K -= len(r[i])
  else:
    print(r[i][K-1])
    break

Submission status: Accepted

Solution code:
K = int(input())
lunlun = []
# x=123


def dfs(x):
    lunlun.append(x)

    if len(str(x)) == 11:
        return

    a = x % 10
    for v in [-1, 0, 1]:
        b = a + v
        if 0 <= b <= 9:
            y = x*10 + b
            dfs(y)


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

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

Submission status: Accepted

Solution code:
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""

from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def floor(a, b):
    """floor(a/b) 整数値を返す"""
    c = (a - a % b)/b
    return int(c)


def main():

    K = int(input())
    q = deque()
    for i in range(1, 10):
        q.append(i)
    cnt = 9
    if cnt >= K:
        print(q[K-1])
        sys.exit()
    while cnt < K:
        x = q.popleft()
        d = x % 10
        for v in [d-1, d, d+1]:
            if 0 <= v <= 9:
                y = x*10 + v
                q.append(y)
                cnt += 1
                if cnt == K:
                    break
    print(y)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""

from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def floor(a, b):
    """floor(a/b) 整数値を返す"""
    c = (a - a % b)/b
    return int(c)


def main():

    def dfs(x):
        lunlun.append(x)
        d = x % 10
        if len(str(x)) == 11:
            return

        for v in [d+1, d, d-1]:
            if 0 <= v <= 9:
                dfs(x*10+v)

    K = int(input())
    cnt = 0
    lunlun = []

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

A = deque(range(1,10))

count = 0
for _ in range(N):
    k = A.popleft()
    m = k % 10
    if m != 0:
        A.append(10 * k + m -1)
    A.append(10 * k + m)
    if m != 9:
        A.append(10 * k + m + 1)
print(k)

Submission status: Accepted

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

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

for i in range(1,k+1):
  x = q.popleft()
  
  if i == k:
    print(x)
    exit()
    
  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)

Submission status: Accepted

Solution code:
def dfs(x):
    ans.append(x)
    if len(str(x))==10:
        return
    
    last=x%10
    
    for i in [last-1,last,last+1]:
        if 0<=i<=9:
            dfs(10*x+i)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k = int(input())

ls = []
for i in range(1,10):
  ls.append(i)
idx_next = 0
for i in range(1,10):
  idx = idx_next
  idx_next = len(ls)
  for v in ls[idx:]:
    r = v%10
    if r-1 >= 0:
      ls.append(v*10+r-1)
    ls.append(v*10+r)
    if r+1 <= 9:
      ls.append(v*10+r+1)
print(ls[k-1])

Submission status: Accepted

Solution code:
k = int(input())
L = [1,2,3,4,5,6,7,8,9]
i = 0
while i < k:
    if int(str(L[i])[-1]) == 0:
        n2 = L[i]*10 + L[i]%10
        n3 = L[i]*10 + L[i]%10 +1
        L.append(n2)
        L.append(n3)
    elif 1 <= int(str(L[i])[-1]) <= 8:
        n1 = L[i]*10 + L[i]%10 -1
        n2 = L[i]*10 + L[i]%10
        n3 = L[i]*10 + L[i]%10 +1
        L.append(n1)
        L.append(n2)
        L.append(n3)
    elif int(str(L[i])[-1]) == 9:
        n1 = L[i]*10 + L[i]%10 -1
        n2 = L[i]*10 + L[i]%10
        L.append(n1)
        L.append(n2)
    i +=1

print(L[k-1])