Olympic 30/4 2018 - Khối 10 - Bài 2 - Chia đất

Xem dạng PDF

Gửi bài giải

Điểm: 0,40 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: chiadat.inp
Output: chiadat.out

Nguồn bài:
Olympic 30/4
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Phú hộ qua đời để lại cho 4 người con một mảnh đất hình vuông có kích thước ~n \times n~, trên đó có trồng một số cây gỗ quí. Theo di chúc, mảnh đất sẽ được chia thành ~4~ phần, mỗi phần là một hình chữ nhật. Để tiết kiệm chi phí chia đất nên chỉ có thể thực hiện cắt mảnh đất bởi một nhát cắt theo chiều ngang và một nhát cắt theo chiều dọc. Các con của phú hộ đều thích có nhiều cây gỗ quí vì vậy họ sẽ chọn phần đất có nhiều cây gỗ quí hơn. Thứ tự nhận đất sẽ từ lớn tới nhỏ, người em út sẽ nhận phần có ít cây gỗ quí nhất.

Yêu cầu: Hãy chỉ cách chia đất để chênh lệch giữa số cây gỗ quí của người anh cả và của người em út là ít nhất.

Input

Cho từ tệp văn bản CHIADAT.INP có định dạng:

  • Dòng thứ nhất ghi số nguyên dương ~n~ (~2 \le n \le 500~).
  • Tiếp theo là ~n~ dòng, mỗi dòng ghi ~n~ số, số ~0~ hoặc số ~1~. Số ~0~ thể hiện vị trí không có cây gỗ quí, số ~1~ thể hiện vị trí có cây gỗ quí.
  • Các số ghi trên cùng một dòng cách nhau bởi ít nhất một kí tự trắng.

Output

Ghi vào tệp văn bản CHIADAT.OUT chỉ có một dòng ghi một số nguyên là số lượng chênh lệch cây gỗ quí ít nhất trên phần đất của người anh cả và của người em út.

Ràng buộc

  • Có ~50\%~ số test tương ứng ~50\%~ số điểm có ~2 \le n \le 150~.
  • Có ~50\%~ số test tương ứng ~50\%~ số điểm có ~150 < n \le 500~.

Sample Input 1

6
1 0 1 0 0 1
0 1 0 0 0 1
1 0 0 0 0 0
0 1 1 0 0 1
0 1 0 0 1 0
1 0 1 0 0 0

Sample Output 1

1

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -32
    ANHTUANCBN  đã bình luận lúc 4, Tháng 3, 2022, 21:56

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.