Chọn ĐTQG Đắk Lắk 2025 - Tổ hợp tên lửa
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Một đơn vị quân đội hiện có ~N~ tên lửa được đánh số từ ~1~ đến ~N~, tên lửa thứ ~i~ có sức công phá là ~a_i~ ~(1 \le a_i \le 10^9)~. Nhờ hệ thống tình báo tinh vi, họ đã biết rằng, để tiêu diệt được các mục tiêu của đối phương thì cần phải sử dụng tổ hợp tên lửa có tổng sức công phá không nhỏ hơn ~P~. Vì tên lửa là loại vũ khí công nghệ cao, rất đắt đỏ, nên họ muốn sử dụng nó một cách tối ưu nhất.
Để chuẩn bị cho trận chiến, họ cần rà soát lại và đánh giá vai trò của từng tên lửa. Với tên lửa thứ ~i~, họ xét mọi tổ hợp có chứa nó mà có thể tiêu diệt được mục tiêu. Nếu sau khi bỏ tên lửa thứ ~i~ ra khỏi các tổ hợp đó, mà tồn tại một tổ hợp không còn tiêu diệt được mục tiêu thì tên lửa thứ ~i~ cần phải được đưa ngay vào thế sẵn sàng chiến đấu. Ngược lại, nếu sau khi bỏ tên lửa thứ ~i~ ra, mỗi tổ hợp còn lại vẫn còn đủ sức công phá mục tiêu thì tên lửa thứ ~i~ chưa cần đưa vào thế sẵn sàng. Biết rằng, sau khi loại bỏ tên lửa thứ ~i~, tổ hợp còn lại nếu không còn tên lửa nào thì vẫn được tính là một tổ hợp tên lửa có sức công phá bằng ~0~.
Yêu cầu: Hãy cho biết những tên lửa nào cần được đưa ngay vào thế sẵn sàng chiến đấu.
Input
Dòng đầu tiên chứa hai số nguyên dương ~N, P~ ~(N, P \le 5 \cdot 10^3)~;
Dòng thứ hai chứa ~N~ số nguyên ~a_i~ ~(1 \le i \le N)~ là sức công phá của các tên lửa.
Output
Một dòng duy nhất là số thứ tự của các tên lửa cần đưa ngay vào thế sẵn sàng chiến đấu theo thứ tự từ nhỏ đến lớn, các số cách nhau một khoảng trắng.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~N \le 20~ |
| 2 | ~40\%~ | ~N, P \le 400~ |
| 3 | ~40\%~ | Không có giới hạn gì thêm |
Sample Input 1
4 9
5 4 2 6
Sample Output 1
1 2 4
Notes
Các tổ hợp chứa tên lửa thứ nhất mà có thể tiêu diệt mục tiêu là: ~\{5; 4\}, \{5; 6\}, \{5; 4; 2\}, \{5; 4; 6\}, \{5; 2; 6\}, \{5; 4; 2; 6\}~. Tồn tại tổ hợp ~\{5; 4\}~ khi bỏ tên lửa thứ nhất thì sức công phá còn lại là ~4~ nên không tiêu diệt được mục tiêu, nên cần đưa tên lửa thứ nhất vào thế sẵn sàng chiến đấu.
Các tổ hợp chứa tên lửa thứ ba mà có thể tiêu diệt mục tiêu là: ~\{5; 4; 2\}, \{5; 2; 6\}, \{4; 2; 6\}, \{5; 4; 2; 6\}~. Khi bỏ tên lửa thứ ba thì các tổ hợp này vẫn tiêu diệt được mục tiêu, nên chưa cần đưa tên lửa thứ ba vào thế sẵn sàng.
Bình luận