結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2025-04-15 14:54:27 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 651 bytes |
コンパイル時間 | 339 ms |
コンパイル使用メモリ | 82,352 KB |
実行使用メモリ | 304,552 KB |
最終ジャッジ日時 | 2025-04-15 14:54:37 |
合計ジャッジ時間 | 9,800 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 5 TLE * 1 -- * 27 |
ソースコード
def popcount(x): binQ = bin(x)[2:] return binQ.count("1") N = int(input()) INF=float('inf') visited = [INF] * (N+1) visited[1] = 1 nxt = [[False] * (N+1) for _ in range(N+1)] nxt[0][1] = True for i in range(N): for j in range(1, N+1): if not nxt[j]: continue cnt = popcount(j) if j + cnt <= N and visited[j+cnt] > visited[j] + 1: visited[j+cnt] = min(visited[j+cnt], visited[j] + 1) nxt[i+1][j+cnt] = True if 1 <= j - cnt and visited[j-cnt] > visited[j] - 1: visited[j-cnt] = min(visited[j-cnt], visited[j] + 1) nxt[i+1][j-cnt] = True if visited[N] == INF: print(-1) else: print(visited[N])