Vật trên lưng ngựa đôi
Đề bài
Mô tả
Ủy ban Thăm dò Đại hội Thể thao Du mục (NGEC) đang thăm dò ý tưởng tổ chức một giải đấu vật trên lưng ngựa đôi, trong đó mỗi đội gồm hai kỵ sĩ cùng cưỡi một con ngựa. Ủy ban đã quảng bá một giải đấu thử nghiệm, và đã có kỵ sĩ hăng hái đăng ký thi đấu! Giờ NGEC cần ghép các kỵ sĩ thành từng cặp sao cho giải đấu vừa công bằng vừa hấp dẫn.
Liên đoàn Audaryspak Trung Á (CAAL) lưu danh sách tất cả các đô vật trên lưng ngựa cùng điểm xếp hạng của họ. Từ kinh nghiệm với môn vật trên lưng ngựa thông thường, NGEC quyết định rằng một cặp cân bằng nhất khi tổng điểm xếp hạng của hai kỵ sĩ bằng đúng một số nguyên cho trước.
Vì những lý do bản quyền khó hiểu, CAAL từ chối công bố điểm xếp hạng chính xác của từng kỵ sĩ. Tuy vậy, NGEC có những ước lượng khá tốt: họ biết điểm xếp hạng thật của kỵ sĩ nằm trong đoạn . Vì vậy NGEC sẽ cân nhắc ghép hai kỵ sĩ và thành một cặp nếu tồn tại các điểm xếp hạng và sao cho .
NGEC muốn tạo ra nhiều cặp kỵ sĩ nhất có thể, trong đó không có kỵ sĩ nào thuộc hai cặp. Hãy giúp họ.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (, ): số kỵ sĩ và tổng điểm xếp hạng mong muốn của hai kỵ sĩ trong một cặp. Các kỵ sĩ được đánh số từ đến .
Tiếp theo là dòng, dòng thứ chứa hai số nguyên và (): đoạn điểm xếp hạng của kỵ sĩ thứ .
Dữ liệu ra
In ra , số cặp lớn nhất có thể tạo được, sau đó là dòng, mỗi dòng gồm hai số nguyên là số hiệu của hai kỵ sĩ trong một cặp. Nếu có nhiều cách ghép cặp, in ra cách bất kỳ.
Ràng buộc
- , .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 10 6 7 1 4 2 2 3 8 5 7 9 9 |
2 6 2 3 4 |
Kỵ sĩ () ghép với kỵ sĩ (), kỵ sĩ () ghép với kỵ sĩ (). Không có hai kỵ sĩ nào trong nhóm , , , ghép được với nhau, nên mỗi cặp phải chứa kỵ sĩ hoặc kỵ sĩ : không thể có cặp. |
| 4 10 5 5 4 6 1 2 3 3 |
1 1 2 |
Kỵ sĩ cần bạn có điểm từ đến , kỵ sĩ cần bạn có điểm : không ai đáp ứng được. Chỉ ghép được kỵ sĩ với kỵ sĩ (). |
Bình luận