Problem ID:
thtla_12b_3
Points:
1.6 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
CHANGE.INP
Output:
CHANGE.OUT
Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Perl, Python
Có ~4~ loại tiền mệnh giá ~5~ đồng, ~10~ đồng, ~20~ đồng và ~50~ đồng với số lượng mỗi lọai tờ tiền là không giới hạn. Một người cần đổi ~M~ đồng thành các tờ tiền với mệnh giá như đã cho.
Yêu cầu: Viết chương trình nhập vào số nguyên ~M~ ~(0 \le M < 100 000 000)~
- Kiểm tra xem có thể đổi hết M đồng thành các tờ tiền theo mệnh giá đã cho không?
- Nếu có thể đổi hết M đồng, thì hãy cho biết tổng số tờ đổi được ít nhất là bao nhiêu?
Dữ liệu vào:
Cho trong tập tin văn bản CHANGE.INP
gồm một dòng chứa số nguyên ~M~.
Dữ liệu ra:
Ghi ra tập tin văn bản CHANGE.OUT
gồm một dòng duy nhất:
- Nếu không thể đổi được thì ghi
-1
- Nếu đổi được thì ghi tổng số tờ đổi được ít nhất.
Sample Input 1
75
Sample Output 1
3
Với ~75~ đồng thì có thể đổi được ~1~ tờ ~50~ đồng, ~1~ tờ ~20~ đồng và ~1~ tờ ~5~ đồng. Do đó tổng số tờ đổi được ít nhất là ~3~.
Sample Input 2
104
Sample Output 2
-1
Với ~104~ đồng thì không thể đổi hết thành các tờ tiền với mệnh giá như trên.
Comments