Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VM15SWAP - Đổi chỗ

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274855/problem/E
https://codeforces.com/group/FLVn1Sc504/contest/272945/problem/E

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 ij cho nhau còn swapRow(i, j) sẽ đổi chỗ 2 hàng ij cho nhau. Ta có hàm valid(x1, y1, x2, y2), hàm này sẽ trả về true nếu hình chữ nhật có góc trái trên là (x1, y1) và góc phải dưới là (x2, y2) 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ị x0 + y0 lớn nhất sao cho valid(1, 1, x0, y0) = true.

Yêu cầu: Tìm cách thực hiện 2 loại thao tác trên không quá 105 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 MN.
  • 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 x0, y0
    • 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ó 1M, N ≤ 1000
  • Trong 40% test (tương ứng với 40% số điểm), 1M,N20
  • Trong quá trình thi, bài của bạn chỉ được chấm với 2 test ví dụ. Nếu được chấm đúng, kết quả sẽ được hiện là 100.

Ví dụ

Input 1:
3 3
0 1 1
1 1 0
1 1 1
Output 1
1 3
1
R 1 3
Input 2
3 1
0
1
1
Output 2
0 0

Giải thích

Ở ví dụ 1, ta sẽ tiến hành đảo 2 hàng 1 và 3 cho nhau.

0 1 1  ->  1 1 1

1 1 0  ->  1 1 0

1 1 1  ->  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.

=> valid(1, 1, 1, 3) = true.

  • Hình chữ nhật này sẽ cho ra tổng x0 y0 (= 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ị > max(3, 1) = 3.

Nên kết quả xuất ra là 0 0.


Được gửi lên bởi:VOJ Team
Ngày:2015-07-29
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC
Nguồn bài:VM15 - Lê Yên Thanh

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.