結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2020-12-21 06:37:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 58 ms / 5,000 ms |
コード長 | 1,302 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 81,536 KB |
実行使用メモリ | 65,592 KB |
最終ジャッジ日時 | 2024-07-01 10:01:18 |
合計ジャッジ時間 | 2,849 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import sys from collections import deque sys.setrecursionlimit(10**7) def I(): return int(sys.stdin.readline().rstrip()) def MI(): return map(int,sys.stdin.readline().rstrip().split()) def LI(): return list(map(int,sys.stdin.readline().rstrip().split())) def LI2(): return list(map(int,sys.stdin.readline().rstrip())) def S(): return sys.stdin.readline().rstrip() def LS(): return list(sys.stdin.readline().rstrip().split()) def LS2(): return list(sys.stdin.readline().rstrip()) def popcount(n): c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555) c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333) c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f) c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff) c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff) c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff) return c N = I() P = [popcount(i) for i in range(N+1)] inf = 10**18 dist = [inf]*(N+1) dist[1] = 1 deq = deque([1]) while deq: i = deq.pop() j,k = i+P[i],i-P[i] if j <= N and dist[j] == inf: dist[j] = dist[i]+1 deq.appendleft(j) if k > 0 and dist[k] == inf: dist[k] = dist[i]+1 deq.appendleft(k) ans = dist[-1] print(ans if ans != inf else -1)