結果

問題 No.3 ビットすごろく
コンテスト
ユーザー Ribura
提出日時 2020-04-29 21:03:13
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 38 ms / 5,000 ms
コード長 646 bytes
コンパイル時間 83 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-07-01 09:46:50
合計ジャッジ時間 2,174 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

n = int(readline())


def check():
    s = deque([0] * (n + 1))
    s[1] = 1
    q = deque([1])
    while q:
        v = q.popleft()
        if v == n:
            return s[v]
        bit = bin(v).count('1')
        v1 = v + bit
        v2 = v - bit
        if 0 < v1 <= n and s[v1] == 0:
            q.append(v1)
            s[v1] = s[v] + 1
        if 0 < v2 <= n and s[v2] == 0:
            q.append(v2)
            s[v2] = s[v] + 1
    return -1


print(check())
0