Trung vị của dãy XOR (bản dễ)
Đề bài
Mô tả
Nếu đã tham gia kỳ thi ICPC Quốc gia Việt Nam 2022, chắc hẳn bạn vẫn còn nhớ bài cuối cùng của kỳ thi, Median of Xor Sequence. Lần này, chúng tôi đưa ra cho bạn một phiên bản gần như y hệt bài toán đó. Và để mọi thứ dễ hơn nữa, giới hạn của các số trong dữ liệu đã được giảm đáng kể. Chúng tôi mong được thấy thật nhiều bài nộp Accepted!
Cho bốn số nguyên không âm , , và . Gọi là tập hợp chứa tất cả các giá trị của mọi cặp số nguyên thỏa mãn và . Nhiệm vụ của bạn là tìm trung vị của .
Lưu ý là một tập hợp. Nói cách khác, nếu có nhiều cặp cho cùng một giá trị thì giá trị đó chỉ được tính một lần trong .
Ví dụ, xét , , và . Ta có:
- , , , ;
- , , , ;
- , , , .
Do đó có phần tử phân biệt, theo thứ tự tăng dần là , nên trung vị của là phần tử thứ tư, bằng .
Phép XOR theo bit (ký hiệu ) là phép toán trên hai dãy bit cùng độ dài, thực hiện phép hoặc loại trừ trên từng cặp bit tương ứng: bit kết quả bằng khi và chỉ khi hai bit khác nhau, và bằng khi hai bit giống nhau. Ví dụ:
- ;
- ;
- .
Trung vị của một dãy số tăng dần là nếu chẵn và nếu lẻ.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên (), số bộ test.
- dòng tiếp theo, mỗi dòng chứa bốn số nguyên , , , (, , ) mô tả một bộ test. Mọi số đều được viết ở hệ thập phân.
Dữ liệu ra
Với mỗi bộ test, in ra trên một dòng một số nguyên là trung vị của , viết ở hệ thập phân.
Ràng buộc
- .
- , , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 5 6 9 6 9 12 22 |
5 19 |
Bộ test đầu tiên là ví dụ trong đề bài. |
| 2 0 0 0 0 0 3 4 4 |
0 5 |
; có phần tử nên trung vị là phần tử thứ hai, bằng . |
Bình luận