結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2017-11-29 10:25:54 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
RE
|
実行時間 | - |
コード長 | 941 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 11,392 KB |
最終ジャッジ日時 | 2024-11-27 18:38:39 |
合計ジャッジ時間 | 4,983 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 RE * 22 |
ソースコード
N=int(input()) #Nのビット数 n_bit=0 tmp=N while(tmp!=0): n_bit+=1 tmp=int(tmp/2) # print(n_bit) #kに到達できる最小の移動数を順に調べていく(ただし-1のとき移動できないとする) move_num=[-1 for i in range(N+1)] #境界条件 move_num[0]=0 move_num[1]=1 def Update(k): # print(k) if move_num[k]==-1: return #'1'をカウント one_num=0 mask=0b1 for l in range(n_bit): if k&mask!=0: one_num+=1 mask=mask<<1 #前の更新 if move_num[k-one_num]==-1 or move_num[k-one_num]>move_num[k]+1: move_num[k-one_num]=move_num[k]+1 Update(k-one_num) #後ろの更新 if k+one_num>N: return if move_num[k+one_num]>move_num[k]+1 or move_num[k+one_num]==-1: move_num[k+one_num]=move_num[k]+1 Update(k+one_num) for i in range(1,N+1): Update(i) # print(i,move_num) print(move_num[N])