Ba lô nửa đầy
Đề bài
Mô tả
Bạn có một chiếc ba lô sức chứa và món đồ, món thứ nặng .
Hãy chọn một số món bỏ vào ba lô sao cho tổng trọng lượng của chúng ít nhất bằng một nửa sức chứa nhưng không vượt quá sức chứa, tức là:
Lưu ý bạn không cần làm tổng trọng lượng lớn nhất có thể, chỉ cần nó nằm trong đoạn trên. Nếu có nhiều cách chọn thoả mãn, in ra cách nào cũng được. Nếu không tồn tại cách chọn nào, hãy báo là không thể.
Dữ liệu vào
- Dòng đầu chứa số nguyên : số lượng bộ dữ liệu.
- Với mỗi bộ dữ liệu:
- Dòng đầu chứa hai số nguyên và .
- Dòng thứ hai chứa số nguyên .
Dữ liệu ra
Với mỗi bộ dữ liệu:
- Nếu không có cách chọn nào thoả mãn, in ra một số .
- Ngược lại, in ra trên dòng đầu số lượng món được chọn, dòng thứ hai in số nguyên đôi một khác nhau () là chỉ số các món được chọn.
Ràng buộc
- Tổng trên tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 3 3 6 2 19 8 19 69 9 4 7 12 1 1 1 17 1 1 1 |
1 1 -1 6 1 2 3 5 6 7 |
Bộ 1: món duy nhất nặng đúng . Bộ 2: nhưng mọi món đều nặng hơn nên không bỏ được món nào. Bộ 3: , lấy sáu món nặng (bỏ qua món nặng ) cho tổng đúng . |
| 4 2 10 1000000000 6 3 10 11 3 3 1 5 2 2 9 4 4 |
1 2 2 2 3 -1 2 1 2 |
Bộ 1: món nặng hơn nên phải bỏ qua, món nặng . Bộ 2: món nặng , hai món còn lại cho tổng . Bộ 3: mà món duy nhất chỉ nặng . Bộ 4: nên một món nặng là chưa đủ, phải lấy cả hai để được . |
Bình luận