結果

問題 No.3 ビットすごろく
ユーザー piconic_X
提出日時 2016-08-13 19:50:00
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,214 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 13,640 KB
最終ジャッジ日時 2024-11-07 16:28:37
合計ジャッジ時間 6,915 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def get_bitnum(n):
    i = 0
    while n > 0:
        if n % 2 == 1:
            i += 1
        n = n // 2
    return i


def create_bitroute(N):
    bitroute = [get_bitnum(i+1) for i in range (N)]
    return bitroute


def search(bitroute, N):
    history = []
    res = []
    queue = [(0,1)]
    while queue != []:
        hd = queue.pop(0)
        pos = hd[0]
        time = hd[1]
        if pos == N-1:
            res.append(time)
        else:
            history.append(pos)
            bitnum = bitroute[pos]
            posR = pos + bitnum
            posL = pos - bitnum
            time += 1
            RB = not (posR > N-1 or posR in history)
            LB = not (posL < 1 or posL in history)
            if RB and LB:
                queue.append((posR, time))
                queue.append((posL, time))
            elif RB and not LB:
                queue.append((posR, time))
            elif LB and not RB:
                queue.append((posL, time))
            else:
                pass
    return res


def main():
    N = int(input())
    bitroute = create_bitroute(N)
    res = search(bitroute, N)
    if res == []:
        ans = -1
    else:
        ans = min(res)
    print(ans)


main()
0