Bạn Lam có N đồng. Lam muốn đổi N đồng (N<=10^6) thành các tờ tiền có mệnh giá 500,200,100. Tính tổng số lượng tờ tiền và nhiều nhất mà Lam có thể dổi được. INPUT Số nguyên dương N. OUTPUT Hai số nguyên dương lần lượt là số lượng tờ tiền ít nhất và nhiều nhất mà Lam có thể đổi được. Nếu không có phương án thỏa mãn, ghi số -1. C++20 cần gấp

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