Đổi tiền xu tối thiểu

General
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề 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$.
Draft saved