Thuật toán

NX: Nếu `N` không chia hết cho `100` thì không có cách đổi (Do `500x+200y+100z` với `x,y,z in NN,x^2+y^2+z^2 ne 0` luôn có hai chữ số tận cùng là `0`)

`+` Để đổi được số tờ tiền nhiều nhất thì ta phải đổi chúng ra nhiều nhất tờ có mệnh giá `100` có thể. Mà `N \ vdots \ 100`

`=>` Số tờ tiền nhiều nhất có thể đổi được là `N/100`

`+` Để đổi được số tờ tiền ít nhất thì ta phải ưu tiên đổi chúng ra các mệnh giá lớn nhiều nhất có thể. Vì vậy ta sẽ đổi tờ tiền theo thứ tự sau: `500 -> 200 -> 100`

Dễ thấy rằng luôn tồn tại cách đổi như vậy do sau khi đổi thành các tờ có mệnh giá là `500` và `200` thì số tiền cần đổi còn lại luôn chia hết cho `100`

`=>` Số tờ tiền ít nhất có thể đổi được là `|__N/500__|+|__(N mod 500)/200__|+((N mod 500) mod 200)/100`

Giải thích

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    if (n % 100 != 0) cout << - 1;
    else {
        cout << (n / 500) + ((n % 500) / 200) + ((n % 500) % 200 / 100) << ' ';
        cout << n / 100;
    }
    return 0;
}