Đổi tiền xu tối thiểu
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Hệ thống tiền tệ có các mệnh giá xu: $1, 2, 5, 10, 20, 50, 100, 200, 500$. Cho số tiền nguyên không âm $N$, hãy tìm số lượng đồng xu ít nhất cần dùng để tạo thành đúng tổng tiền $N$.
Dữ liệu vào
Một dòng duy nhất chứa số nguyên $N$.
Dữ liệu ra
In ra số lượng đồng xu ít nhất.
Ví dụ
| Input | Output |
|---|---|
| 43 | 4 |
| 1000 | 2 |
Giới hạn
- $0 \le N \le 10^9$.
Community Discussion