結果

問題 No.3 ビットすごろく
ユーザー rarpipipi
提出日時 2023-12-31 00:47:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 70 ms / 5,000 ms
コード長 447 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 71,948 KB
最終ジャッジ日時 2024-09-27 16:56:31
合計ジャッジ時間 3,688 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #

from collections import deque
def bit_count(self):
    return bin(self).count('1')
n=int(input())
que=deque()
que.append(1)
dp=[0]*(n+1)
dp[1]=1
while que:
    now=que.popleft()
    move=bit_count(now)
    if 1<=now+move<=n and not dp[now+move]:
        dp[now+move]=dp[now]+1
        que.append(now+move)
    if 1<=now-move<=n and not dp[now-move]:
        dp[now-move]=dp[now]+1
        que.append(now-move)
    
print(dp[-1] if dp[-1] else -1)
0