Đếm số cách đổi tiền không phân biệt thứ tự
Cùng một số tiền có thể được ghép từ các đồng xu theo nhiều cách, nhưng 1 + 2 và 2 + 1
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
Cùng một số tiền có thể được ghép từ các đồng xu theo nhiều cách, nhưng 1 + 2 và 2 + 1 được coi là một cách vì chỉ khác thứ tự. Việc đếm theo tổ hợp đòi hỏi thứ tự vòng lặp khác với bài đếm dãy bước, và đó chính là điểm dễ sai nhất của dạng bài này.
Yêu cầu
Cho k loại mệnh giá (mỗi loại có vô số đồng) và số tiền t. Hãy đếm số cách chọn một nhóm đồng xu có tổng đúng bằng t, không phân biệt thứ tự sắp xếp.
Quy ước nộp bài
Nộp tệp solution.cpp đọc dữ liệu từ stdin và ghi kết quả ra stdout. Chỉ in một số nguyên trên một dòng, không kèm chữ hay dấu cách thừa.
Input
- Dòng thứ nhất: hai số nguyên k và t (1 <= k <= 10, 1 <= t <= 300).
- Dòng thứ hai: k số nguyên là mệnh giá, cách nhau bởi dấu cách (1 <= giá trị <= 300).
Output
- Một số nguyên trên một dòng là số cách đổi. In 0 nếu không có cách nào.
Ràng buộc
- Mỗi mệnh giá dùng được không hạn chế số lượng.
- Hai cách chỉ khác nhau ở thứ tự các đồng xu được tính là một.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
3 5
1 2 5
Output
4
Ví dụ 2
Input
2 4
1 2
Output
3
Giải thích
Bốn cách là 1+1+1+1+1, 1+1+1+2, 1+2+2, 5; cách 2+1+1+1 đã trùng với 1+1+1+2 nên không tính lại. In ra:
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.
