Bài 5: ( 3điểm) Chia lưới
Cho lưới M x 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 giá 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 vào: từ file BAI5.INP, được cho như sau:
- Dòng đầu tiên gồm 2 số M, N là kích thước ô 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 trống, ô nào không có giá trị được cho
bằng 0.
Kết quả: ghi ra file BAI5.OUT miêu tả lưới sau khi thành hai phần, là một ma trận kích thước M x 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, số 1 ký hiệu cho các ô tương ứng với phần thứ
hai).
BAI5.INP BAI5.OUT
ví dụ:
5 6
1 1 1 1 1 1
0 0 0 0 7 0
1 1 0 0 0 0
0 1 3 5 0 0
0 12 2 5 0 0
0 0 0 0 0 0
0 9 2 10 0 0
0 0 0 0 0 0
Bạn đang xem bài 5: - ĐỀ THI CHỌN HỌC SINH GIỎI TỈNH NĂM HỌC 2010-2011 MÔN TIN HỌC LỚP 12 THPT