Nhiệm vụ của bạn là chọn ra một tập hợp con gồm ít phần tử nhất từ dãy số đã cho, sao cho tổng giá trị của các phần tử được chọn nghiêm ngặt lớn hơn tổng giá trị của các phần tử còn lại không được chọn.
Cụ thể, gọi là tập các chỉ số của các phần tử được chọn (). Tìm giá trị nhỏ nhất thỏa mãn:
Dữ liệu:
Dòng đầu tiên chứa số nguyên duy nhất ().
Dòng thứ hai chứa số nguyên dương ().
Kết quả:
In ra một số nguyên duy nhất là số lượng phần tử ít nhất cần chọn.
Ví dụ:
Dữ liệu:
3
2 1 2
Kết quả:
2
Giải thích:
Tổng của cả dãy là .
Nếu chọn hai phần tử , tổng là . Phần tử còn lại là , tổng là . Vì nên số lượng phần tử tối thiểu là . (Nếu chỉ chọn một phần tử có giá trị , tổng là , không lớn hơn tổng phần còn lại là ).
Dữ liệu:
6
1 1 1 2 2 2
Kết quả:
3
Giải thích:
Tổng của cả dãy là . Một nửa tổng là .
Ta cần chọn các phần tử sao cho tổng của chúng lớn hơn .
Chọn ba phần tử có giá trị lớn nhất là có tổng là . Số lượng ít nhất là .
Giới hạn:
Subtask #1 (15% số điểm): .
Subtask #2 (20% số điểm): .
Subtask #3 (10% số điểm): Các phần tử trong dãy bằng nhau ().
Subtask #4 (25% số điểm): và .
Subtask #5 (30% số điểm): Không có ràng buộc bổ sung.
