Bạn đang xây dựng một ứng dụng cho điện thoại di động có màn hình đen trắng. Ứng dụng cần nhiều hình ảnh với các kích thước khác nhau. Thay vì lưu trữ các ảnh, bạn muốn tạo ra chúng bằng thư viện đồ họa của điện thoại.

Mỗi ảnh có dạng hình vuông gồm \(N\times N\) điểm ảnh, mỗi điểm có màu trắng hoặc đen. Khi bắt đầu vẽ một ảnh, có thể giả sử mọi điểm ảnh trên màn hình đều màu trắng. Tọa độ \(x\) tăng từ trái sang phải, tọa độ \(y\) tăng từ trên xuống dưới; các cột và hàng được đánh số bắt đầu từ \(1\).

Thư viện chỉ cung cấp thao tác XOR(L,R,T,B), đảo màu tất cả điểm ảnh thuộc hình chữ nhật có góc trên trái \((L,T)\) và góc dưới phải \((R,B)\), kể cả các biên: trắng thành đen và đen thành trắng. Các tham số \(L,R,T,B\) lần lượt là tọa độ biên trái, phải, trên và dưới. Chú ý thứ tự tham số này có thể khác với các thư viện đồ họa khác.

Cho trước một ảnh đích, hãy tạo ra ảnh đó từ màn hình trắng bằng ít thao tác XOR nhất có thể. Bạn được cung cấp các tệp đầu vào và cần nộp các tệp kết quả, không cần nộp mã nguồn chương trình tìm lời giải.

Dữ liệu vào

Có 10 ảnh trong các tệp xor1.in đến xor10.in, được cung cấp trong tệp đính kèm xor-inputs.zip. Trong mỗi tệp:

• Dòng đầu chứa \(N\), với \(5\le N\le 2000\).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên, mô tả ảnh đích theo thứ tự hàng. Giá trị \(0\) biểu thị màu trắng, \(1\) biểu thị màu đen.

Dữ liệu ra

Trong kỳ thi gốc, mỗi tệp xorI.in có một tệp kết quả tương ứng. Trên bản luyện tập này, chọn ngôn ngữ OUTPUT và nộp một tệp ZIP chứa 10 tệp kết quả ngay tại thư mục gốc của ZIP, không đặt trong thư mục con, theo ánh xạ sau:

Nội dung mỗi tệp giữ nguyên định dạng của kỳ thi gốc:

• Dòng đầu có dạng #FILE xor I, trong đó I là số thứ tự của tệp đầu vào.
• Dòng thứ hai chứa số thao tác \(K\).
• \(K\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(L,R,T,B\) của một thao tác, theo đúng thứ tự thực hiện.

Mỗi thao tác phải thỏa mãn \(1\le L\le R\le N\) và \(1\le T\le B\le N\).

Chẳng hạn, 01.out phải bắt đầu bằng #FILE xor 1, còn 10.out bắt đầu bằng #FILE xor 10. Số trong dòng #FILE là số bộ dữ liệu gốc từ 1 đến 10, không thêm số 0 ở đầu như trong tên tệp ZIP.

Chấm điểm

Bản luyện tập này sử dụng các mốc cố định lấy từ kết quả tốt nhất của IOI 2002. Với ảnh từ 1 đến 10, số thao tác mốc \(B\) lần lượt là 3, 34, 28, 122, 74, 481, 566, 200, 500, 810. Mỗi bộ kiểm tra có trọng số 1. Một lời giải hợp lệ dùng \(K>0\) thao tác nhận tỉ lệ điểm \(\min(1,(1+9B/K)/10)\); lời giải tốt hơn mốc vẫn chỉ nhận tối đa toàn bộ điểm của bộ đó. Tổng điểm được chuẩn hóa về thang 100 từ các tỉ lệ này, không áp dụng bước làm tròn từng ảnh đến một chữ số thập phân hay làm tròn tổng đến số nguyên của kỳ thi gốc. Nếu ảnh toàn trắng được tạo bằng 0 thao tác thì nhận toàn bộ điểm.

Mỗi ảnh được 0 điểm nếu ảnh tạo ra không đúng, số thao tác thực tế khác \(K\), \(K>40000\), hoặc có thao tác chứa tọa độ không hợp lệ. Cụ thể, các trường hợp \(L>R\), \(T>B\), tọa độ không dương hay lớn hơn \(N\) đều không hợp lệ.

Trong cách chấm tương đối của kỳ thi gốc, một kết quả hợp lệ được \(1+9\times B/K\) điểm, trong đó \(B\) là số thao tác ít nhất trong các lời giải hợp lệ của tất cả thí sinh cho cùng ảnh. Khi đó, điểm mỗi ảnh được làm tròn đến một chữ số sau dấu phẩy; tổng điểm của 10 ảnh được làm tròn đến số nguyên gần nhất. Đây là quy tắc lịch sử, được thay bằng cách chấm mốc cố định nêu trên trong bản luyện tập này.

Ví dụ, nếu bạn dùng 121 thao tác và đó là kết quả tốt nhất của các thí sinh, bạn được 10 điểm. Nếu kết quả tốt nhất dùng 98 thao tác, bạn được \(1+9\times98/121\), làm tròn thành \(8{,}3\) điểm.

Ví dụ

7
0 0 0 0 0 0 0
0 1 1 1 0 0 0
1 0 0 1 0 0 0
1 0 1 0 1 1 0
1 0 1 0 1 1 0
0 1 0 0 1 1 0
0 0 1 1 1 1 0

#FILE xor 0
3
2 4 2 6
3 6 4 7
1 3 3 5

Nguồn

Đề gốc IOI 2002. Tài liệu kỳ thi.