Nhân dịp lễ kỷ niệm thành lập trường, Đoàn thanh niên tổ chức một màn đồng diễn xếp hình trên sân vận động. Sân được chia thành một lưới ô vuông kích thước . Tại mỗi ô vuông, một học sinh sẽ đứng và mặc áo màu Trắng (biểu thị bằng số ) hoặc màu Xanh (biểu thị bằng số ).
Để quản lý và điều phối đội hình này, Ban tổ chức áp dụng một sơ đồ phân cấp nhân sự theo quy tắc đệ quy như sau:
Xét một khu vực hình vuông trên sân:
Nếu tất cả học sinh trong khu vực đều mặc áo cùng một màu (tất cả là hoặc tất cả là ), Ban tổ chức chỉ cần cử một người quản lý trực tiếp để phụ trách khu vực đó.
Nếu khu vực có sự pha trộn giữa hai màu áo, Ban tổ chức sẽ cử một người giám sát cấp cao để điều phối chung, đồng thời chia khu vực thành 4 khu vực hình vuông nhỏ hơn có kích thước bằng nhau (tương ứng với 4 góc: trên-trái, trên-phải, dưới-trái, dưới-phải). Quy trình này được lặp lại đệ quy cho từng khu vực con cho đến khi các khu vực đạt được sự đồng nhất về màu áo.
Nhiệm vụ của bạn là xác định tổng số nhân sự (bao gồm cả người quản lý trực tiếp và người giám sát cấp cao) cần thiết để quản lý toàn bộ đội hình trên sân theo sơ đồ trên.
Dữ liệu:
Dòng đầu tiên chứa số nguyên (). Kích thước của sân là .
dòng tiếp theo, mỗi dòng chứa số nguyên ( hoặc ) mô tả màu áo của các học sinh trên sân.
Kết quả:
Một số nguyên duy nhất là tổng số lượng nhân sự cần điều động.
Ví dụ:
Dữ liệu:
1
1 1
1 0
Kết quả:
5
Dữ liệu:
2
0 0 0 0
0 0 0 0
0 0 1 1
0 0 1 0
Kết quả:
9
Giải thích:
Ở ví dụ 1: Sân kích thước có màu áo không đồng nhất nên cần 1 người giám sát cấp cao và 4 người quản lý trực tiếp cho từng ô đơn lẻ. Tổng là .
Ở ví dụ 2: Sân kích thước không đồng nhất (1 người giám sát cấp cao tại gốc). Chia thành 4 vùng :
Vùng trên-trái toàn màu Trắng: 1 người quản lý trực tiếp.
Vùng trên-phải toàn màu Trắng: 1 người quản lý trực tiếp.
Vùng dưới-trái toàn màu Trắng: 1 người quản lý trực tiếp.
Vùng dưới-phải không đồng nhất: 1 người giám sát và 4 người quản lý con.
Tổng cộng: (gốc) nhân sự.
Giới hạn:
Subtask #1 (20% số điểm): .
Subtask #2 (10% số điểm): Đội hình trên sân chỉ toàn một màu duy nhất với .
Subtask #3 (30% số điểm): .
Subtask #4 (40% số điểm): Không có ràng buộc bổ sung ().
