PreVOI 2023 - Phú Thọ - Biến đổi
Xem dạng PDFTrong 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:
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;
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