AtCoderでPythonの勉強 その5

AtCoder Beggineres Selection、問5 ABC087B – Coins です

問題文
あなたは、500円玉を A 枚、100円玉を B 枚、50円玉を C 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。
同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約
・0 ≤ A,B,C ≤ 50
・A+B+C ≥ 1
・50 ≤ X ≤ 20,000
・A,B,C は整数である
・X は50 の倍数である
実行時間制限:2sec

入力は以下の形式で標準入力から与えられる。
A
B
C
X

出力　硬貨を選ぶ方法の個数を出力せよ。

全探索すると3重ループになりますが、A, B, Cとも50以下なので全探索しても50の3乗で125,000通り51の3乗で132,651通り。時間的に大丈夫じゃないかなあ。。。

最初に書いたプログラム

A = int(input())
B = int(input())
C = int(input())
X = int(input())

match = 0
for yen500 in range(A):
    for yen100 in range(B):
        for yen50 in range(C):
            if (yen500 * 500 + yen100 * 100 + yen50 * 50) == X:
                match = match + 1
print(match)

例題（A=B=C=2, X=100, 正解は2）を入れたら結果が1になりました。
for x in range(N)
だとxは0からN – 1までしか動かない。まだ基本的なところで間違えてしまいます。
修正版（for文以降のみ）

for yen500 in range(A + 1):
    for yen100 in range(B + 1):
        for yen50 in range(C + 1):
            if (yen500 * 500 + yen100 * 100 + yen50 * 50) == X:
                match = match + 1
print(match)

例題の結果が2になったので提出。 AC いただきました。
実行時間は25msでした。3重ループでもNが小さければ全探索で間に合うようです。