Cho một số nguyên dương và một tập hợp các mệnh giá tiền cố định .
Nhiệm vụ của bạn là phân tích số nguyên thành tổng của các phần tử thuộc tập sao cho tổng số lượng các phần tử được sử dụng là ít nhất.
Yêu cầu: Tìm giá trị nhỏ nhất.
Dữ liệu:
- Một dòng duy nhất chứa số nguyên ().
Kết quả:
- In ra một số nguyên duy nhất là số lượng tờ tiền ít nhất cần dùng.
Ví dụ:
Dữ liệu:
Kết quả:
Giải thích:
- Số tiền có thể được phân tách thành: . Tổng cộng có tờ tiền. Đây là số lượng ít nhất có thể đạt được.
Dữ liệu:
Kết quả:
Giải thích:
- Số tiền có thể được phân tách thành: . Tổng cộng có tờ tiền.
Giới hạn:
- Subtask #1 (20% số điểm): .
- Subtask #2 (30% số điểm): .
- Subtask #3 (20% số điểm): .
- Subtask #4 (30% số điểm): .
