N枚のお札がすべてが5000円だったとして目標金額と合計金額の比較をすると、 合計金額を減らすためには5000円を1000円に変換するしかなく、 合計金額を増やすためには5000円を10000円に変換するしかない。 これを利用すればよい。 もし行ったり来たりしてもたどり着けないならばそれは不可能な数値。
実装上の注意としては、N枚目の変換が終わった後にもう一度判定を入れなくてはならないので、 ループをN+1回回すか、ループ終了後に再度判定を入れる必要がある。サンプルテストケースに助けられたので反省。 また、sumは毎回計算しても全然間に合ったが、本当は5000 * Nの初期値に対して変換のたびに-4000か+5000すれば追加の計算は不要。
もしお札が4枚だったら場合分け必要そうだから探索かな。。
def solve(N, Y): r = [5000 for _ in range(N)] for i in range(N + 1): s = sum(r) if s == Y: return ( len([d for d in r if d == 10000]), len([d for d in r if d == 5000]), len([d for d in r if d == 1000])) elif s < Y and i < N: r[i] = 10000 elif s > Y and i < N: r[i] = 1000 return (-1, -1, -1) if __name__ == "__main__": N, Y = tuple(map(int, input().split(" "))) print(" ".join(map(str, list(solve(N, Y)))))
