Tìm trung vị của hai mảng đã sắp xếp trong O(log(min(M, N)))

Mục tiêu kiến thức

• Hiểu bài toán phân hoạch nhị phân hai mảng đã sắp xếp: Chia hai mảng A và B thành hai nửa trái và phải sao cho số lượng phần tử hai nửa bằng nhau và mọi phần tử nửa trái đều ≤ mọi phần tử nửa phải.
• Chặt nhị phân trên mảng có kích thước nhỏ hơn để đạt độ phức tạp O(log(min(M, N))) thay vì O(M + N).
• Xử lý chính xác giá trị trung vị cho cả hai trường hợp: tổng số phần tử lẻ và chẵn.

Mô tả bài toán

Cho hai mảng đã sắp xếp tăng dần A (gồm N phần tử) và B (gồm M phần tử). Hãy tìm giá trị trung vị của mảng hợp nhất A ∪ B.

• Nếu tổng số phần tử N + M là lẻ, trung vị là phần tử chính giữa.
• Nếu N + M là chẵn, trung vị là trung bình cộng của 2 phần tử chính giữa (in ra số thực với đúng 1 chữ số thập phân).

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 0 ≤ N, M ≤ 10⁵.
• Thời gian: 1000ms. Bộ nhớ: 256MB.