#349271 (Python3) No.3 ビットすごろく

• 問題: No.3 ビットすごろく
• ユーザー: maburoe
• 提出日時: 2019-05-28 13:39:21
• 言語: Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
• 結果: WA
• 実行時間: -
• コード長: 584 bytes
• コンパイル時間: 93 ms
• コンパイル使用メモリ: 11,896 KB
• 実行使用メモリ: 10,508 KB
• 最終ジャッジ日時: 2023-10-17 18:23:06
• 合計ジャッジ時間: 2,763 ms
• ジャッジサーバーID （参考情報）: judge14 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	31 ms; 10,100 KB
testcase_01	AC	30 ms; 10,100 KB
testcase_02	AC	27 ms; 10,100 KB
testcase_03	AC	31 ms; 10,300 KB
testcase_04	AC	28 ms; 10,140 KB
testcase_05	AC	34 ms; 10,412 KB
testcase_06	AC	31 ms; 10,304 KB
testcase_07	AC	30 ms; 10,160 KB
testcase_08	WA	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	AC	33 ms; 10,408 KB
testcase_13	AC	30 ms; 10,284 KB
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	AC	29 ms; 10,164 KB
testcase_19	RE	-
testcase_20	WA	-
testcase_21	AC	27 ms; 10,100 KB
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	AC	28 ms; 10,100 KB
testcase_27	WA	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	WA	-
testcase_31	AC	29 ms; 10,100 KB
testcase_32	RE	-

ソースコード

goal = int(input())

# goal_1bit_num = bin(goal)
# print(goal_1bit_num.count('1'))

stepped = set()
maybe_answers = set()


def step(position, count):
    if position in stepped:
        return
    else:
        stepped.add(position)

    if position not in range(1, goal + 1):
        return

    if position == goal:
        maybe_answers.add(count)
        return

    bit1_num = bin(position).count('1')
    step(position + bit1_num, count + 1)
    step(position - bit1_num, count + 1)


step(1, 1)

if len(maybe_answers) == 0:
    print('-1')
else:
    print(min(maybe_answers))