VM15SWAP - Đổi chỗ

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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 ( 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á 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 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ó 1 ≤ M , N ≤ 1000
  • Trong 40% test (tương ứng với 40% số điểm), 1 ≤ M , N ≤ 20
  • 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 .

  • Người up: voj
  • Nguồn bài: VM15 - Lê Yên Thanh