Trung vị của dãy XOR
Đề bài
Mô tả
Cho bốn số nguyên không âm , , và . Gọi là "đa tập" chứa mọi giá trị của tất cả các 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 "đa tập": nếu có nhiều cặp cho cùng một giá trị thì giá trị đó xuất hiện nhiều lần trong .
Ví dụ, xét , , và . Ta có:
- , , , ;
- , , , ;
- , , , .
Như vậy phần tử của theo thứ tự tăng dần là , nên trung vị của , tức phần tử thứ sáu, là .
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, bằng khi hai bit bằng nhau. Ví dụ:
- ;
- ;
- .
Trung vị của dãy số đã sắp xếp 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.
- Mỗi dòng trong dòng tiếp theo chứa bốn số nguyên , , , (, , ) mô tả một bộ test. Mọi số đều 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 11 13 20 22 |
5 26 |
Bộ test thứ nhất được giải thích ở trên. |
| 4 0 0 0 0 1 2 3 3 0 3 0 3 7 7 0 4 |
0 1 1 5 |
Ví dụ này không có trong đề gốc. Ở bộ test thứ hai, nên trung vị là phần tử thứ nhất, . Ở bộ test thứ ba, mỗi giá trị từ đến xuất hiện lần; phần tử thứ là . Ở bộ test thứ tư, . |
Bình luận