Mô tả
Chị Hồng làm quầy vé ở bến xe Miền Đông. Chiều nay, một bác khách tóc bạc phơ vừa mua vé đi về quê đón lễ. Bác đưa cho chị tờ năm trăm nghìn crisp tinh tươm, còn giá vé chuyến này chỉ có hai trăm ba mươi nghìn đồng. Chị Hồng mở ngăn kéo, nhìn các xấp tiền lẻ được sắp ngăn nắp và bắt đầu tính nhẩm xem nên trả lại bác mấy tờ để vừa đủ tiền mà bác lại không phải cầm xó nhiều giấy lẻ.
Ngăn kéo của chị có sáu mệnh giá theo thứ tự giảm dần: 500000, 200000, 100000, 50000, 20000, 10000. Vì là hệ tiền tệ chuẩn của Việt Nam, chị luôn ưu tiên lấy mệnh giá lớn nhất trước để số tờ trả lại là ít nhất. Nhiệm vụ của bạn là viết một chương trình nhận vào số tiền cần trả lại và tính tổng số tờ tiền tối thiểu mà chị Hồng phải đưa cho khách.
Đầu vào
Một số nguyên dương amount — số tiền cần trả lại, tính bằng đồng (VND).
Đầu ra
Trả về một số nguyên duy nhất là tổng số tờ tiền ít nhất cần đổi. Dữ liệu vào luôn đảm bảo amount là bội số của 10000, nên chắc chắn đổi được đúng hết.
Ràng buộc
- 10000 ≤ amount ≤ 1000000000 (tức từ một tờ mười nghìn đến một trăm nghìn tờ).
amountluôn chia hết cho 10000.
Ví dụ
Giả sử amount = 270000 (chị cần trả lại hai trăm bảy mươi nghìn).
- Đầu tiên lấy mệnh giá 200000: đổi được 1 tờ, còn lại 70000.
- Tiếp theo bỏ qua 100000 vì lớn hơn 70000, lấy luôn mệnh giá 50000: đổi được 1 tờ, còn lại 20000.
- Cuối cùng lấy mệnh giá 20000: đổi được 1 tờ, còn lại 0.
Tổng cộng cần 3 tờ, nên kết quả trả về là 3.