結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2023-02-14 22:13:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 65 ms / 5,000 ms |
コード長 | 718 bytes |
コンパイル時間 | 152 ms |
コンパイル使用メモリ | 82,336 KB |
実行使用メモリ | 73,276 KB |
最終ジャッジ日時 | 2024-07-17 09:58:52 |
合計ジャッジ時間 | 3,128 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
# 辺を張ってBFS or ダイクストラ法で間に合うか N = int(input()) edges = [[] for i in range(N+1)] for i in range(1, N): one_count = bin(i).count('1') if i+one_count <= N: edges[i].append(i+one_count) if i-one_count >= 1: edges[i].append(i-one_count) from collections import deque que = deque() que.append(1) INF = 10**10 distance = [INF]*(N+1) distance[1] = 1 while que: current = que.popleft() for nxt in edges[current]: #print('current', current, 'nxt', nxt) if distance[nxt] > distance[current]+1: distance[nxt] = distance[current]+1 que.append(nxt) if distance[N] == INF: print(-1) else: print(distance[N])