Bài 004. BẢNG SỐ


Cho một bảng hình chữ nhật kích thước M x N với M, N nguyên dương. M, N  50. Hình chữ nhật này được chia thành M x N ô vuông bằng nhau với kích thước đơn vị bởi các đường song song với các cạnh, trên ô vuông [i, j] ghi số nguyên A[i, j] (2  A[i, j]  50). Từ mảng A ta lập mảng B mà B[i, j] được xây dựng như sau: Biểu diễn số A[i, j] thành tổng các số nguyên tố với ràng buộc: trong biểu diễn đó có nhiều nhất chỉ một số nguyên tố xuất hiện hai lần. Trong các cách biểu diễn, chọn ra biểu diễn nhiều hạng tử nhất thì B[i, j] bằng số số hạng của biểu diễn này kể cả bội (nếu có). Ví dụ: Nếu A[i, j] = 10 = 2 + 3 + 5 thì B[i, j] = 3; Nếu A[i, j] = 12 = 2 + 2 + 3 + 5 thì B[i, j] = 4; Chú ý: Không được biểu diễn A[i, j] = 10 = 2 + 2 + 2 + 2 + 2 để có B[i, j] = 5 vì như vậy không thoả mãn ràng buộc a) Dữ liệu vào được cho bởi Text file INP.B1 trong đó: Dòng đầu ghi hai số M, N M dòng sau, dòng thứ i ghi N phần tử trên dòng i của bảng A: A[i, 1], A[i, 2], ..., A[i, N] hai phần tử liên tiếp cách nhau ít nhất một dấu trống. b) Kết quả ghi ra Text file OUT.B1: Giá trị bảng B, mỗi dòng của bảng ghi trên một dòng của file, hai phần tử liên tiếp cách nhau ít nhất một dấu trống. c) Hãy tìm hình chữ nhật lớn nhất được tạo bởi các ô mang giá trị bằng nhau của bảng B. Ghi tiếp ra file OUT.B1 một dòng gồm 5 số là: diện tích lớn nhất tìm được, toạ độ trên trái và dưới phải của hình chữ nhật có diện tích lớn nhất đó.