#79. Trạm Quan Trắc (Mã bài: OBSERVATORY)

Để chuẩn bị cho dự án tìm kiếm sự sống ngoài trái đất, Cơ quan Hàng không Vũ trụ quyết định xây dựng một trạm quan trắc mới trên cao nguyên đá. Bản đồ địa hình của cao nguyên được mô tả bởi một lưới ô vuông kích thước , trong đó ô ở hàng , cột có độ cao là .

Trạm quan trắc cần một nền móng vững chắc hình chữ nhật kích thước (chiếm hàng liên tiếp và cột liên tiếp trên bản đồ). Để đảm bảo sự ổn định về mặt địa chất và tối ưu hóa tầm nhìn, các kỹ sư trưởng quy định rằng "độ cao nền" của trạm quan trắc sẽ được tính bằng giá trị trung vị của các độ cao trong khu vực được chọn.

Mục tiêu của dự án là chọn vị trí đặt nền móng sao cho "độ cao nền" đạt giá trị lớn nhất có thể. Nếu có nhiều vị trí cùng đạt được độ cao lớn nhất này, hãy đếm số lượng các vị trí đó.

Định nghĩa trung vị: Với một khu vực gồm ô có độ cao . Sắp xếp các độ cao này theo thứ tự không giảm: . Giá trị trung vị là .

Yêu cầu:

1. Tìm giá trị trung vị lớn nhất có thể đạt được.
2. Đếm số lượng vị trí đặt trạm quan trắc đạt được giá trị đó.

Dữ liệu:

• Dòng đầu tiên chứa bốn số nguyên dương ;
• dòng tiếp theo, mỗi dòng chứa số nguyên dương, số thứ của dòng thứ là .

Kết quả: Gồm một dòng ghi hai số nguyên là độ cao nền lớn nhất tìm được và số lượng vị trí đặt trạm quan trắc đạt được độ cao đó.

Ví dụ:

Dữ liệu:

4 5 3 3
10 20 30 40 50
15 25 35 45 55
5 15 25 35 45
10 10 10 10 10

Kết quả:

40 1

Giải thích: Cửa sổ kích thước . Xét vị trí góc trên bên phải (hàng 1-3, cột 3-5):

• Các độ cao trong vùng: .
• Sắp xếp: .
• Trung vị (phần tử thứ ): 40. Đây là giá trị lớn nhất có thể đạt được trong tất cả các vị trí, và chỉ có duy nhất 1 vị trí này.

Giới hạn:

• Subtask (20% số điểm): ;
• Subtask (30% số điểm): và ;
• Subtask (10% số điểm): ;
• Subtask (40% số điểm): không có ràng buộc bổ sung.