Otoshidama [AtCoder Beginner Contest 085 C]

https://abc085.contest.atcoder.jp/tasks/abc085_c

解法

https://abc085.contest.atcoder.jp/submissions/1952413

10000円と5000円と1000円の枚数a,b,cを全探索する。
このまま全探索するとO(N^3)でTLEするので、a,bのみ全探索する。
するとcはN-(a+b)となり一意に定まるので大丈夫。
これはO(N^2)。あとは、合計がYになるかを判定して、なれば答える。
どれもならないなら-1
オーバーフローするかもと思いlong longを使った。

typedef long long ll;
int N; ll Y;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Y;
    rep(a, 0, N + 1) rep(b, 0, N + 1) {
        int c = N - (a + b);
        if (0 <= c) {
            if (10000LL * a + 5000LL * b + 1000LL * c == Y) {
                printf("%d %d %d\n", a, b, c);
                return;
            }
        }
    }
 
    printf("-1 -1 -1\n");
}