2022.05.20

【python】ジュニア数学オリンピックの問題を力づくで解いてみる（2016年度 – 問8）

mokabuu

問題

各桁の数字に１個もダブりがない３７の倍数のうち最大値を答えよ。

僕の感想

解放が全く頭に浮かばん…。

総当たりしよう…。←

よし、プログラム書くぞ！←

実際のプログラム

文字通り総当たりして見たら、ものすごく遅かったです。笑

不安になりすぎて途中でPrintはさみました。笑

まあ、そりゃそうですよね。

欲しいのって配列の一番最後なので、それまでの計算ってぶっちゃけ無駄じゃないですか？

力づくにもほどがありました…。

ちなみに各桁にダブりがない最大値は「9876543210」になるので、必然的に解はそれ以下の数字になると思っています。

MAX_POSSIBLE_NUM = 9876543210
GIVEN_NUM = 37

valid_num = []
num = 0;

while num * GIVEN_NUM <= MAX_POSSIBLE_NUM:
    result = num * GIVEN_NUM
    str_result = str(result)

    if str_result.count("0") == 1 & str_result.count("1") == 1 & str_result.count("2") == 1 & str_result.count("3") == 1 & str_result.count("4") == 1 & str_result.count("5") == 1 & str_result.count("6") == 1 & str_result.count("7") == 1 & str_result.count("8") == 1 & str_result.count("9") == 1:
        valid_num.append(result)

    print(str_result)
    num = num + 1

print("------- Answer -------")
print(valid_num[-1])

せめて、もう少しまともな回答にするために、後ろから数字を探すことにしました。

9876543210以下が解になるため、9876543210/37した数字を起点にそれ以下の37の倍数の中から各桁にダブりのない数字を探していき、最初に見つかった数字を解とする作戦です。

依然、パワープレイですが、まだマシだと思います。

MAX_POSSIBLE_NUM = 9876543210
GIVEN_NUM = 37

num = MAX_POSSIBLE_NUM / GIVEN_NUM;

while num < 0:
    result = num * GIVEN_NUM
    str_result = str(result)

    if str_result.count("0") == 1 & str_result.count("1") == 1 & str_result.count("2") == 1 & str_result.count("3") == 1 & str_result.count("4") == 1 & str_result.count("5") == 1 & str_result.count("6") == 1 & str_result.count("7") == 1 & str_result.count("8") == 1 & str_result.count("9") == 1:
        print("------- Answer -------")
        print(str_result)
        break

    num = num - 1

こちらはサクッと実行が終わりまして「9876435012」とのことでした。正誤は不明ですが、プログラムが言うのだから間違いないと思っています。