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()) 
 
lunlun = [i for i in range(1, 10)]
 
p = 0 

def generate_lunlun(p):
    last = p % 10
    if last - 1 >= 0:
        yield p * 10 + last - 1
    yield p * 10 + last
    if last + 1 <= 9:
        yield p * 10 + last + 1 

while len(lunlun) < k:
    for new_lunlun in generate_lunlun(lunlun[p]):
        lunlun.append(new_lunlun)
    p += 1

print(lunlun[k-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
K=int(input())
la=[]
tmp=0
sans=""
def f(tmp,K,i,j):
    global sans
    #if tmp==K:

    if j==9:
        ra=range(8,10)
    elif j==0:
        ra=range(2)
    else:
        ra=range(j-1,j+2)
    #for k in range(10):
    for k in ra:
        tmp+=la[i-1][k]
        if tmp==K and i==1:
            sans+=str(k)
            return
        elif tmp>=K:
            #print("tmp:",tmp)
            #print("K:",K)
            sans+=str(k)
            #f(0,tmp-K,i-2,k)
            #f(tmp-la[i-1][k],K,i-2,k)
            f(tmp-la[i-1][k],K,i-1,k)
            return
        """
        elif tmp==K and i==1:
            sans+=str(k)
            return
        """



for i in range(100):#keta=i+1
    la.append([0 for _ in range(10)])
    if i==0:
        #la[i][0]=0
        la[i][0]=1
        for j in range(1,10):
            la[i][j]=1
            tmp+=1
            if tmp==K:
                sans=str(j)
                break
        else:
            continue
        break
    else:
        #la[i][0]=sum(la[i-1])#
        la[i][0]=sum(la[i-1][:2])
        for j in range(1,10):
            if j==9:
                la[i][9]=sum(la[i-1][8:])
            else:
                la[i][j]=sum(la[i-1][j-1:j+2])
            tmp+=la[i][j]
            if tmp>=K:
                #print("tmp:",tmp)
                #print("j:",j)
                sans+=str(j)
                #K=tmp-K
                #tmp=0
                tmp-=la[i][j]
                f(tmp,K,i,j)
                break
        else:
            continue
        break
#print("la:",la)
#print(sans)
print(int(sans))

#la[0][0]直す
#初めて数字決定したあとの数字探し関数における
#、MSBに関するfor
#K,tmpの更新式を直す
#再帰f後のbreakまわり
#再帰fの終了条件_36_100の例
#ai[0]がおかしい_38_110の例

Submission status: Accepted

Solution code:
k=int(input())
#a,b=map(int,input().split())
#l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

from collections import deque

q=deque([1,2,3,4,5,6,7,8,9])
ansl=[]
s=1
while len(str(s))<=10:
    s=q.popleft()
    ansl.append(s)
    sl=list(str(s))
    last_digit=int(sl[-1])
    for digit in range(max(0,last_digit-1),min(last_digit+1,9)+1):
        newval=int(str(s)+str(digit))
        #ansl.append(int(str(s)+str(digit)))
        q.append(newval)
print(ansl[k-1])

Submission status: Accepted

Solution code:
k=int(input())
a=[]
def judge(x):
    if x> 3234566667:
        return
    a.append(x)
    for i in range(10):
        if abs(x%10-i)<=1:
            judge(x*10+i)

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

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

Submission status: Accepted

Solution code:
k =  int(input())

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

while(1):
    if k <= len(a):
        print (a[k-1])
        break

    b = []
    k = k - len(a)

    for x in a:
        for i in [-1,0,1]:
            d =  x%10  + i
            if d < 0 or d > 9: continue
            b.append( x*10 + d)
    a = b.copy()

Submission status: Accepted

Solution code:
k = int(input())
a=['1','2','3','4','5','6','7','8','9']
 
while k>len(a):
    b=[]
    for i in a:
        if i[-1]!='0':
            b.append(i+chr(ord(i[-1])-1))
        b.append(i+i[-1])
        if i[-1]!='9':
            b.append(i+chr(ord(i[-1])+1))
    k-=len(a)
    a=b.copy()
 
print(a[k-1])

Submission status: Accepted

Solution code:
k =  int(input())

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

while(1):
    if k <= len(a):
        print (a[k-1])
        break

    b = []
    k = k - len(a)
    x = a
    a = b
    b = x

    for x in b:
        for i in [-1,0,1]:
            d =  x%10  + i
            if d < 0 or d > 9: continue
            a.append( x*10 + d)

Submission status: Accepted

Solution code:
k =  int(input())

#make a list by 1-9


def swap(a,b):
    x = a
    a = b
    b = x

    return a,b

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

while(1):
    if k <= len(a):
        print (a[k-1])
        break

    b = []
    k = k - len(a)
    a,b = swap(a,b)

    for x in b:
        for i in [-1,0,1]:
            d =  x%10  + i
            if d < 0 or d > 9: continue
            a.append( x*10 + d)

Submission status: Accepted

Solution code:

dp = [[0,1,0,0,1,0,0,1,0,0,1,0]]
K = int(input())
sum = 0
deg = 1
flag = False

def deg_runrun(sum,i,deg,K):
    if deg == 0:
        return
    if deg == 1:
        for j in range(i-1,i+2):
            sum += dp[deg][j]
            if sum == K: 
                print(j-1,end='')
                return

    for j in range(i-1,i+2):
        if sum + dp[deg][j] >= K:
            print(j-1,end='')
            deg_runrun(sum, j, deg-1, K)
            return
        sum += dp[deg][j]


while not flag:
    dp.append([0]*12)
    for i in range(1,11):
        dp[deg][i] = dp[deg -1][i-1]+dp[deg-1][i]+dp[deg -1][i+1] 
    for i in range(2,11):
        if sum + dp[deg][i] >= K:
            print(i-1,end='')
            deg_runrun(sum, i, deg-1, K)
            flag = True
            break
        sum += dp[deg][i]
    deg += 1

print('')

Submission status: Accepted

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

while k>len(a):
    b=[]
    for i in a:
        if i[-1]!='0':
            b.append(i+chr(ord(i[-1])-1))
        b.append(i+i[-1])
        if i[-1]!='9':
            b.append(i+chr(ord(i[-1])+1))
    k-=len(a)
    a=b.copy()

print(a[k-1])

Submission status: Accepted

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

while 1:
    if k<=len(a):
        print(a[k-1])
        exit()
    b=[]
    for i in a:
        if i[-1]!='0':
            b.append(i+chr(ord(i[-1])-1))
        b.append(i+i[-1])
        if i[-1]!='9':
            b.append(i+chr(ord(i[-1])+1))
    k-=len(a)
    a=b.copy()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

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

while len(ansq)<=K:
    num = d.popleft()

    if str(num)[-1] == "0":
        da = num*10
        db = num*10+1
        d.append(da)
        d.append(db)
        ansq.append(da)
        ansq.append(db)
        continue

    if str(num)[-1] == "9":
        da = num*10+8
        db = num*10+9
        d.append(da)
        d.append(db)
        ansq.append(da)
        ansq.append(db)
        continue

    da = num*10+int(str(num)[-1])-1
    db = num*10+int(str(num)[-1])
    dc = num*10+int(str(num)[-1])+1
    d.append(da)
    d.append(db)
    d.append(dc)
    ansq.append(da)
    ansq.append(db)
    ansq.append(dc)


print(ansq[K-1])

Submission status: Accepted

Solution code:
from collections import deque

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

while len(ansq)<=K:
    num = d.popleft()

    if str(num)[-1] == "0":
        d.append(num*10)
        d.append(num*10+1)
        ansq.append(num*10)
        ansq.append(num*10+1)
        continue

    if str(num)[-1] == "9":
        d.append(num*10+8)
        d.append(num*10+9)
        ansq.append(num*10+8)
        ansq.append(num*10+9)
        continue

    d.append(num*10+int(str(num)[-1])-1)
    d.append(num*10+int(str(num)[-1]))
    d.append(num*10+int(str(num)[-1])+1)
    ansq.append(num*10+int(str(num)[-1])-1)
    ansq.append(num*10+int(str(num)[-1]))
    ansq.append(num*10+int(str(num)[-1])+1)
    
print(ansq[K-1])

Submission status: Accepted

Solution code:
import sys

def JudgeLunLun(num):
  val = num
  next = 0
  if num <= 12:
    val = num
  else:
    # 真面目なルンルン数判定。文字列に変換して1桁毎の処理を行う。
    # 加算処理に備えて文字として扱う
    A = str(num)
    for i in range(len(A)-1):
      if abs(int(A[i])-int(A[i+1])) > 1:
        val = 0
        # A[i+1]が大きい時は、A[i]をカウントアップするしかない。
        if int(A[i]) < int(A[i+1]):
          head = str(int(A[:i+1])+1)
          body = '0'
          tail = '0' * (len(A) - (i+2))
        else:
          if int(A[i]) - int(A[i+1]) > 2:
            head = A[:i+1]
            body = str(int(A[i]) -1)
            tail = '0' * (len(A) - (i+2))            
          else:
            head = A[:i+1]
            body = str(int(A[i+1]) +1)
            tail = '0' * (len(A) - (i+2))
            if body == '10':
              head = str(int(head)+1)
              body = '0'
        
        # 編集後の値を結合して数値変換して返す
        next = int(head+body+tail)
  
  return val, next

def main():
  K = int(input())
  cnt = 0
  i = 1
  while cnt < K:
    val, next = JudgeLunLun(i)
    # ルンルン数判定
    if val > 0:
      i += 1
      cnt += 1
      if cnt == K:
        break
    else:
      i = next
    
  print(val)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

for i in range(N):
    a = q.popleft()
    d = a % 10
    if d > 0:
        q.append(10*a + d - 1)
    q.append(10*a + d)
    if d < 9:
        q.append(10*a + d + 1)

print(a)

Submission status: Accepted

Solution code:
from collections import deque

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

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

print(x)

Submission status: Accepted

Solution code:
from collections import deque


def dump_neighbor(val):
    if(val == 0):
        return [val, val+1]
    elif(val == 9):
        return [val-1, val]
    else:
        return [val-1, val, val+1]

def dfs(d, K):
    for i in range(K):
        val = d.popleft()
        neighbors = dump_neighbor(val%10)
        for neighbor in neighbors:
            d.append(val*10 + neighbor)
    print(val)
    

if __name__ == "__main__":
    K = int(input().rstrip())
    d = deque([val for val in range(1,10)])
    dfs(d, K)

Submission status: Accepted

Solution code:
count = 9
dp = [[[str(i)] for i in range(10)] for j in range(100)]
ans = [i for i in range(1,10)]

keta = 0
while count < 10**5:
    for i in range(10):
        curr = []
        for elem in dp[keta][i]:
            top = int(elem[0])
            if top > 0:
                curr += [str(top-1) + elem]
                if top > 1:
                    ans += [int(str(top-1) + elem)]
            if top < 9:
                curr += [str(top+1) + elem]
                ans += [int(str(top+1) + elem)]
            curr += [str(top) + elem]
            if top > 0 :
                ans += [int(str(top) + elem)]
        dp[keta+1][i] = curr
        count += len(curr)
    keta += 1

ans.sort()

K = int(input())
print(ans[K-1])

Submission status: Accepted

Solution code:
from collections import deque
import sys
l = int(input())
a = deque(range(1, 10))
count = 0
while True:
	x = a.popleft()
	count += 1
	if count==l:
		print(x)
		sys.exit(0)
	mod = x%10
	if mod !=0:
		a.append(x*10 + mod -1)
	a.append(x*10 + mod)
	if mod !=9:
		a.append(x*10 + mod +1)

Submission status: Accepted

Solution code:
K=int(input())

from collections import deque
q=deque()

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

Submission status: Accepted

Solution code:
from collections import deque

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

  # 前後をチェックする再帰関数( 要素として深さも必要そう / DPのメモ化とか使えそう )
  # 
  # 生データ
  # 1桁
  # [1, 2, 3, 4, 5, 6, 7, 8, 9]
  # 2桁 
  # [10, 11, 12, 21, 22, 23,..., 98, 99]
  #
  # 1
  # 10 11 12
  #
  #          2
  # .. .. .. 21 22 23
  #
  # Point.
  #   1の木, 2の木と小さい順に自然となってる
  #   重複していない
  #
  # キューを使った方法の解説
  #
  # 初期状態
  # 1 2 3 4 5 6 7 8 9
  #
  # 遷移1
  # . 2 3 4 5 6 7 8 9 10 11 12
  #
  # 遷移2
  # . . 3 4 5 6 7 8 9 10 11 12 21 22 23
  #
  # 遷移3
  # . . . 4 5 6 7 8 9 10 11 12 21 22 23 32 33 34

  # 最初の1桁データの用意
  q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

  for _ in range(k-1):
    p = q.popleft()
    l = p % 10
    # print("l:", l)

    if l - 1 >= 0:
      new_data1 = p*10 + (l - 1)
      # print("new_data1:", new_data1)
      q.append(new_data1)
      # print("q:", q)
    
    new_data2 = p*10 + l
    # print("new_data2:", new_data2)
    q.append(new_data2)
    # print("q:", q)

    if l + 1 <= 9:
      new_data3 = p*10 + (l + 1)
      # print("new_data3:", new_data3)
      q.append(new_data3)
      # print("q:", q)

  print(q[0])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    k = int(readline())
    if k < 10:
        print(k)
    else:
        ls_r = [str(i) for i in range(1, 10)]
        ls_z = ["0"]
        t = 9
        while True:
            t_ls_r = []
            t_ls_z = []
            for v in ls_r + ls_z:
                top = int(v[0])
                for i in range(max(0, top - 1), min(10, top + 2)):
                    if i == 0:
                        t_ls_z.append("".join([str(i)] + list(str(v))))
                    else:
                        t_ls_r.append("".join([str(i)] + list(str(v))))
            if len(t_ls_r) + t >= k:
                t_ls_r.sort()
                print(t_ls_r[k - t - 1])
                exit()
            else:
                ls_r = t_ls_r
                ls_z = t_ls_z
                t += len(t_ls_r)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque

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

  # 前後をチェックする再帰関数( 要素として深さも必要そう / DPのメモ化とか使えそう )
  # 
  # 生データ
  # 1桁
  # [1, 2, 3, 4, 5, 6, 7, 8, 9]
  # 2桁 
  # [10, 11, 12, 21, 22, 23,..., 98, 99]
  #
  # 1
  # 10 11 12
  #
  #          2
  # .. .. .. 21 22 23
  #
  # Point.
  #   1の木, 2の木と小さい順に自然となってる
  #   重複していない
  #
  # キューを使った方法の解説
  #
  # 初期状態
  # 1 2 3 4 5 6 7 8 9
  #
  # 遷移1
  # . 2 3 4 5 6 7 8 9 10 11 12
  #
  # 遷移2
  # . . 3 4 5 6 7 8 9 10 11 12 21 22 23
  #
  # 遷移3
  # . . . 4 5 6 7 8 9 10 11 12 21 22 23 32 33 34

  # 最初の1桁データの用意
  q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

  for _ in range(k-1):
    p = q.popleft()
    l = p % 10
    # print("l:", l)

    if l - 1 >= 0:
      new_data1 = int(str(p) + str(l - 1))
      # print("new_data1:", new_data1)
      q.append(new_data1)
      # print("q:", q)
    
    new_data2 = int(str(p) + str(l))
    # print("new_data2:", new_data2)
    q.append(new_data2)
    # print("q:", q)

    if l + 1 <= 9:
      new_data3 = int(str(p) + str(l + 1))
      # print("new_data3:", new_data3)
      q.append(new_data3)
      # print("q:", q)

  # print("===============")
  print(q[0])
  # print("===============")

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
K = int(input())

lun = list(range(0, 10)) + [0] * (K - 9 + 2) # lun[0]はダミー

k = 9
i = 1
while k < K:
    next = lun[i]
    dig = next % 10
    if dig > 0:
        k += 1
        lun[k] = next * 10 + dig - 1
    k += 1
    lun[k] = next * 10 + dig
    if dig < 9:
        k += 1
        lun[k] = next * 10 + dig + 1
    i += 1

print(lun[K])

Submission status: Accepted

Solution code:
from collections import deque

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

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

print(lun.popleft())

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

res = []
q = list(range(1,10))
while len(q)>0:
    a = q.pop()
    res.append(a)
    if a<4*10**10:
        d = a%10
        if d>0:
            q.append(10*a+d-1)
        q.append(10*a+d)
        if d<9:
            q.append(10*a+d+1)

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

Submission status: Accepted

Solution code:
K = int(input())

lun = list(range(0, 10)) + [0] * (K - 9 + 2) # lun[0]はダミー
k = 10

for i in range(1, K):
    if k > K: break
    next = lun[i]
    dig = next % 10  # 1の位
    if dig == 0: # 次の桁は0か1
        lun[k] = next * 10
        lun[k + 1] = next * 10 + 1
        k += 2
    elif dig == 9: # 次の桁は8か9
        lun[k] = next * 10 + 8
        lun[k + 1] = next * 10 + 9
        k += 2
    else:  # 次の桁はdig-1かdigかdig+1
        lun[k] = next * 10 + dig - 1
        lun[k + 1] = next * 10 + dig
        lun[k + 2] = next * 10 + dig + 1
        k += 3

print(lun[K])

Submission status: Accepted

Solution code:
from collections import deque

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

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

Submission status: Accepted

Solution code:
from copy import deepcopy
k = int(input())

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

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

prev_lun = deepcopy(lun)

while True:
    size = len(lun)
    for pl in prev_lun:
        for i in [-1, 0, 1]:
            d = pl%10 + i
            if 0 <= d <= 9:
                lun.append(pl*10 + d)
            if len(lun) == k:
                # print(lun)
                print(lun[k-1])
                exit()
                
    prev_lun = deepcopy(lun[size:])

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

K = iin()

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

cnt = 0
D = [-1,0,1]
while True:
    cnt += 1
    a = A.popleft()
    if cnt == K: 
        print(a)
        break
    t = (a % 10)
    for d in D:
        n = t+d
        if 0 <= n <= 9:
            A.append(a*10+n)

Submission status: Accepted

Solution code:
k=int(input())
s=9
l=[1,2,3,4,5,6,7,8,9]
n=0
while s<10**5+1:
  t=l[n]
  z=int(str(t)[-1])
  if z>0:  
    l.append(t*10+z-1)
    s+=1
  l.append(t*10+z)
  s+=1
  if z<9:
    l.append(t*10+z+1)
    s+=1
  n+=1
l.sort()
print(l[k-1])

Submission status: Accepted

Solution code:
k = int(input())

l = [i for i in range(1,10)]
for i in range(k):
    if l[i]%10 != 0:
        l.append(10*l[i]+l[i]%10-1)
    l.append(10*l[i]+l[i]%10)
    if l[i]%10 != 9:
        l.append(10*l[i]+l[i]%10+1)
print(l[k-1])

Submission status: Accepted

Solution code:
import queue

k = int(input())

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

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

Submission status: Accepted

Solution code:
import queue
k = int(input())
q = [1,2,3,4,5,6,7,8,9]
qq = queue.Queue()
for i in range(1,10):
	qq.put(i)

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

Submission status: Accepted

Solution code:
import queue
K = int(input())
q = queue.Queue()
count = 0
for i in range(1,10):
  q.put(str(i))
while count < K:
  tmp = q.get()
  count += 1
  if count == K:
    print(tmp)
    break
  if tmp[-1] == '0':
    for k in ['0', '1']:
      q.put(tmp + k)
  elif tmp[-1] == '9':
    for t in ['8', '9']:
      q.put(tmp + t)
  else:
    for c in [str(int(tmp[-1]) - 1),tmp[-1], str(int(tmp[-1]) + 1)]:
      q.put(tmp + c)

Submission status: Accepted

Solution code:
import queue
K = int(input())
q = queue.Queue()
count = 0
for i in range(1,10):
  q.put(str(i))
while count < K:
  tmp = q.get()
  count += 1
  if count == K:
    print(tmp)
    break
  if tmp[-1] == '0':
    for add in ['0', '1']:
      q.put(tmp + add)
  elif tmp[-1] == '9':
    for add in ['8', '9']:
      q.put(tmp + add)
  else:
    for add in [str(int(tmp[-1]) - 1),tmp[-1], str(int(tmp[-1]) + 1)]:
      q.put(tmp + add)

Submission status: Accepted

Solution code:
X = int(input())
A = []
Amod = 0
j = 0
for i in range(1,10):
    A.append(i)
k=8
if X > 9:
    while(1):
        Amod = A[j]%10
        if Amod == 0:
            A.append(A[j]*10+0)
            A.append(A[j]*10+1)
            k+=2
        elif Amod == 9:
            A.append(A[j]*10+8)
            A.append(A[j]*10+9)
            k+=2
        else:
            A.append(A[j]*10+Amod-1)
            A.append(A[j]*10+Amod)
            A.append(A[j]*10+Amod+1)
            k+=3
        if X <=k:
            break
        j+=1
print(A[X-1])

Submission status: Accepted

Solution code:
import queue

K = int(input())

q = queue.Queue()

counter = 0
for i in range(1, 10):
    q.put(str(i))
    counter += 1
    if counter == K:
        print(i)
        break

while counter < K:
    n = q.get()
    if n[-1] == '0':
        for add in ['0', '1']:
            n_add = n + add
            q.put(n_add)
            counter += 1
            if counter == K:
                print(int(n_add))
                break
    elif n[-1] == '9':
        for add in ['8', '9']:
            n_add = n + add
            q.put(n_add)
            counter += 1
            if counter == K:
                print(n_add)
                break
    else:
        for add in [str(int(n[-1])-1), str(int(n[-1])), str(int(n[-1])+1)]:
            n_add = n + add
            q.put(n_add)
            counter += 1
            if counter == K:
                print(n_add)
                break

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())

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

k = 1
while c < n:
    k = q.popleft()
    # print(k)
    if k%10:
        q.append(10*k + k%10 - 1)
    q.append(10 * k + k % 10)
    if k%10 != 9:
        q.append(10*k + (k%10) + 1)
    c += 1

print(k)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def is_lunlun(n):
    m = str(n)
    for i in range(1,len(m)):
        if abs(int(m[i]) - int(m[i-1])) > 1:
            return False
    return True

def main():
    K = int(input())
    A = [format(str(i),"0>5") for i in range(100000) if is_lunlun(i)]
    B = [int(a1+a2) for a1 in A for a2 in A if int(a1+a2) < 3234566668 and is_lunlun(int(a1+a2))]
    B2 = sorted(set(B))
    print(B2[K])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
from collections import deque
k=deque([])
z=9
m=0
if n<10:
    print(n)
    exit()
for i in range(1,10):
    k.append(i)
while z!=n:
    m=k.popleft()
    if m%10!=0:
        ans=10*m+(m%10)-1
        k.append(ans)
        z+=1
        if z==n:
            print(ans)
            exit()
    ans=10*m+(m%10)    
    k.append(ans)
    z+=1
    if z==n:
        print(ans)
        exit()
    if m%10!=9:
        ans=10*m+(m%10)+1
        k.append(ans)
        z+=1
        if z==n:
            print(ans)
            exit()

Submission status: Accepted

Solution code:
ans = set()
def f(x):
    if len(x) <= 10:
        ans.add(int(x))
        if int(x[-1]) == 0:
            f(x + "1")
            f(x + x[-1])
        elif int(x[-1]) == 9:
            f(x + "8")
            f(x + x[-1])
        else:
            u = str(int(x[-1]) + 1)
            d = str(int(x[-1]) - 1)
            f(x + u)
            f(x + d)
            f(x + x[-1])
for i in range(1,10):
    f(str(i))
ans = list(ans)
ans.sort()
#print(len(ans))
k = int(input())
print(ans[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(K):
    x = q.popleft()
    if x%10 != 0:
        q.append(x*10+x%10-1)
    q.append(x*10+x%10)
    if x%10 != 9:
        q.append(x*10+x%10+1)
    if i == K-1:
        print (x)

Submission status: Accepted

Solution code:
def create_mapper():
	# 1 -> [0,1,2]
	# 2 -> [1,2,3]
	# 3 -> [2,3,4]
	# 4 -> [3,4,5]
	# ...
	# 8 -> [7,8,9]
	# 9 -> [8,9]
	# 0 -> [0,1]
	res = [[]]*10
	for i in range(0, 10):
		if 1 <= i <= 8:
			res[i] = [i-1, i, i+1]
		elif i == 9:
			res[i] = [8, 9]
		elif i == 0:
			res[i] = [0, 1]
	return res
mapper = create_mapper()

def map_list(lst, level):
	res = lst[::1]
	while not all([len(elem) == level for elem in res]):
		new_res = []
		for elem in res:
			if len(elem) < level:
				tmp = []
				for digit in mapper[int(elem[-1])]:
					tmp.append(elem + str(digit))
				new_res += tmp
				# print(tmp)
		res = new_res[::1]
		# print(res)
		# break
	return res

def create_lun():
	res = [i for i in range(1, 10)]
	# max_num = lunlun digit 100000 == 3234566667 <- constraint
	for depth in range(2, 11): # 2 digit to 10 digit
		tmp = [str(i) for i in range(1, 10)] # start with depth = 2
		tmp = map_list(tmp, depth)
		tmp = sorted(list(map(int, tmp)))
		res += tmp
		# print(tmp)
	# print(res[100000-1] == 3234566667)
	return res
table = create_lun()
k = int(input())
print(table[k-1])

Submission status: Accepted

Solution code:
from collections import deque

def make_lunlun():
    lst = []
    que = deque([1,2,3,4,5,6,7,8,9])
    for i in range(100000):
        str_num = str(que.popleft())
        str_one = str_num[-1]
        a = str(int(str_one) - 1)
        b = str(int(str_one) + 1)
        #minus = int(str_num + a)
        same = int(str_num + str_one)
        #plus = int(str_num + b)
        if 0 < int(str_one) < 9:
            minus = int(str_num + a)
            plus = int(str_num + b)
            que.extend([minus,same,plus])
            lst.extend([minus,same,plus])
        elif int(str_one) == 0:
            plus = int(str_num + b)
            que.extend([same,plus])
            lst.extend([same,plus])
        else:
            minus = int(str_num + a)
            que.extend([minus,same])
            lst.extend([minus,same])
    print(lst[K - 10])    

K = int(input())
if K <= 12:
    print(K)
else:
    make_lunlun()

Submission status: Accepted

Solution code:
k=int(input())
from collections import deque
lunlun=deque([i for i in range(1,10)])
for i in range(10**5):
  a=lunlun.popleft()
  if not a%10==0:
    lunlun.append(a*10+a%10-1)
  lunlun.append(a*10+a%10)
  if not a%10==9:
    lunlun.append(a*10+a%10+1)
  if i==k-1:
    break

print(a)

Submission status: Accepted

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

k = int(input())
lun = {1, 2, 3, 4, 5, 6, 7, 8, 9}
temp = set()
while len(lun) < k:
    for i in lun:
        last = int(str(i)[-1])
        for j in last_number(last):
            temp.add(int(str(i) + str(j)))
    lun.update(temp)
    temp = set()
answer = sorted(list(lun))
print(answer[k - 1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
cand = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
temp = []
for i in range(k):
    t = cand.popleft()
    temp.append(t)
    if t % 10 != 0:
        cand.append(t*10+(t%10-1))
    cand.append(t*10+(t%10))
    if t % 10 != 9:
        cand.append(t*10+(t%10+1))
print(temp[k-1])

Submission status: Accepted

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

q = queue.Queue()
[q.put(i) for i in range(1, 10)]
for _ in range(K):
    num = q.get()
    mod = num % 10
    deca = num * 10 + mod 
    if mod != 0:
        q.put(deca - 1)
    q.put(deca)
    if mod != 9:
        q.put(deca + 1)
        
print(num)