結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2023-12-09 21:17:50 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 103 ms / 5,000 ms |
コード長 | 1,197 bytes |
コンパイル時間 | 132 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-09-27 03:45:38 |
合計ジャッジ時間 | 3,035 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
from collections import deque def bit(n): cnt=0 while n: cnt+=n%2 n=n//2 return cnt def main(): N=int(input()) adj=[[] for i in range(N+1)] flag=[False]*(N+1) flag[1]=True queue=deque() queuelen=1 deeepnessArray=[0 for i in range(N+1)] deeepnessArray[1]=1 solved=False queue.appendleft(1) result=[] for i in range(N+1): if N >= i+bit(i) and i+bit(i)>0: adj[i].append(i+bit(i)) if N>=i-bit(i) and i-bit(i)>0: adj[i].append(i-bit(i)) #print(adj) if N==1: print(1) else: while queuelen!=0 and not solved: v=queue.pop() queuelen-=1 for u in adj[v]: if u == N: solved=True if flag[u]==False: flag[u]=True queue.appendleft(u) queuelen+=1 #print(u,"を発見",deepness) deeepnessArray[u]=deeepnessArray[v]+1 #print(deeepnessArray) if solved: print(deeepnessArray[N]) else: print(-1) main()