Bạn đang cài đặt một chương trình thị giác cho một con robot. Mỗi lần camera của robot chụp một bức ảnh, bức ảnh được lưu dưới dạng ảnh đen trắng trong bộ nhớ của robot. Mỗi ảnh là một lưới điểm ảnh kích thước \(H \times W\), với các hàng được đánh số từ \(0\) đến \(H-1\) và các cột được đánh số từ \(0\) đến \(W-1\). Có chính xác hai điểm ảnh đen trong mỗi bức ảnh; tất cả các điểm ảnh còn lại đều màu trắng.

Robot có thể xử lý mỗi bức ảnh bằng một chương trình gồm các lệnh đơn giản. Bạn được cung cấp các giá trị \(H\), \(W\) và một số nguyên dương \(K\). Nhiệm vụ của bạn là viết một thủ tục tạo ra chương trình cho robot để, với bất kỳ bức ảnh nào, xác định xem khoảng cách giữa hai điểm ảnh đen có bằng chính xác \(K\) hay không.

Khoảng cách giữa điểm ảnh ở hàng \(r_1\), cột \(c_1\) và điểm ảnh ở hàng \(r_2\), cột \(c_2\) là

Trong công thức này, \(|x|\) biểu thị giá trị tuyệt đối của \(x\), bằng \(x\) nếu \(x \geq 0\) và bằng \(-x\) nếu \(x<0\).

Sau đây là cách thức hoạt động của robot.

Bộ nhớ của robot là một mảng đủ lớn gồm các ô nhớ được đánh số bắt đầu từ \(0\). Mỗi ô lưu trữ \(0\) hoặc \(1\); một khi đã được thiết lập, giá trị của ô không thay đổi nữa. Bức ảnh được lưu lần lượt theo từng hàng trong các ô từ \(0\) đến \(H \cdot W-1\). Hàng đầu tiên được lưu trong các ô từ \(0\) đến \(W-1\), còn hàng cuối cùng được lưu trong các ô từ \((H-1)\cdot W\) đến \(H\cdot W-1\). Cụ thể, ô \(i\cdot W+j\) có giá trị \(1\) nếu điểm ảnh ở hàng \(i\), cột \(j\) là màu đen, và có giá trị \(0\) nếu điểm ảnh đó là màu trắng.

Chương trình của robot là một dãy lệnh, được đánh số bằng các số nguyên liên tiếp bắt đầu từ \(0\). Khi chương trình chạy, các lệnh được thực hiện lần lượt. Mỗi lệnh đọc giá trị của một hoặc nhiều ô nhớ (gọi là dữ liệu đầu vào của lệnh) và tạo ra một giá trị duy nhất bằng \(0\) hoặc \(1\) (gọi là dữ liệu đầu ra của lệnh). Đầu ra của lệnh \(i\) được lưu trong ô \(H\cdot W+i\). Đầu vào của lệnh \(i\) chỉ có thể lấy từ các ô lưu điểm ảnh hoặc đầu ra của các lệnh trước đó, tức là các ô từ \(0\) đến \(H\cdot W+i-1\).

Có bốn loại lệnh:

Đầu ra của lệnh cuối cùng trong chương trình phải bằng \(1\) nếu khoảng cách giữa hai điểm ảnh đen bằng chính xác \(K\), và bằng \(0\) trong trường hợp ngược lại.

Chi tiết cài đặt

Bạn cần viết tệp vision.cpp, khai báo #include "vision.h" và cài đặt thủ tục sau. Trình chấm cung cấp hàm main.

void construct_network(int H, int W, int K);

• \(H\), \(W\): các chiều của mỗi bức ảnh được camera của robot chụp.
• \(K\): một số nguyên dương.
• Thủ tục này phải tạo ra chương trình cho robot để xác định, với bất kỳ bức ảnh nào được camera chụp, liệu khoảng cách giữa hai điểm ảnh đen có bằng chính xác \(K\) hay không.

Chương trình của robot ban đầu rỗng. Thủ tục construct_network phải gọi một hoặc nhiều hàm sau để thêm các lệnh vào cuối chương trình. Trong C++, các hàm được khai báo trong vision.h như sau:

int add_not(int N);
int add_and(std::vector<int> Ns);
int add_or(std::vector<int> Ns);
int add_xor(std::vector<int> Ns);

• Các hàm lần lượt thêm một lệnh NOT, AND, OR hoặc XOR.
• N (đối với add_not) là chỉ số ô nhớ mà lệnh NOT vừa thêm sẽ đọc làm đầu vào.
• Ns (đối với add_and, add_or, add_xor) là mảng chứa các chỉ số ô nhớ mà lệnh tương ứng vừa thêm sẽ đọc làm đầu vào.
• Mỗi hàm trả về chỉ số ô nhớ lưu đầu ra của lệnh vừa thêm. Các lời gọi liên tiếp đến những hàm này trả về các số nguyên liên tiếp bắt đầu từ \(H\cdot W\).

Chương trình của robot được có tối đa \(10\,000\) lệnh. Tổng số giá trị đầu vào mà tất cả các lệnh đọc được không vượt quá \(1\,000\,000\). Nói cách khác, tổng độ dài các mảng Ns trong mọi lời gọi add_and, add_or, add_xor, cộng với số lần gọi add_not, không được vượt quá \(1\,000\,000\).

Sau khi thêm lệnh cuối cùng, thủ tục construct_network phải kết thúc và trả quyền điều khiển cho trình chấm. Chương trình của robot sau đó được chạy trên một số bức ảnh. Bài nộp vượt qua một trường hợp kiểm thử nếu, với mỗi bức ảnh được kiểm tra, đầu ra của lệnh cuối cùng bằng \(1\) khi và chỉ khi khoảng cách giữa hai điểm ảnh đen bằng \(K\).

Quá trình chấm có thể trả về một trong các thông báo lỗi sau:

Ví dụ

Giả sử \(H=2\), \(W=3\), \(K=3\). Chỉ có hai bức ảnh mà khoảng cách giữa hai điểm ảnh đen bằng \(3\).

• Trường hợp 1: các điểm ảnh đen có chỉ số ô nhớ \(0\) và \(5\).
• Trường hợp 2: các điểm ảnh đen có chỉ số ô nhớ \(2\) và \(3\).

Một cách xây dựng chương trình cho robot là thực hiện lần lượt các lời gọi sau (viết theo cú pháp C++):

1. add_and({0, 5}): thêm lệnh có đầu ra bằng \(1\) khi và chỉ khi trường hợp thứ nhất xảy ra. Đầu ra được lưu trong ô \(6\).
2. add_and({2, 3}): thêm lệnh có đầu ra bằng \(1\) khi và chỉ khi trường hợp thứ hai xảy ra. Đầu ra được lưu trong ô \(7\).
3. add_or({6, 7}): thêm lệnh có đầu ra bằng \(1\) khi và chỉ khi một trong hai trường hợp trên xảy ra. Đây là lệnh cuối cùng của chương trình; đầu ra được lưu trong ô \(8\).

Các ràng buộc

• \(1 \leq H \leq 200\).
• \(1 \leq W \leq 200\).
• \(2 \leq H\cdot W\).
• \(1 \leq K \leq H+W-2\).

Giới hạn thời gian: \(1\) giây. Giới hạn bộ nhớ: \(1024\) MiB.

Các subtasks

Điểm của bài là tổng điểm các subtask vượt qua. Để nhận điểm của một subtask, bài nộp phải vượt qua tất cả các trường hợp kiểm thử của subtask đó. Nhóm kiểm thử mẫu có \(0\) điểm.

Trình chấm mẫu

Trình chấm mẫu trong gói đính kèm đọc dữ liệu đầu vào theo định dạng sau:

• Dòng \(1\): \(H\;W\;K\).
• Dòng \(2+i\) (\(i\geq 0\)): \(r_1[i]\;c_1[i]\;r_2[i]\;c_2[i]\).
• Dòng cuối cùng: \(-1\).

Mỗi dòng, trừ dòng đầu tiên và dòng cuối cùng, biểu diễn một bức ảnh có hai điểm ảnh đen. Gọi bức ảnh được mô tả ở dòng \(2+i\) là bức ảnh \(i\). Một điểm ảnh đen nằm ở hàng \(r_1[i]\), cột \(c_1[i]\); điểm ảnh đen còn lại nằm ở hàng \(r_2[i]\), cột \(c_2[i]\).

Trước tiên, trình chấm mẫu gọi construct_network(H, W, K). Nếu construct_network vi phạm một ràng buộc được mô tả trong đề, trình chấm mẫu in một trong các thông báo lỗi liệt kê ở cuối phần Chi tiết cài đặt rồi thoát.

Nếu không có lỗi, trình chấm mẫu tạo ra hai kết quả đầu ra.

Thứ nhất, trình chấm mẫu in đầu ra của chương trình robot theo định dạng:

• Dòng \(1+i\) (\(i\geq 0\)): đầu ra của lệnh cuối cùng trong chương trình robot đối với bức ảnh \(i\) (\(1\) hoặc \(0\)).

Thứ hai, trình chấm mẫu ghi tệp log.txt trong thư mục hiện tại theo định dạng:

• Dòng \(1+i\) (\(i\geq 0\)): \(m[i][0]\;m[i][1]\;\ldots\;m[i][c-1]\).

Dãy trên dòng \(1+i\) mô tả các giá trị trong bộ nhớ robot sau khi chương trình chạy với bức ảnh \(i\) làm đầu vào. Cụ thể, \(m[i][j]\) là giá trị của ô nhớ \(j\). Độ dài \(c\) của dãy bằng \(H\cdot W\) cộng với số lệnh trong chương trình robot.

Trong trình chấm mẫu được cung cấp, nếu một dòng mô tả ảnh có tọa độ nằm ngoài ảnh hoặc hai điểm ảnh trùng nhau, trình chấm in \(-1\) và ghi \(-1\) vào dòng tương ứng của log.txt, rồi tiếp tục đọc ảnh tiếp theo. Dòng chỉ chứa \(-1\) vẫn là dấu kết thúc dữ liệu đầu vào.

Dữ liệu mẫu trong gói đính kèm

Dữ liệu vào (examples/01.in):

2 3 3
0 0 0 1
0 0 0 2
0 0 1 0
0 0 1 1
0 0 1 2
0 1 0 2
0 1 1 0
0 1 1 1
0 1 1 2
0 2 1 0
0 2 1 1
0 2 1 2
1 0 1 1
1 0 1 2
1 1 1 2
-1

Dữ liệu ra của một chương trình robot đúng (examples/01.out):

0
0
0
0
1
0
0
0
0
1
0
0
0
0
0

Mẫu này liệt kê tất cả \(15\) cách chọn hai điểm ảnh đen trong ảnh \(2\times 3\). Chỉ ảnh thứ \(5\) và ảnh thứ \(10\) trong danh sách có khoảng cách giữa hai điểm ảnh đen bằng \(3\), tương ứng với hai trường hợp trong phần Ví dụ. Nội dung log.txt phụ thuộc vào chương trình robot mà bạn xây dựng.

Nguồn: Đề chính thức IOI 2019, ngày thi 2, bài Vision Program (vision), bản tiếng Việt; đối chiếu với bản Markdown, gói đính kèm và dữ liệu chấm do ban tổ chức cung cấp.