Cho một dãy số nguyên gồm phần tử , trong đó giá trị của mỗi phần tử chỉ nằm trong tập hợp .
Yêu cầu: Hãy phân chia tất cả phần tử của dãy vào các nhóm sao cho tổng các phần tử trong mỗi nhóm không vượt quá . Hãy tìm số lượng nhóm ít nhất có thể đạt được. Lưu ý rằng mỗi phần tử là một thực thể đơn lẻ, không thể chia nhỏ để đưa vào các nhóm khác nhau.
Dữ liệu:
Dòng đầu tiên chứa số nguyên ().
Dòng thứ hai chứa số nguyên ().
Kết quả:
In ra một số nguyên duy nhất là số lượng nhóm tối thiểu tìm được.
Ví dụ:
Dữ liệu:
5
1 2 4 3 3
Kết quả:
4
Giải thích:
Nhóm 1: Chứa phần tử có giá trị (Tổng = 4).
Nhóm 2: Chứa một phần tử giá trị và một phần tử giá trị (Tổng = ).
Nhóm 3: Chứa một phần tử giá trị (Tổng = 3).
Nhóm 4: Chứa một phần tử giá trị (Tổng = 2).
Dữ liệu:
8
2 3 4 4 2 1 3 1
Kết quả:
5
Giải thích:
Hai nhóm chứa hai phần tử .
Hai nhóm chứa cặp .
Một nhóm chứa hai phần tử .
Giới hạn:
Subtask #1 (10% số điểm): .
Subtask #2 (10% số điểm): với mọi .
Subtask #3 (20% số điểm): với mọi .
Subtask #4 (25% số điểm): .
Subtask #5 (35% số điểm): Không có ràng buộc bổ sung ().
