PreVOI Phú Thọ 2023 - Ngày 05/02

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 hai loại giá trị \(1\) hoặc \(-1\). Xét hai loại phép biến đổi:

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

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ữ liệu vào từ file văn bản CTAB.INP:
  • 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 file văn bản CTAB.OUT 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.

Example

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

2

Scoring

• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài thỏa mãn: \(n \leq 3\).
• \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thỏa mãn: \(n \leq 10\).
• \(20\%\) số test khác ứng với \(20\%\) số điểm của bài thỏa mãn: \(n \leq 100\).
• \(30\%\) số test còn lại ứng với \(30\%\) số điểm của bài thỏa mãn: \(n \leq 1000\).

Bài 5. Gặp gỡ (7 điểm)

Đất nước Z có \(n\) thành phố, các thành phố được đánh số từ \(1\) đến \(n\). Có đúng \(n-1\) con đường hai chiều nối giữa các thành phố thỏa mãn điều kiện: có thể đi từ thành phố bất kì đến tất cả các thành phố còn lại theo đường trực tiếp hoặc gián tiếp qua các thành phố khác. Đất nước Z thường có các sự kiện văn hóa lớn, mỗi lần sự kiện sẽ được tổ chức tại một thành phố, điều này ảnh hưởng tới chi phí di chuyển trên các con đường. Cụ thể, nếu thành phố \(u\) là thành phố tổ chức sự kiện văn hóa, khi đó các con đường hướng tới thành phố \(u\) sẽ có chi phí là \(a\) còn các con đường đi xa thành phố \(u\) sẽ có chi phí là \(b\). Con đường từ \(i\) tới \(j\) được gọi là hướng tới \(u\) nếu đường đi ngắn nhất từ \(i\) tới \(u\) dài hơn đường đi ngắn nhất từ \(j\) tới \(u\), ngược lại thì con đường từ \(i\) tới \(j\) được gọi là đi xa thành phố \(u\). Khi sự kiện văn hóa diễn ra, một người di chuyển qua con đường sẽ bị mất chi phí bằng tổng của từng lần di chuyển, lần di chuyển thứ \(k\) (\(1 \le k \le s\)) sẽ mất chi phí \(k \cdot \text{cost}_k\), trong đó \(\text{cost}_k\) bằng \(a\) hoặc \(b\) tùy thuộc lần di chuyển thứ \(k\) đi qua con đường hướng tới thành phố tổ chức sự kiện hay đi xa thành phố tổ chức sự kiện.

Một câu hỏi thường gặp ở đất nước Z là: nếu sự kiện văn hóa diễn tại thành phố \(u\), có hai người ở thành phố \(i\) và thành phố \(j\) thì chi phí nhỏ nhất để hai người gặp nhau tại một thành phố nào đó là bao nhiêu.

Yêu cầu: Cho thông tin về các con đường của đất nước Z và \(q\) câu hỏi, mỗi câu hỏi được mô tả bằng \(5\) số \(u, i, j, a, b\) cần trả lời chi phí nhỏ nhất để hai người gặp nhau.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\);
• \(n-1\) dòng sau, mỗi dòng chứa hai số nguyên mô tả con đường nối giữa hai thành phố;
• \(q\) dòng sau, mỗi dòng chứa năm số nguyên dương mô tả một câu hỏi.

Output

• Ghi ra file văn bản MEETING.OUT gồm \(q\) dòng, mỗi dòng là trả lời của câu hỏi trong dữ liệu vào.

Example

8 3
1 2
5 6
5 3
4 3
8 2
3 1
7 5
3 3 2 5 2
5 8 7 8 12
1 4 7 10 2

6
80
20

Scoring

• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài thỏa mãn: \(n, q \le 2000\);
• \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thỏa mãn: \(n, q \le 50000\) và các câu hỏi có \(u = 1\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm của bài thỏa mãn: \(n, q \le 50000\) và các câu hỏi có \(a = b\);
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài thỏa mãn: \(n, q \le 50000\).

Cho bảng kích thước \(n \times n\) (\(3 \le n \le 10\)). Các hàng và cột đều được đánh số từ \(1\) đến \(n\). Ban đầu mỗi ô có một quân bài; ô ở hàng \(i\), cột \(j\) chứa quân bài số \((i-1)\times n+j\).

Người quản trò thống nhất hai dãy số nguyên \(r_1,r_2,\ldots,r_5\) và \(c_1,c_2,\ldots,c_5\), rồi lấy ngẫu nhiên \(n^2-5\) quân bài khỏi bảng, nên trên bảng còn đúng \(5\) quân. Trong số các quân đã lấy, người quản trò chọn tiếp \(m\) quân bất kỳ (\(0 < m \le n^2-5\)), tráo ngẫu nhiên rồi xếp thành một dãy bài cho người chơi xem.

Người chơi thực hiện \(m\) lượt. Mỗi lượt diễn ra như sau:

• Người chơi chọn một quân bài đang có trên bảng rồi bỏ đi, nên bảng còn \(4\) quân.
• Người quản trò lấy quân đầu dãy và đặt lại vào vị trí ban đầu của nó trên bảng, nên bảng lại có \(5\) quân. Gọi \(x\) là số quân bài nhiều nhất cùng một hàng và \(y\) là số quân bài nhiều nhất cùng một cột. Điểm của lượt này là \(r_x+c_y\).

Hãy giúp người chơi đạt tổng điểm lớn nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(n,m\) (\(m \le 50\)).
• Dòng thứ hai chứa \(10\) số nguyên \(r_1,r_2,\ldots,r_5,c_1,c_2,\ldots,c_5\), đều không âm và không vượt quá \(10^6\).
• Dòng thứ ba chứa \(5\) số nguyên mô tả năm quân bài còn lại trên bảng sau khi người quản trò lấy bài ra.
• Dòng thứ tư chứa \(m\) số nguyên mô tả dãy bài sau khi người quản trò tráo.

Output

• In ra một số nguyên duy nhất là tổng điểm lớn nhất.

Example

3 2
0 2 3 0 0 0 1 3 0 0
1 2 5 6 7
9 3

9

Scoring

• \(30\%\) số điểm: \(n=3\).
• \(30\%\) số điểm: \(n \le 6\).
• \(20\%\) số điểm: \(n \le 7\).
• \(20\%\) số điểm: \(n \le 10\).