Đổi tiền xu

Buổi 12 — Greedy Algorithm greedy Implementation
Points
8
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Hệ thống tiền tệ có các mệnh giá xu gồm: $1, 5, 10, 20, 50, 100, 500$. Với số tiền nguyên dương $N$, hãy tìm số lượng đồng xu ít nhất cần dùng để đổi được đúng số tiền $N$ (mỗi mệnh giá có thể dùng nhiều lần).

Dữ liệu vào

Một dòng duy nhất chứa số nguyên dương $N$.

Dữ liệu ra

Một số nguyên duy nhất là số lượng đồng xu ít nhất cần dùng.

Ví dụ
Input Output
68 6
1000 2
Giới hạn
  • $1 \le N \le 10^9$
Draft saved