Đổi tiền bằng ít đồng xu nhất
Máy đổi tiền chỉ có bốn loại xu mệnh giá 25, 10, 5 và 1. Với mỗi số tiền cần trả,
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Máy đổi tiền chỉ có bốn loại xu mệnh giá 25, 10, 5 và 1. Với mỗi số tiền cần trả, máy muốn dùng càng ít đồng xu càng tốt để tiết kiệm vật lý cho nhân viên nạp tiền.
Yêu cầu
Cho số tiền n (đơn vị là đồng xu nhỏ nhất). Hãy in ra số đồng xu ít nhất cần dùng để đổi đủ n, khi chỉ được dùng các mệnh giá 25, 10, 5, 1 và mỗi mệnh giá được dùng bao nhiêu đồng cũng được.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc n từ stdin và in ra stdout một số nguyên duy nhất là số đồng xu ít nhất.
Input
- Một số nguyên n (1 <= n <= 1000).
Output
Một số nguyên duy nhất: số đồng xu ít nhất cần dùng.
Ràng buộc
- Bộ mệnh giá cố định là {25, 10, 5, 1}, không có mệnh giá nào khác.
- Quy tắc tham lam đúng cho bộ mệnh giá này: **luôn lấy mệnh giá lớn nhất còn vừa với số
tiền còn lại**, lặp cho tới khi hết tiền. Vì n chia hết cho 1, quy tắc này luôn kết thúc và cho kết quả tối ưu.
- Mỗi bộ dữ liệu chạy trong 1 giây.
Ví dụ 1
Input
41
Output
4
Ví dụ 2
Input
30
Output
2
Giải thích
Với n = 41, dùng 25 + 10 + 5 + 1 là 4 đồng xu; không có cách nào dùng 3 đồng xu để đủ 41, nên in ra 4.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
