【AtCoder版！蟻本】ABC085 C - Otoshidama【準備編】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210317160400p:plain
AtCoder版！蟻本の準備編で類題としてあげられているABC085 CをPythonで解いていきます。

リンク

AtCoder Beginner Contest 085 C - Otoshidama

問題文

日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約

・1≤N≤2000
・1000≤Y≤2×10^7
・N は整数である。
・Y は 1000 の倍数である。

解答例

n, y = map(int,input().split())

# 組み合わせが存在するか判定フラグ
flag = False

# お札の組み合わせを全探索
for a in range(n+1): # 1万円札
    if flag:    # 組み合わせが見つかっていたら終了
        break
    for b in range(n-a+1): # 5千円札
        c = (y - 10000 * a - 5000 * b)//1000 # 千円札の枚数候補
        if c >= 0 and a + b + c == n: # 候補が条件を満たすか判定
            print(a,b,c)
            flag = True
            break

# 組み合わせがなければ-1を出力
if flag == False:
    print("-1 -1 -1")

解説

1万円、5千円、千円札をN枚組み合わせてY円にすることができるか、できるならその枚数を答える問題です。

1万円札をa枚、5千円札をb枚、千円札をc枚として全探索を行いました。
Nの範囲が最大で2000なので、3重ループにすると計算量が多くなりすぎです。
1万円札a枚と5千円札b枚、および目標金額Y円が決まっていると、千円札のc枚は計算で求めることができます。

よって、1万円札のaと5千円札のbの2重ループとして各ループごとにcの候補を計算。
候補cがこの問題の条件にあうか判別することで計算量を落としています。

条件を満たすcが見つかれば、a,b,cの組み合わせを出力し、見つからなければ-1を出力すればOKでした。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク