Bài 56/2001 - Chia lưới
(Dành cho học sinh THPT)
Cho lưới M N (m, n <= 20) ô vuông, trong mỗi ô cho trước một số tự nhiên. Hãy tìm cách chia lưới trên
làm hai phần (chia theo cạnh lưới) sao cho trị tuyệt đối hiệu số của tổng các số trong mỗi phần có giá trị nhỏ
nhất (như hình dưới đây).
7
1 3 5
12 2 5
9 2 10
Dữ liệu được cho trong file LUOI.INP, được cho như sau:
- Dòng đầu tiên gồm 2 số m, n là kích thước của ô lưới.
- m dòng tiếp theo, mỗi dòng gồm n số cách nhau bởi dấu cách, ô nào không có giá trị được cho bằng 0.
Dữ liệu ra trong file LUOI.OUT miêu tả lưới sau khi chia thành hai phần: là một ma trận kích thước m n
gồm các số 0 và 1 (số 0 kí hiệu cho các ô tương ứng với phần thứ nhất, và số 1 kí hiệu cho các ô tương ứng
với phần thứ hai).
Sample Input:
Dữ liệu cho sau đây tương ứng với hình trên:
Sample Output:
5 6
0 1 1 1 1 1
0 0 0 0 7 0
0 1 3 5 0 0
0 1 0 1 1 1
0 12 2 5 0 0
0 0 0 1 1 1
0 9 2 10 0 0
0 0 0 0 0 0
0 0 0 0 0 1
Bạn đang xem bài 56/ - 100 DE TIN HSG CO DAP AN
