Problem:


Score : 400 points

Problem Statement

A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:

In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1.

For example, 1234, 1, and 334 are lunlun numbers, while none of 31415, 119, or 13579 is.

You are given a positive integer K. Find the K-th smallest lunlun number.

Constraints

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer.

Sample Input 1

15

Sample Output 1

23

We will list the 15 smallest lunlun numbers in ascending order:

1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
21,
22,
23.

Thus, the answer is 23.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

13

Sample Output 3

21

Sample Input 4

100000

Sample Output 4

3234566667

Note that the answer may not fit into the 32-bit signed integer type.



Sample input:
15


Sample output:
23

Submission status: Accepted

Solution code:
k = int(input())
if k<=9:
    print(k)
    exit(0)

dp = [[1]*10]
counts = [0,9]
digit = 0

while counts[-1] < k:
    digit += 1
    d = [0]*10
    d[0] = dp[-1][0] + dp[-1][1]
    for i in range(1,9):
        d[i] = dp[-1][i-1] + dp[-1][i] + dp[-1][i+1]
    d[9] = dp[-1][8] + dp[-1][9]
    dp.append(d)
    count = counts[-1]
    for i in range(1,10):
        count += d[i]
        if count >= k:
            leading = i
            print(leading, end="")
            count -= d[i]
            k -= count
            break
    counts.append(count)

digit -= 1

while digit>=0:
    d = dp[digit]
    if leading == 0:
        r = range(0,2)
    elif leading == 9:
        r = range(8,10)
    else:
        r = range(leading-1,leading+2)
    count = 0
    for i in r:
        count += d[i]
        if count >= k:
            leading = i
            print(leading, end="")
            count -= d[i]
            k -= count
            digit -= 1
            break
print("")

Submission status: Accepted

Solution code:
import collections

k = int(input())
time = 1

q = collections.deque()

q.extend([1,2,3,4,5,6,7,8,9])

while(time <= k):

    i = q.popleft()
    #print(i)
    time += 1

    #0じゃないなら
    if i % 10 != 0:
        q.append(i*10 + i%10 - 1)

    #それ以外
    q.append(i*10 + i%10)

    #9じゃないなら
    if i % 10 != 9:
        q.append(i*10 + i%10 + 1)

print(i)

Submission status: Accepted

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

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

while(flg != 1):
    ans = q.popleft()
    cnt += 1

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

    if cnt == k:
        print(ans)
        flg = 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()
    amari = x%10
    if amari == 0:
        l, m = 10*x, 10*x+1
        q.append(l)
        q.append(m)
    elif amari == 1:
        l, m, r = x*10, x*10+1, x*10+2
        q.append(l)
        q.append(m)
        q.append(r)
    elif amari == 9:
        l, m = 10*x+8, 10*x+9
        q.append(l)
        q.append(m)
    else:
        l, m, r = 10*x+(amari-1), 10*x+(amari), 10*x+(amari+1)
        q.append(l)
        q.append(m)
        q.append(r)

print(x)

Submission status: Accepted

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

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


def generate_lunlun(x):
    y = x % 10
    if 0 <= y-1:
        yield 10*x + y-1
    yield 10*x + y
    if y+1 < 10:
        yield 10*x + y+1


cnt = 0
while True:
    x = ans.popleft()
    for i in generate_lunlun(x):
        ans.append(i)
    cnt += 1
    if cnt == k:
        print(x)
        break

Submission status: Accepted

Solution code:
K=int(input())
lst=[1]
qqq=0
for i in range(K-1):
    if qqq==len(lst)-1:
        if lst[qqq]<9:
            lst[qqq]+=1
            for j in range(qqq-1,-1,-1):
                lst[j]=max(0,lst[j+1]-1)
            qqq=0
        else:
            lst=[0]*len(lst)+[1]
            qqq=0
    else:
        while qqq<len(lst)-1:
            if lst[qqq]<=lst[qqq+1] and lst[qqq]<9:
                break
            qqq+=1
        if qqq==len(lst)-1 and lst[qqq]==9:
            lst=[0]*len(lst)+[1]
            qqq=0
        else:
            lst[qqq]+=1
            for j in range(qqq-1,-1,-1):
                lst[j]=max(0,lst[j+1]-1)
            qqq=0
lst=list(map(str,lst[::-1]))
print("".join(lst))

Submission status: Accepted

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

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

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

print(x)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    K = int(input())
    queue = deque([i + 1 for i in range(9)])
    cnt = 1

    if K < 13:
        print(K)
        return

    while cnt < K:
        cnt += 1
        x = queue.popleft()
        r = x % 10

        if r != 0:
            queue.append(x*10 + r - 1)
        queue.append(x*10 + r)
        if r != 9:
            queue.append(x*10 + r + 1)

    print(queue.popleft())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#D
from collections import deque
import sys
k=int(input())
que = deque()
count=0
for i in range(1, 10):  #1~9まで
    que.append(i)
    count += 1
    if count == k:
        print(que.pop())
        sys.exit()
# print(que)
# print(count)
while True:
    tmp = que.popleft()  #データを左から取り出す
    tmp = tmp * 10 + tmp % 10  #中心整数を求める 中心整数＋下一桁
    if tmp % 10 != 0:  #下一桁目が0でない場合
        que.append(tmp- 1)
        count += 1
        # print(count)
        if count == k:
            break
    que.append(tmp)
    count += 1
    # print(count)
    if count == k:
        break
    if tmp % 10 != 9:
        que.append(tmp + 1)
        count += 1
        # print(count)
        if count == k:
            break
    # print(que)
print(que.pop())

Submission status: Accepted

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


def generate_lunlun(x):
    y = x % 10
    if 0 <= y-1:
        yield 10*x + y-1
    yield 10*x + y
    if y+1 < 10:
        yield 10*x + y+1


idx = 0
while len(ans) < k:
    x = ans[idx]
    for i in generate_lunlun(x):
        ans.append(i)
    idx += 1

print(ans[k-1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
k = int(input())

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


def generate_lunlun(x):
    mod = x % 10

    if mod - 1 >= 0:
        yield x*10 + mod-1

    yield x*10 + mod

    if mod + 1 <= 9:
        yield x*10 + mod + 1


p = 0

while len(lunlun) < k:
    for i in generate_lunlun(lunlun[p]):
        lunlun.append(i)

    p += 1

print(lunlun[k-1])

Submission status: Accepted

Solution code:
import queue

K = int(input())

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

result = 0
while count != K:
    tmp = q.get()  # 先頭のキューを取り出す
    keta1 = tmp % 10  # 1の位を取得
    for i in range(-1, 2):
        if keta1 == 0 and i == -1:  # 1の位が0のとき
            continue
        if keta1 == 9 and i == 1:  # 1の位が9のとき
            continue
        result = tmp * 10 + (keta1 + i)
        q.put(result)  # 最後に付け足す
        count += 1
        if count == K:
            print(result)
            break
        else:
            continue

Submission status: Accepted

Solution code:
from collections import deque
def solve():
    K = int(input())
    q = deque(list(range(1,10)))
    cnt = 0

    tmp = 0
    while cnt < K:
        tmp = q.popleft()
        cnt += 1

        ones_place = tmp % 10
        if ones_place != 0:
            q.append(tmp*10+ones_place-1)
        q.append(tmp*10+ones_place)
        if ones_place != 9:
            q.append(tmp*10+ones_place+1)
    
    print(tmp)
        
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

def lunlun():
    cnt=0
    while True:
        now = stack.popleft()
        cnt += 1
        if cnt == k: return now
        s = str(now)
        for i in range(-1,2):
            temp=int(s[-1]) + i 
            if temp>=0 and temp<10: 
                temp1=int(s + str(temp))
                stack.append(temp1)
print(lunlun())

Submission status: Accepted

Solution code:
import sys

k = int(sys.stdin.readline().rstrip())

def main(k):
    if k <= 9:
        print(k)
        return
    res = list(range(1, 10))
    k -= 9
    while True:
        nex = []
        for n in res:
            r = n % 10
            n *= 10
            for i in range(-1, 2):
                if 0 <= r + i <= 9:
                    nex.append(n + r + i)
                    k -= 1
                    if not k:
                        print(nex[-1])
                        return
        res = nex.copy()

if __name__ == '__main__':
    main(k)

Submission status: Accepted

Solution code:
import queue

K = int(input())
q = queue.Queue()

for i in range(1, 10):
    q.put(i)
v = 0
for i in range(K):
    v = q.get()
    m = v%10
    if m != 0:
        q.put(10*v+m-1)
    q.put(v*10+m)
    if m != 9:
        q.put(10*v+m+1)
print(v)

Submission status: Accepted

Solution code:
a = []

def dfs(x):
    if x > 3234566667:
        return
    a.append(x)
    for i in range(10):
        if abs(x%10-i) <= 1:
            dfs(x*10+i)

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

Submission status: Accepted

Solution code:
k = int(input())

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

def gen_runrun(x):
    a = x % 10
    if a in [1,2,3,4,5,6,7,8]:
        runrun.append(x * 10 + a - 1)
        runrun.append(x * 10 + a )
        runrun.append(x * 10 + a + 1)
    elif a == 0:
        runrun.append(x * 10 + a )
        runrun.append(x * 10 + a + 1)
    elif a == 9:
        runrun.append(x * 10 + a - 1)
        runrun.append(x * 10 + a )

i = 0
while len(runrun) < k + 10:
    gen_runrun(runrun[i])
    i += 1

print(runrun[k - 1])

Submission status: Accepted

Solution code:
k = int(input())
lunlun = [1, 2, 3, 4, 5, 6, 7, 8, 9] #ルンルン数リスト

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

Submission status: Accepted

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

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

c = 0
while len(que):
    x = que.popleft()
    c += 1
    for m in range(max(0, x % 10 - 1), min(9, x % 10 + 1) + 1):
        que.append(10*x+m)
    
    if c == K:
        print(x)
        break

Submission status: Accepted

Solution code:
import queue

# ['1', '0'] => 10 関数 
def strtoNum(l):
    val = ''
    for _ in l:
        val += _
    return int(val)

# 入力
k = int(input())

# k < 10だけ別対応しておく
if k < 10:
    print(k)
    exit()

# ルンルン数を管理するキュー
lun = queue.Queue()
# 初期値として1~9を入れておく
for i in range(1, 10):
    lun.put(i)

# 10からスタートなので、既にルンルンカウントを9にしておく
cnt = 9
# 0~
apdNum = [[0,1],[0,1,2],[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9]]

while not lun.empty():
    # dequeueした数を取得
    getNum = list(str(lun.get()))
    # 一番最後の桁だけを確認する
    chkNum = int(getNum[len(getNum)-1])
    for i in apdNum[chkNum]:
        cnt += 1
        putNum = getNum + [str(i)]
        if cnt == k:
            print(strtoNum(putNum))
            exit()
        else:
            lun.put(strtoNum(putNum))

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
lunlun = []
q = deque([1,2,3,4,5,6,7,8,9])
while len(lunlun) <= k:
    first = q.popleft()
    lunlun.append(first)
    if first%10-1 >= 0:
        q.append(first*10 + (first%10-1))
    q.append(first*10 + first%10)
    if first%10+1 <= 9:
        q.append(10*first + (first%10+1))
print(lunlun[k-1])

Submission status: Accepted

Solution code:
def dfs(s):
    d=len(s)
    if d>10:
        return
    
    if s!='':
        if s[0]!='0':
            num.add(int(s))

    for c in '0123456789':
        if s=='':
            dfs(s+c)
        else:
            if abs(int(s[-1])-int(c))<=1:
                dfs(s+c)

k=int(input())
num=set()

dfs('')
ans=list(num)
ans.sort()
print(ans[k-1])

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def main():
    K = int(input())
    q = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    heapq.heapify(q)
    while len(q) < K:
        K -= len(q)
        new_q = []
        for i in q:
            d1 = i % 10
            if d1 > 0:
                new_q.append(i * 10 + d1 - 1)
            new_q.append(i * 10 + d1)
            if d1 < 9:
                new_q.append(i * 10 + d1 + 1)
        q = new_q
        heapq.heapify(q)
    print(q[K-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from string import digits

k = int(sys.stdin.readline().rstrip())

def main():
    if k <= 9:
        print(k)
        return
    res = list(digits[1:])
    r = k - 9
    nex = []
    while True:
        for n in res:
            o = ord(n[-1])
            for i in range(-1, 2):
                d = chr(o + i)
                if d < '0' or d > '9': continue
                nex.append(n + d)
                r -= 1
                if not r:
                    print(nex[-1])
                    return
        res = nex.copy()
        nex.clear()

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from string import digits

k = int(sys.stdin.readline().rstrip())

def main():
    if k <= 9:
        print(k)
        return
    res = list(digits[1:])
    r = k - 9
    while True:
        nex = []
        for n in res:
            o = ord(n[-1])
            for i in range(-1, 2):
                d = chr(o + i)
                if d < '0' or d > '9': continue
                nex.append(n + d)
                r -= 1
                if not r:
                    print(nex[-1])
                    return
        res = nex.copy()    

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def main():
    K = int(input())
    q = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    heapq.heapify(q)
    while len(q) < K:
        K -= len(q)
        new_q = []
        for i in q:
            d1 = int(str(i)[-1])
            if d1 > 0:
                new_q.append(i * 10 + d1 - 1)
            new_q.append(i * 10 + d1)
            if d1 < 9:
                new_q.append(i * 10 + d1 + 1)
        q = new_q
        heapq.heapify(q)
    print(q[K-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from string import digits

k = int(sys.stdin.readline().rstrip())

def main():
    r = k
    if r <= 9:
        print(digits[r])
        return
    res = list(digits[1:])
    r -= 9
    while True:
        nex = []
        for n in res:
            o = ord(n[-1])
            for i in range(-1, 2):
                d = chr(o+i)
                if d < '0' or d > '9': continue
                nex.append(n + d)
                r -= 1
                if r == 0:
                    print(nex[-1])
                    return
        res = nex.copy()    

if __name__ ==  '__main__':
    main()

Submission status: Accepted

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

while len(a)<K:
  temp=set()
  for now in prev:
    c=now%10
    if c==0:
      temp.add(now*10)
      temp.add(now*10+1)
    elif c==9:
      temp.add(now*10+9)
      temp.add(now*10+8)
    else:
      temp.add(now*10+c-1)
      temp.add(now*10+c)
      temp.add(now*10+c+1)
  prev=temp
  a=a|temp
print(sorted(list(a))[K-1])

Submission status: Accepted

Solution code:
import sys
from string import digits

k = int(sys.stdin.readline().rstrip())

def main():
    r = k
    if r <= 9:
        print(digits[r])
        return
    res = list(digits[1:])
    r -= 9
    while True:
        nex = []
        for n in res:
            o = ord(n[-1])
            for i in range(-1, 2):
                tail = chr(o+i)
                if tail < '0' or tail > '9': continue
                nex.append(n+tail)
                r -= 1
                if r == 0:
                    print(nex[-1])
                    return
        res = nex.copy()    

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

k = ni()
runrun = k
ans = 0


class Node(object):
    def __init__(self, nam ):
        self.nam = nam
        if nam == -1:
            ne = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        else:
            nam_digit= nam%10
            nam=nam*10+nam_digit
            ne = [nam - 1, nam, nam + 1]
            if nam_digit == 0:
                ne = [nam, nam+1]
            elif nam_digit == 9:
                ne = [nam-1, nam]
        self.nextlist = ne
        self.nextc = -1
        self.j = False


node = Node(-1)
queue = collections.deque()
j=False
while runrun is not 0:
    queue.extend(node.nextlist)
    nx_nam = queue.popleft()
    node = Node(nx_nam)
    runrun -= 1
ans = node.nam

print("{}".format(ans))

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)


def solve(K: int):
    def _make(s, idx):
        if idx > 0:
            if s[idx] == '9':
                return None
            prev = int(s[idx - 1])
            cur  = int(s[idx]) + 1
            if abs(prev - cur) > 1:
                return None
        if idx == 0 and s[idx] == '9':
            return '1' + ('0' * len(s))

        ret = s[:idx]
        ret += str(int(s[idx]) + 1)
        for _ in s[idx + 1:]:
            ret += str(max(0, int(ret[-1]) - 1))
        return ret

    def get_next(s):
        idx = 0
        l = len(s)
        for idx in range(l)[::-1]:
            tmp = _make(s, idx)
            if tmp is not None:
                return tmp
        return None

    val = '0'
    for i in range(K):
        val = get_next(val)
    print(val)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K = int(input())

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

lst = [[1] * 11 for _ in range(2)]
lst_append = lst.append
lst[0][10] = 0
lst[1][0] = 0
lst[1][10] = 0

now = 9
p = 0
flag = 0
while True:
    if p == 0:
        lst[flag + 1][0] = lst[flag][0] + lst[flag][1]
        p += 1
        continue
    tmp = lst[flag][p - 1] + lst[flag][p] + lst[flag][p + 1]
    lst[flag + 1][p] = tmp
    if now + tmp >= K:
        break
    now += tmp
    p += 1

    if p == 10:
        p = 0
        flag += 1
        lst_append([0] * 11)

# print ('now', now)
# print ('p', p)
# print ('flag', flag)
# print (lst[0])
# print (lst[1])

#先頭がpでかつ現在地がnow
ans = str(p)
flag += 1
while True:
    if flag == 0:
        break
    # print (p)
    if p >= 1 and K <= now + lst[flag - 1][p - 1]:
        flag -= 1
        ans += str(p - 1)
        p -= 1
    elif K <= now + lst[flag - 1][p - 1] + lst[flag - 1][p]:
        now += lst[flag - 1][p - 1]
        flag -= 1
        ans += str(p)
    else:
        now += lst[flag - 1][p - 1] + lst[flag - 1][p]
        flag -= 1
        ans += str(p + 1)
        p += 1

print (ans)

# for tmp in lst:
#     print (tmp)

Submission status: Accepted

Solution code:
import heapq

K =int(input())

pque = []
for i in range(1, 10):
    heapq.heappush(pque, i)

for i in range(K):
    tmp = heapq.heappop(pque)
    if tmp % 10 == 0:
        heapq.heappush(pque, tmp * 10)
        heapq.heappush(pque, tmp * 10 + 1)
    elif tmp % 10 == 9:
        heapq.heappush(pque, tmp * 10 + 9)
        heapq.heappush(pque, tmp * 10 + 8)
    else:
        next_ = tmp % 10
        heapq.heappush(pque, tmp * 10 + next_ - 1)
        heapq.heappush(pque, tmp * 10 + next_)
        heapq.heappush(pque, tmp * 10 + next_ + 1)

print (tmp)

Submission status: Accepted

Solution code:
import queue

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

K = int(input())
for _ in range(K):
    now_lunlun_num = q_lunlun_num.get()
    first_digit = now_lunlun_num % 10

    if first_digit != 0:
        q_lunlun_num.put(now_lunlun_num*10 + first_digit - 1)
    
    q_lunlun_num.put(now_lunlun_num*10 + first_digit)

    if first_digit != 9:
        q_lunlun_num.put(now_lunlun_num*10 + first_digit +1 )

print(now_lunlun_num)