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: Time Limit Exceeded

Solution code:
K = int(input())

#一桁
#1から9まで全部 -> 1 * 9

#二桁
#10 11 12 21 22 23 32 33 34... 98 99 -> 3 * 8 + 2

#三桁
#100 101 110 111 112 121 122 123


def isLunLun(n):
    if (n < 10):
        return 1

    strN = str(n)
    for i in range(len(strN) - 1):
        if (abs(int(strN[i]) - int(strN[i + 1])) > 1):
            return 0
    return 1

counter = 1
n = 1
while(K > counter):
    n += 1
    tmp = int(isLunLun(n))
    if (1 == tmp):
        counter += 1

print(n)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
def Lun(k):
	str_k=str(k)
	check=True
	if len(str_k)==1:
		return check
		
	for i in range(len(str_k)-1):
		if (int(str_k[i])+1)>=int(str_k[i+1])>=(int(str_k[i])-1):
			check=True
		else:
			check=False
			return check
	return check
K=int(input())
cnt=1
cnt_L=0
L=0
while True:
	if Lun(cnt):
		cnt_L+=1
		if cnt_L==K:
			L=cnt
			break
	cnt+=1

print(L)

Submission status: Time Limit Exceeded

Solution code:
#幅
k = int(input())
ans = []
queue = [i for i in range(1,10)]

while queue:
    if len(ans)==k:
        print(ans[k-1])
        break
    now = queue.pop(0)
    ans.append(now)
    if int(str(now)[-1]) -1 >= 0:
        queue.append(int(str(now) +str(int(str(now)[-1])-1)))

    queue.append(int(str(now) +str(now)[-1]))

    if int(str(now)[-1]) +1 <= 9:
        queue.append(int(str(now) +str(int(str(now)[-1])+1)))

Submission status: Time Limit Exceeded

Solution code:
def nextLunlunNumber(prefix):
    if prefix == 0:
        return [1, 2, 3, 4, 5, 6, 7, 8, 9]
    last = (prefix % 10)
    if last == 0:
        return [prefix*10 + last, prefix*10 + last+1]
    elif last == 9:
        return [prefix*10 + last-1, prefix*10 + last]
    else:
        return [prefix*10 + last-1, prefix*10 + last, prefix*10 + last+1]

def main():
    lns = [None] * 100000
    q = nextLunlunNumber(0)
    i = 0
    while q and i < (100000):
        n = q.pop(0)
        lns[i] = n
        q += (nextLunlunNumber(n))
        i += 1
    k = int(input())
    print(lns[k-1])

main()

Submission status: Time Limit Exceeded

Solution code:
k = int(input())

def check(i):
  s = str(i)
  flag = True
  for j in range(len(s)-1):
    if (abs(int(s[j])-int(s[j+1])) >= 2):
      flag = False
  return flag

cnt = 0
for i in range(1, 3234566667):
  if (len(str(i)) == 1):
    cnt += 1
  elif(check(i)):
    cnt += 1

  if (cnt == k):
    print(i)
    break

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
a = list(map(str, list(range(1, 10))))
ans = a + []
while len(ans) < k:
    b = []
    for i in a:
        if i == "323456667":
            break
        il = i[-1]
        intil = int(il)
        if il == "0":
            ad = ["0","1"]
        elif il == "9":
            ad = ["8","9"]
        else:
            ad = [intil-1, intil, intil+1]
        c = [i + str(j) for j in ad]
        b = b + c
    a = b
    ans = ans + b

print(ans[k-1])

Submission status: Time Limit Exceeded

Solution code:
def f(n):
    
    for i in range(len(str(n))-1):
        if abs(int(str(n)[i])-int(str(n)[i+1]))>1:
            return False
    return True
            
    
n= int(input())
cnt=0
i=1
while True:
    if f(i)==True:
        cnt=cnt+1
        if cnt==n:
            print(i)
            break
    i=i+1

Submission status: Time Limit Exceeded

Solution code:
K=int(input())

def log(X):
    s = 1
    t = 0
    while s <= X:
        s = 10 *s
        t = t + 1
    return t
        
def element(X):
    L = log(X)
    List = []
    Y = X
    for i in range(L):
        List.append((Y%(10**(i+1)))//(10**i))
        Y = Y - Y%(10**(i+1))
    return List


s = 0
t = 1
while s < K:
    if log(t) == 1:
        s = s+1
        t = t+1
    else:
        judge = 0
        for i in range(log(t)-1):
            if element(t)[i]-1 > element(t)[i+1] or element(t)[i+1] > element(t)[i]+1:
                judge = judge +1
        if judge == 0:
            s = s+1
            t = t +1
        else:
            t = t+1
            
print(t-1)

Submission status: Time Limit Exceeded

Solution code:
K=int(input())
answer=0
count=0
i=1

while count<K:
    if i<=9:
        count+=1
        if count==K:
            answer=i
            break
    else:
        S=str(i)
        judge=True
        for j in range(1,len(S)):
            if abs(int(S[j-1])-int(S[j]))<=1:
                pass
            else:
                judge=False
        if judge==True:
            count+=1
            if count==K:
                answer=i
                break
    i+=1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys

K = int(input())
count = 9
out = 0

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


for i in range(10,3234566667):
  si = list(map(int, str(i)))

  for j in range(0,(len(str(i)) - 1)):
    if abs(int(si[j]) - int(si[j+1])) > 1:
      out = out + 1
    
  if out == 0:
    count = count + 1 

  if count == K:
    Ans = i
    break
  
  out = 0

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())

def lunlun(x):
    if x == 0:
        return False
    s = str(x)
    good = True
    for i in range(1, len(s)):
        if abs(int(s[i - 1]) - int(s[i])) > 1:
            good = False
    return good

n = 0
last = 0
total = 0
while total < k:
    if lunlun(n):
        last = n
        total += 1
    n += 1

print(last)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
cnt = 0
num = 0

while True:
    if cnt == k:
        break
    num += 1
    list_num = list(str(num))
    a = 0
    for i in range(len(list_num)):
        if i+1 == len(list_num):
            break
        if abs(int(list_num[i])-int(list_num[i+1])) > 1:
            a = 1
    if a == 0:
        cnt += 1

print(num)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
      input = sys.stdin.readline
      K = int(input())
      low, high = 0, 3234566668
      while high - low > 1:
            mid = (low + high) // 2
            midS = str(mid)
            lenS = len(midS)
            q = deque()
            for j in range(lenS):
                  for i in range(1, 10): q.append((i, i, j + 1))
            count = 0
            isRunrun = False
            while q:
                  ns, last, length = q.pop()
                  if length == lenS:
                        if ns <= mid: count += 1
                        if ns == mid: isRunrun = True
                  else:
                        if last == 0: 
                              q.append((ns*10 + 1, 1, length + 1))
                              q.append((ns*10 + 0, 0, length + 1))
                        elif last == 9: 
                              q.append((ns*10 + 8, 8, length + 1))
                              q.append((ns*10 + 9, 9, length + 1))
                        else:
                              q.append((ns*10 + last+1, last + 1, length + 1))
                              q.append((ns*10 + last-1, last - 1, length + 1))
                              q.append((ns*10 + last, last, length + 1))
            if count > K: high = mid
            elif count == K:
                  if isRunrun: low = mid
                  else: high = mid
            else: low = mid
            #print(mid, count)
      print(low)
            
      return 0

if __name__ == "__main__":
      solve()

Submission status: Time Limit Exceeded

Solution code:
def nextLunlunNumber(prefix):
    if prefix == 0:
        return [1, 2, 3, 4, 5, 6, 7, 8, 9]
    last = (prefix % 10)
    if last == 0:
        return [prefix*10 + last, prefix*10 + last+1]
    elif last == 9:
        return [prefix*10 + last-1, prefix*10 + last]
    else:
        return [prefix*10 + last-1, prefix*10 + last, prefix*10 + last+1]

def main():
    lns = []
    q = nextLunlunNumber(0)
    while q and len(lns) < (100000):
        n = q.pop(0)
        lns.append(n)
        q.extend(nextLunlunNumber(n))
    k = int(input())
    print(lns[k-1])

main()

Submission status: Time Limit Exceeded

Solution code:
k=int(input())
r=0
i=1
while r<k:
    s=0
    d=str(i)
    for z in range(1,len(d)) :
        if abs(int(d[z])-int(d[z-1]))>1:
            s+=1
    if s==0:
        r+=1
        if r==k:
            print(i)
    i+=1

Submission status: Time Limit Exceeded

Solution code:
K=int(input())
i=1
current_num=0
while (i<=K) :
  current_num+=1
  current_string=str(current_num)
  
  
  
  flag=True
  for k in range(len(current_string)-1) :
    
    if abs(int(current_string[k])-int(current_string[k+1]))>1 :
      
      flag=False
      break
  if flag==True :
    i+=1
  
  
print(current_num)

Submission status: Time Limit Exceeded

Solution code:
# Code for D - Lunlun Number
# Use input() to fetch data from STDIN
k = int(input())

queue = []
for i in range(9):
    queue.append([i + 1])

def t(parents):
    n = parents[-1]
    if n == 9:
        queue.append(parents + [8])
        queue.append(parents + [9])
    elif n == 0:
        queue.append(parents + [0])
        queue.append(parents + [1])
    else:
        queue.append(parents + [n - 1])
        queue.append(parents + [n])
        queue.append(parents + [n + 1])

for i in range(k):
    p = queue.pop(0)
    t(p)
    if i + 1 == k:
        print("".join(map(str, p)))

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
a = list(map(str, list(range(1, 10))))
ans = a + []
while len(ans) < k:
    b = []
    for i in a:
        inti = int(i)
        if inti > 323456666:
            break
        il = i[-1]
        intil = int(il)
        if intil == 0:
            ad = [0,1]
        elif intil == 9:
            ad = [8,9]
        else:
            ad = [intil-1, intil, intil+1]
        c = [i + str(j) for j in ad]
        b = b + c
    a = b
    ans = ans + b

print(ans[k-1])

Submission status: Time Limit Exceeded

Solution code:
def is_ll(n):
  ns = str(n)
  if len(ns) == 1:
    return True
  else:
    for x in range(len(ns)-1):
      if 1 < abs(int(ns[x]) - int(ns[x+1])):
        return False

    return True
  
K = list(map(int,input().split()))[0]

cnt_ll = 0
num = 1

while cnt_ll!=K:
  if is_ll(num):
    cnt_ll += 1
  num += 1

print(num-1)

Submission status: Time Limit Exceeded

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

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

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

MII = map_int_input

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

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

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

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

LII = list_int_inputs

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

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

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

K = input_int()

# pn = deque()
# pn.append(1)
A = 3234566668
count = 0
for L in range(1, A):
    str_L = str(L)
    chk = True
    for left in range(len(str_L) - 1):
        if abs(int(str_L[left]) - int(str_L[left + 1])) > 1:
            chk = False
            break

    if chk:
        # pn.append(L)
        count += 1
        if count == K:
            ans = L
            break


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    K = int(input())
    for i in range(1,10**8):
        r = True
        s = str(i)
        if len(s) != 1:
            for j in range(len(s)-1):
                if abs(int(s[j])-int(s[j+1])) > 1:
                    r = False
                    break
        if r:
            K -= 1
            if K == 0:
                print(i)
                break
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

k = int(input())
a = list(range(1, 10))
ans = a + []
while len(ans) < k:
    b = []
    for i in a:
        if i > 323456666:
            break
        il = str(i)[-1]
        intil = int(il)
        if intil == 0:
            ad = [0,1]
        elif intil == 9:
            ad = [8,9]
        else:
            ad = [intil-1, intil, intil+1]
        c = [int(str(i) + str(j)) for j in ad]
        b = b + c
    a = b
    ans = ans + b

print(ans[k-1])

Submission status: Time Limit Exceeded

Solution code:
k=int(input())
r=0
for i in range (1,323456667):
    s=0
    d=str(i)
    for z in range(1,len(d)) :
        if abs(int(d[z])-int(d[z-1]))>1:
            s+=1
    if s==0:
        r+=1
        if r==k:
            print(i)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

     runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     count = 0
     while(len(runrun) < k):
          target = runrun[count]
          runrun = runrun + make(target)
          count += 1
          # print(runrun)

     print(runrun[k-1])

def make(n):
     num = n % 10
     if num == 0:
          return [n * 10 + num, n * 10 + num + 1]
     elif num == 9:
          return [n * 10 + num - 1, n * 10 + num]
     else:
          return [n * 10 + num - 1, n * 10 + num, n * 10 + num + 1]

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
count = 0
num = 1

while count!=k:
    N = str(num)
    check = 0
    for i in range(len(N)-1):
        if abs(int(N[i])-int(N[i+1]))>1:
            check = 1
    if check==0:
        count += 1
    num += 1

print(num-1)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())

runrun = 0
n = 1
while(True):
    s = str(n)
    prev = int(s[0])
    isOK = True
    for c in s:
        if abs(int(c) - prev) <=1:
            prev = int(c)
        else:
            isOK = False
            break
    if isOK:
        runrun+=1
    if runrun == K:
        break
    n+=1
print(n)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
x = 1

def check(y):
	n = len(y)
	for i in range(n-1):
		if abs(ord(y[i])-ord(y[i+1])) <= 1:
			continue
		return False
	return True
ans = 0

while(True):
	y = str(x)
	if check(y):
		ans += 1
		if k == ans:
			print(y)
			exit()
	x += 1

Submission status: Time Limit Exceeded

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

num=0
i=0

while num!=K:
    i+=1
    list_i=list(map(int,str(i)))
    flg=True
    for j in range(len(list_i)):
        if j>0:
            if abs(list_i[j-1]-list_i[j])>1:
                flg=False
    
    if flg:
        num+=1

print(i)

Submission status: Time Limit Exceeded

Solution code:
cnt = 0

k = int(input())
"""
def bt(l):
    if cnt == k:
        print("".join(map(str,l)))
    else:
        if len(l) == 1:
            if l[0] == 9:
                bt([1,0])
"""
def islunlun(l):
    for x in range(1,len(l)):
        if abs(ord(l[x])-ord(l[x-1])) > 1:
            return False
    return True

cnt = 0
x = 1
while True:
    if islunlun(str(x)):
        cnt += 1
    if cnt == k:
        print(x)
        exit(0)
    x += 1

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
A = "0123456789"
S = [i for i in range(1,10)]
Q = [str(i) for i in range(1,10)]
while Q:
    q = Q.pop(0)
    D = []
    if q[-1]=="0":
        D = [q+"0",q+"1"]
    elif q[-1]=="9":
        D = [q+"0",q+"1"]
    else:
        a = A.index(q[-1])
        D = [q+A[a-1],q+A[a],q+A[a+1]]
    for d in D:
        S.append(int(d))
        if len(d)<11:
            Q.append(d)
S.sort()
print(S[K-1])

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
queue = deque([1,2,3,4,5,6,7,8,9])
count = 1
while count <= K:
  num = queue.popleft()
  if num%10!=0:
    queue.append(num*10+num%10-1)
  queue.append(num*10+num%10)
  if num%10!=9:
    queue.append(num*10+num%10+1)
  count+=1
  
print(num)

Submission status: Accepted

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

d = deque()
c = 0
for i in range(1, 10):
  d.append(i)

while True:
  tmp = d.popleft()
  c += 1
  if c == k:
    ans = tmp
    break
  if tmp % 10 != 0:
    d.append(tmp * 10 + (tmp % 10 - 1))
  d.append(tmp * 10 + tmp % 10)
  if tmp % 10 != 9:
    d.append(tmp * 10 + (tmp % 10 + 1))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
nums = deque([])
for i in range(1, 10):
  nums.appendleft(i)
count = 1
while count < K:
  num = nums.pop()
  last = int(str(num)[-1])
  for i in range(max(0, last-1), min(10, last+2)):
    nums.appendleft(int(str(num)+str(i)))
  count += 1
print(nums.pop())

Submission status: Accepted

Solution code:
from collections import deque

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

while len(queue) < 10 ** 5:
    n_str = queue.popleft()
    last_c = n_str[len(n_str) - 1]
    if last_c == "0":
        queue.append(n_str + "0")
        queue.append(n_str + "1")

        lunlun.append(n_str + "0")
        lunlun.append(n_str + "1")
    elif last_c == "1":
        queue.append(n_str + "0")
        queue.append(n_str + "1")
        queue.append(n_str + "2")

        lunlun.append(n_str + "0")
        lunlun.append(n_str + "1")
        lunlun.append(n_str + "2")
    elif last_c == "2":
        queue.append(n_str + "1")
        queue.append(n_str + "2")
        queue.append(n_str + "3")

        lunlun.append(n_str + "1")
        lunlun.append(n_str + "2")
        lunlun.append(n_str + "3")
    elif last_c == "3":
        queue.append(n_str + "2")
        queue.append(n_str + "3")
        queue.append(n_str + "4")

        lunlun.append(n_str + "2")
        lunlun.append(n_str + "3")
        lunlun.append(n_str + "4")
    elif last_c == "4":
        queue.append(n_str + "3")
        queue.append(n_str + "4")
        queue.append(n_str + "5")

        lunlun.append(n_str + "3")
        lunlun.append(n_str + "4")
        lunlun.append(n_str + "5")
    elif last_c == "5":
        queue.append(n_str + "4")
        queue.append(n_str + "5")
        queue.append(n_str + "6")

        lunlun.append(n_str + "4")
        lunlun.append(n_str + "5")
        lunlun.append(n_str + "6")
    elif last_c == "6":
        queue.append(n_str + "5")
        queue.append(n_str + "6")
        queue.append(n_str + "7")

        lunlun.append(n_str + "5")
        lunlun.append(n_str + "6")
        lunlun.append(n_str + "7")
    elif last_c == "7":
        queue.append(n_str + "6")
        queue.append(n_str + "7")
        queue.append(n_str + "8")

        lunlun.append(n_str + "6")
        lunlun.append(n_str + "7")
        lunlun.append(n_str + "8")
    elif last_c == "8":
        queue.append(n_str + "7")
        queue.append(n_str + "8")
        queue.append(n_str + "9")

        lunlun.append(n_str + "7")
        lunlun.append(n_str + "8")
        lunlun.append(n_str + "9")
    elif last_c == "9":
        queue.append(n_str + "8")
        queue.append(n_str + "9")

        lunlun.append(n_str + "8")
        lunlun.append(n_str + "9")

print(lunlun[K-1])

Submission status: Accepted

Solution code:
def main():
    K = int(input()) 

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

    start1 = ["1"]
    start2 = ["2"]
    start3 = ["3"]
    start4 = ["4"]
    start5 = ["5"]
    start6 = ["6"]
    start7 = ["7"]
    start8 = ["8"]
    start9 = ["9"]

    while len(lunlun) < 10 ** 5:
        next_starts = []
        for i in range(1, 10):
            news = []
            if i == 1:
                for n in start1:
                    if len(n) == 1:
                        new_n = n + "0"
                    else:
                        if abs(int(n[0])) > 1 or abs(int(n[1])) > 1:
                            break
                        new_n = n[0] + "0" + n[1:]
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start1:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start2:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 2:
                for n in start1:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start2:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start3:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 3:
                for n in start2:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start3:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start4:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 4:
                for n in start3:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start4:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start5:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 5:
                for n in start4:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start5:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start6:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 6:
                for n in start5:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start6:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start7:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 7:
                for n in start6:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start7:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start8:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 8:
                for n in start7:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start8:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start9:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)
            elif i == 9:
                for n in start8:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                for n in start9:
                    new_n = str(i) + n
                    lunlun.append(new_n)
                    news.append(new_n)
                next_starts.append(news)

        start1 = next_starts[0]
        start2 = next_starts[1]
        start3 = next_starts[2]
        start4 = next_starts[3]
        start5 = next_starts[4]
        start6 = next_starts[5]
        start7 = next_starts[6]
        start8 = next_starts[7]
        start9 = next_starts[8]

    print(lunlun[K-1])

main()

Submission status: Accepted

Solution code:
from collections import deque
 
K = int(input())
 
count = 0
Q = deque([1,2,3,4,5,6,7,8,9])
while count != K:
  a = Q.popleft()
  b = a%10
  if b != 0:
    Q.append(a*10 + b - 1)
  Q.append(a*10 + b)
  if b != 9:
    Q.append(a*10 + b + 1)
  count += 1
  #print(Q)
print(a)

Submission status: Accepted

Solution code:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())
import sys
sys.setrecursionlimit(10**6)

def valid(i):
    ar=[]
    if i-1>=0:
        ar.append(i-1)
    ar.append(i)
    if i+1<=9:
        ar.append(i+1)
    return ar

k=int(input())
cur=[1,2,3,4,5,6,7,8,9]
if k<=9:
    print(cur[k-1])
else:
    while(k>len(cur)):
        new_cur=[]
        for i in cur:
            temp=valid(i%10)
            for j in temp:
                new_cur.append(i*10 + j)
        k-=len(cur)
        cur=new_cur.copy()
    print(cur[k-1])

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(K):
    runrun = q.popleft()
    rem = runrun % 10
    if rem == 0:
        q.append(runrun * 10)
        q.append(runrun * 10 + rem + 1)
    elif rem == 9:
        q.append(runrun * 10 + rem - 1)
        q.append(runrun * 10 + rem)
    else:
        q.append(runrun * 10 + rem - 1)
        q.append(runrun * 10 + rem)
        q.append(runrun * 10 + rem + 1)

print(runrun)

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(k):
    a = q.popleft()
    b = a % 10
    if b == 0:
        q.append(a * 10)
        q.append(a * 10 + b + 1)
    elif b == 9:
        q.append(a * 10 + b - 1)
        q.append(a * 10 + b)
    else:
        q.append(a * 10 + b - 1)
        q.append(a * 10 + b)
        q.append(a * 10 + b + 1)

print(a)

Submission status: Accepted

Solution code:

from collections import deque

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

if k <= 9:
    print(q[k-1])
    exit()

i = 9
while 1:
    a = q.popleft()
    b = a % 10
    if b == 0:
        q.append(a * 10)
        i += 1
        if i == k:
            print(q[-1])
            exit()
        q.append(a * 10 + b + 1)
        i += 1
        if i == k:
            print(q[-1])
            exit()
    elif b == 9:
        q.append(a * 10 + b - 1)
        i += 1
        if i == k:
            print(q[-1])
            exit()
        q.append(a * 10 + b)
        i += 1
        if i == k:
            print(q[-1])
            exit()
    else:
        q.append(a * 10 + b - 1)
        i += 1
        if i == k:
            print(q[-1])
            exit()
        q.append(a * 10 + b)
        i += 1
        if i == k:
            print(q[-1])
            exit()
        q.append(a * 10 + b + 1)
        i += 1
        if i == k:
            print(q[-1])
            exit()

Submission status: Accepted

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

for i in A:
  if K<len(A):
    break
  x = i%10
  for j in range(max(x-1,0),min(x+2,10)):
    A.append(10*i+j)

print(A[K-1])

Submission status: Accepted

Solution code:
import queue
def resolve():
    n = int(input())
    q = queue.Queue()
    for i in range(1,10):
        q.put(i)
    for _ in range(n):
        x = q.get()
        if x%10!=0:
            q.put(10*x+(x%10)-1)
        q.put(10*x+(x%10))
        if x%10!=9:
            q.put(10*x+(x%10)+1)
    print(x)
resolve()

Submission status: Accepted

Solution code:
import heapq
K = int(input())
def NewLun(strX):
    if strX[-1] != '0' and strX[-1] != '9':
        intX0 = int(strX[-1])
        heapq.heappush(Lun,int(strX + str(intX0+1)))
        heapq.heappush(Lun,int(strX + str(intX0)))
        heapq.heappush(Lun,int(strX + str(intX0-1)))
    elif strX[-1] == '0':
        heapq.heappush(Lun,int(strX + '0'))
        heapq.heappush(Lun,int(strX+'1'))
    else:
        heapq.heappush(Lun,int(strX +'9'))
        heapq.heappush(Lun,int(strX+'8'))
Lun = [i for i in range(1,10)]
heapq.heapify(Lun)
for _ in range(K):
    Ans = heapq.heappop(Lun)
    NewLun(str(Ans))
print(Ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

print(ans)

#解説+コードカンニングAC

Submission status: Accepted

Solution code:
def update_queue(n, queue):
    out = queue[n]
    mod10 = out % 10
    if mod10 != 0:
        queue.append(10 * out + mod10 - 1)
    queue.append(10 * out + mod10)
    if mod10 != 9:
        queue.append(10 * out + mod10 + 1)

    return out, queue

N = int(input())
Q = [1,2,3,4,5,6,7,8,9]

for i in range(N):
    out, Q = update_queue(i, Q)

print(out)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 12 22:49:54 2020

@author: liang
"""

""" 
【小さいものから探索　⇒　キューを用いる】
【幅優先探索の応用】
     10 + 1 + 1
1 => 10 + 1 + 0
     10 + 1 - 1

10 => 100 + 0 + 1
      100 + 0 + 0
      100 + 0 - 1 *
"""

from collections import deque

K = int(input())

q = deque()
for i in range(1,10):
    q.append(i)
    
cnt = 0
while cnt  != K:
    cnt += 1
    ans = q.popleft()
    #print(ans)
    if ans % 10 != 0:
        q.append(10*ans + ans%10 - 1)
    q.append(10*ans + ans%10 )
    if ans % 10 != 9:
        q.append(10*ans + ans%10 + 1)
print(ans)