HSG THPT Hà Tĩnh 2023 - Vận chuyển

Xem dưới dạng PDF

Gửi bài giải

Điểm: 20
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M

Tác giả:
Kiểu bài tập

Sau khi đóng gói xong n gói quà có trọng lượng lần lượt là \(a_1, a_2, ..., a_n\); ông Nam dùng một chiếc xe chuyên dụng để chở các gói quà đi làm từ thiện. Chiếc xe có thể chở được tối đa một lượng bằng \(s\). Ông Nam muốn chọn \(m\) \((1 \le m \le n)\) gói quà có tổng trọng lượng đúng bằng \(s\) nhằm tăng hiệu quả của việc chuyên chở.

Yêu cầu

  • Bạn hãy giúp ông Nam tính toán xem có tìm được \(m\) gói quà trong \(n\) gói quà trên (các gói quà không nhất thiết phải liền tiếp nhau) để có tổng trọng lượng đúng bằng s cho trước hay không.

Dữ liệu vào

  • Dòng đầu tiên ghi hai số nguyên dương \(n\) và \(s\).
  • Dòng tiếp theo ghi trọng lượng của \(n\) gói quà lần lượt là \(a_1, a_2, ..., a_n\) \((0 \le a_i \le 10^{12}\)).

Dữ liệu ra

  • Nếu có cách chọn được \(m\) gói quà có trọng lượng đúng bằng \(s\) thì dòng đầu tiên ghi \(1\); dòng tiếp theo ghi lần lượt trọng lượng các gói quà được chọn. Nếu có nhiều phương án chỉ cần ghi một phương án bất kỳ.
  • Nếu không có cách chọn các gói quà để có trọng lượng bằng s thì ghi ra \(-1\).

Input 1

5 6  
1 2 4 3 5

Output 1

1  
1 2 3

Input 2

5 16  
1 2 4 3 5

Output 2

-1

Ràng buộc:

  • Có 50% số test có: \(n \le 20, 0 \le a_i \le 10^4, s \le 10^4\).
  • 25% số test có: \(n \le 40, a_i \le 10^{12}, s \le 10^{12}\).
  • 25% số test còn lại có: \(0 \le n \le 200, 0 \le a_i \le 200, s \le 4 \times 10^4\).

Nhận xét

Không có ý kiến tại thời điểm này.