結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2019-07-29 22:09:40 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 79 ms / 5,000 ms |
コード長 | 767 bytes |
コンパイル時間 | 88 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 13,440 KB |
最終ジャッジ日時 | 2024-07-01 09:27:03 |
合計ジャッジ時間 | 2,830 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
from collections import defaultdict, deque def bfs(start): distance = [None] + [-1] * N distance[start] = 1 queue = deque([]) queue.append(start) while len(queue) > 0: current_node = queue.popleft() for next_node in adj_dict[current_node]: if distance[next_node] == -1: distance[next_node] = distance[current_node] + 1 queue.append(next_node) return distance N = int(input()) adj_dict = defaultdict(list) for i in range(1, N): tmp = i step = 0 while tmp != 0: step += tmp % 2 tmp = tmp // 2 if 1 <= i-step: adj_dict[i].append(i-step) if i+step <= N: adj_dict[i].append(i+step) distance = bfs(1) print(distance[N])