Cho ~1~ bảng ~M x N~ số ~0~ hoặc ~1~, các dòng và cột được đánh số từ trái sang phải, từ trên xuống dưới. Chỉ số của hàng hoặc cột đều bắt đầu từ ~1~.
Ta có ~2~ thao tác là ~swapCol(i, j)~ và ~swapRow(i, j)~ trong đó ~swapCol(i, j)~ sẽ đổi chỗ ~2~ cột ~i~ và ~j~ cho nhau còn ~swapRow(i, j)~ sẽ đổi chỗ ~2~ hàng ~i~ và ~j~ cho nhau. Ta có hàm ~valid(x_1, y_1, x_2, y_2)~, hàm này sẽ trả về true nếu hình chữ nhật có góc trái trên là ~(x_1, y_1)~ và góc phải dưới là ~(x_2, y_2)~ chỉ chứa toàn số ~1~, ngược lại sẽ trả về ~false~. Giá trị của một bảng bằng với giá trị ~x_0 + y_0~ lớn nhất sao cho valid ~(1, 1, x_0,y_0) = true~.
Yêu cầu: Tìm cách thực hiện ~2~ loại thao tác trên không quá ~10^{5}~ lần để sao cho bảng được tạo ra có giá trị lớn nhất và lớn hơn ~max(M, N)~.
Input
- Dòng ~1~: Chứa ~2~ số nguyên dương ~M~ và ~N~.
- ~M~ dòng tiếp theo: mỗi dòng chứa ~N~ số ~0~ hoặc ~1~.
Output
Nếu không đưa được bảng về giá trị lớn hơn max (~M~, ~N~), in ra ~2~ số ~0 0~.
Nếu đưa được bảng về giá trị lớn hơn max (~M~, ~N~) thì in ra như sau:
Dòng ~1~: ~2~ số nguyên dương ~x_0, y_0~
Dòng ~2~: Số nguyên ~K~ là số thao tác thực hiện
~K~ dòng sau ghi ra thao tác thực hiện dưới dạng
- "~R~ ~i~ ~j~": thực hiện phép ~swapRow(i, j)~
- "~C~ ~i~ ~j~": thực hiện phép ~swapCol(i, j)~
Giới hạn
- Tất cả các test có ~1 \leq M~, ~N \leq 1000~
- Trong ~40\%~ test (tương ứng với ~40\%~ số điểm), ~1 \leq M~, ~N \leq 20~
Sample Input 1
3 3
0 1 1
1 1 0
1 1 1
Sample Output 1
1 3
1
R 1 3
Sample Input 2
3 1
0
1
1
Sample Output 2
0 0
Note
Ở ví dụ ~1~, ta sẽ tiến hành đảo ~2~ hàng ~1~ và ~3~ cho nhau.
~0 1 1 \rightarrow 1 1 1~
~1 1 0 \rightarrow 1 1 0~
~1 1 1 \rightarrow 0 1 1~
Sau khi thực hiện thao tác trên ta có:
- Hình chữ nhật có góc trái trên là (~1~, ~1~) và góc phải dưới là (~1~, ~3~) chỉ chứa toàn số ~1~.
~\rightarrow~ valid (~1~, ~1~, ~1~, ~3~) ~=~ true.
- Hình chữ nhật này sẽ cho ra tổng ~x_0 + y_0~ ~(= 1 + 3 = 4)~ là lớn nhất.
Nên ~4~ sẽ là giá trị của bảng sau khi đảo.
Trong ví dụ này ta sẽ không tìm được cách làm khác cho ra bảng có giá trị lớn hơn.
Ở ví dụ ~2~, vì không có cách biến đổi nào cho ra bảng với giá trị lớn hơn max(~3~, ~1~) ~= 3~.
Nên kết quả xuất ra là ~0~ ~0~.
Comments