【AtCoder】ABC085C - Otoshidama

Question

Ruby初心者です。
AtCoderの「ABC085C - Otoshidama」について質問です。

問題文

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

入力

入力は以下の形式で標準入力から与えられる。
N Y
出力
N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。
N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。
複数の可能性が考えられるときは、そのうちどれを出力してもよい。

私の解答としては以下のものを提出しました。

N, Y =gets.chomp.split.map(&:to_i)

ans = [-1, -1, -1]

for i in (0..N) do #10000円の枚数を固定
    if 10000*i > Y
        break
    elsif 10000*i == Y
        ans = [i, 0, 0]
        break
    else
        for j in (0..N-i) do #5000円の枚数を固定
            if 10000*i + 5000*j + 1000*(N-i-j) == Y
                ans = [i, j, N-i-j] 
                break
            end
        end
    end
end

puts ans

このような回答で提出したところ、
サンプルデータはACで、b08とb21はWAです。
サンプルデータでエラーが出なかったので、どこが間違っているのかわかりません。
教えていただけると幸いです。
よろしくお願いします。

Answer 1

10000 * i == Y の判定文ですが、ちょうどN枚である条件が抜けています。
10000 * i == Y && i == N でACできました。

なお、競技プログラミングでは、細かい条件を書くよりも、
適当に全探索してしまった方が早いです。

以下、例を載せておきます。
参考になれば幸いです。

N, Y =gets.chomp.split.map(&:to_i)
 
ans = [-1, -1, -1]
 
for i in (0..N) do
    for j in (0..N-i) do
        k = N - i - j
        if 10000*i + 5000*j + 1000*k == Y
            ans = [i, j, k]
            break
        end
    end
end
 
puts ans

Comments

[taka10taka12]

nanoseeingさま
質問の回答ありがとうございます！！
実はどこを調べても原因が分からなくて途方に暮れていたんです…
ほんとうにありがとうございます！！

ちなみに、どこかの記事で試行回数が増えるほど処理速度は落ちると書いてあったので、途中でループを抜け出せるコードを書きました。
でも、nanoseeing さんのコードの方が簡潔ですね！ありがとうございます！参考にします！！