結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2021-11-01 14:30:50 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 43 ms / 5,000 ms |
コード長 | 356 bytes |
コンパイル時間 | 275 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-10-10 03:08:06 |
合計ジャッジ時間 | 2,576 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
from collections import deque N=int(input()) DP=[1<<30]*(N+1) DP[1]=1 Q=deque([1]) while Q: x=Q.popleft() b=bin(x).count("1") if x+b<=N and DP[x+b]>DP[x]+1: DP[x+b]=DP[x]+1 Q.append(x+b) if x-b<=N and DP[x-b]>DP[x]+1: DP[x-b]=DP[x]+1 Q.append(x-b) if DP[N]==1<<30: print(-1) else: print(DP[N])