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
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;
}