PreVOI 2023 - Phú Thọ - Biến đổi

Xem dạng PDF

Gửi bài giải

Điểm: 30,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Cho hai bảng số ~A~ và ~B~ cùng kích thước ~n \times n~, các hàng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Mỗi phần tử của bảng chỉ nhận một trong ba loại giá trị ~1, -1, 0~. Xét hai loại phép biến đổi:

  1. Tác động vào hàng thứ ~i~ ~(1 \le i \le n)~ của bảng ~A~, tất cả các ô trên hàng ~i~ chứa số ~1~ biến đổi thành ~-1~, các ô chứa số ~-1~ biến đổi thành ~1~, các ô chứa số ~0~ không thay đổi;

  2. Tác động vào cột thứ ~j~ ~(1 \le j \le n)~ của bảng ~A~, tất cả các ô trên cột ~j~ chứa số ~1~ biến đổi thành ~-1~, các ô chứa số ~-1~ biến đổi thành ~1~, các ô chứa số ~0~ không thay đổi.

Yêu cầu: Hãy tìm cách biến đổi bảng ~A~ để nhận được bảng ~B~ với ít phép biến đổi nhất.

Input

  • Dòng đầu chứa số nguyên ~n~;

  • ~n~ dòng sau, mỗi dòng chứa ~n~ số nguyên mô tả bảng ~A~.

  • ~n~ dòng sau, mỗi dòng chứa ~n~ số nguyên mô tả bảng ~B~.

Output

Ghi ra một số nguyên duy nhất là số phép biến đổi ít nhất cần thực hiện, ghi -1 nếu không tồn tại cách biến đổi.

Scoring

Subtask Điểm Ràng buộc
1 ~20\%~ ~n \le 3~;
2 ~30\%~ ~n \le 10~;
3 ~20\%~ ~n \le 20~;
4 ~30\%~ ~n \le 100~.

Sample Input 1

2
1 -1
-1 1
-1 -1
-1 -1

Sample Output 1

2

Notes

Biến đổi hàng ~1~, sau đó biến đổi cột ~2~.


Bình luận

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


Không có bình luận tại thời điểm này.