trang chủ / đề bài / icpc22_nat_m

Trung vị của dãy XOR

Đề bài

Mô tả

Cho bốn số nguyên không âm a, b, c và d. Gọi S là "đa tập" chứa mọi giá trị z=x⊕y của tất cả các cặp số nguyên (x,y) thỏa mãn a≤x≤b và c≤y≤d. Nhiệm vụ của bạn là tìm trung vị của S.

Lưu ý S là một "đa tập": nếu có nhiều cặp (x,y) cho cùng một giá trị x⊕y thì giá trị đó xuất hiện nhiều lần trong S.

Ví dụ, xét a=3, b=5, c=6 và d=9. Ta có:

  • 3⊕6=5, 3⊕7=4, 3⊕8=11, 3⊕9=10;
  • 4⊕6=2, 4⊕7=3, 4⊕8=12, 4⊕9=13;
  • 5⊕6=3, 5⊕7=2, 5⊕8=13, 5⊕9=12.

Như vậy 12 phần tử của S theo thứ tự tăng dần là 2,2,3,3,4,5,10,11,12,12,13,13, nên trung vị của S, tức phần tử thứ sáu, là 5.

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 1 khi và chỉ khi hai bit khác nhau, bằng 0 khi hai bit bằng nhau. Ví dụ:

  • 3⊕6=0112⊕1102=1012=5;
  • 4⊕7=1002⊕1112=0112=3;
  • 5⊕8=01012⊕10002=11012=13.

Trung vị của dãy số đã sắp xếp tăng dần v1≤v2≤…≤vn là vn/2 nếu n chẵn và v(n+1)/2 nếu n lẻ.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên t (1≤t≤75), số bộ test.
  • Mỗi dòng trong t dòng tiếp theo chứa bốn số nguyên a, b, c, d (0≤a,b,c,d<10200, a≤b, c≤d) 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 S, viết ở hệ thập phân.

Ràng buộc

  • 1≤t≤75.
  • 0≤a≤b<10200, 0≤c≤d<10200.

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, S={1,2} nên trung vị là phần tử thứ nhất, 1. Ở bộ test thứ ba, mỗi giá trị từ 0 đến 3 xuất hiện 4 lần; phần tử thứ 8 là 1. Ở bộ test thứ tư, S={3,4,5,6,7}.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0