Tìm Trung Vị Của Hai Mảng Đã Sắp Xếp (Median of Two Sorted Arrays)

Mô tả bài toán

Cho hai mảng số nguyên A và B đã được sắp xếp theo thứ tự tăng dần, kích thước lần lượt là N và M.

Hãy tìm giá trị trung vị (median) của mảng hợp nhất gồm N + M phần tử của hai mảng này.

• Nếu N + M lẻ: Trung vị là phần tử đứng chính giữa.
• Nếu N + M chẵn: Trung vị là trung bình cộng của 2 phần tử đứng chính giữa.

Yêu cầu thuật toán đạt độ phức tạp thời gian O(log(min(N, M))).

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

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.