結果

問題 No.3 ビットすごろく
ユーザー papinniepapinnie
提出日時 2019-08-06 20:05:02
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 763 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-07-18 14:20:01
合計ジャッジ時間 4,075 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
10,752 KB
testcase_01 AC 31 ms
10,880 KB
testcase_02 AC 31 ms
10,752 KB
testcase_03 AC 577 ms
10,880 KB
testcase_04 AC 31 ms
10,880 KB
testcase_05 RE -
testcase_06 AC 700 ms
11,008 KB
testcase_07 AC 31 ms
11,008 KB
testcase_08 WA -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 AC 396 ms
11,008 KB
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 AC 31 ms
11,008 KB
testcase_19 RE -
testcase_20 WA -
testcase_21 AC 30 ms
10,752 KB
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 WA -
testcase_27 WA -
testcase_28 RE -
testcase_29 RE -
testcase_30 WA -
testcase_31 AC 30 ms
10,752 KB
testcase_32 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())

def get_total(x):
    return sum(map(int,list("{0:b}".format(x))))

already = set()

def go_next(now, mv_count):
    already.add(now)
    mv_count += 1
    step = get_total(now) # 進める数
    #print("now", now, "mv_count", mv_count, "step", step)
    
    go_m = now + step  # 進む先
    if go_m == N:
        # goal
        print(mv_count)
        exit(0)
    if  go_m < N:
        go_next(go_m, mv_count)
    
    back_m = now - step # 戻る先
    if back_m not in already:
        # 行ったことのあるところなら行かない
        if back_m > 0:
            go_next(back_m, mv_count)

if N == 1:
    print(1)
else:
    # 今=1, ステップ=1で再帰スタート
    go_next(1, 1)

# 到達できなかった
print(-1)
0