시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 21 19 18 94.737%

문제

You are implementing a vision program for a robot. Each time the robot camera takes a picture, it is stored as a black and white image in the robot's memory. Each image is an $H \times W$ grid of pixels, with rows numbered $0$ through $H-1$ and columns numbered $0$ through $W-1$. There are exactly two black pixels in each image, and all other pixels are white.

The robot can process each image with a program consisting of simple instructions. You are given the values of $H$, $W$, and a positive integer $K$. Your goal is to write a procedure to produce a program for the robot that, for any image, determines whether the distance between the two black pixels is exactly $K$. Here, the distance between a pixel in row $r_1$ and column $c_1$ and a pixel in row $r_2$ and column $c_2$ is $|r_1-r_2|+|c_1-c_2|$. In this formula $|x|$ denotes the absolute value of $x$, which equals $x$ if $x \geq 0$ and equals $-x$ if $x \lt 0$.

We now describe how the robot works.

The robot's memory is a sufficiently large array of cells, indexed from $0$. Each cell can store either $0$ or $1$ and its value, once set, will not be changed. The image is stored row by row in cells indexed $0$ through $H \cdot W - 1$. The first row is stored in cells $0$ through $W-1$, and the last row is stored in cells $(H - 1) \cdot W$ through $H \cdot W - 1$. In particular, if the pixel in row $i$ and column $j$ is black, the value of cell $i\cdot W + j$ is $1$, otherwise it is $0$.

A robot's program is a sequence of instructions, which are numbered with consecutive integers starting from $0$. When the program is run, the instructions are executed one by one. Each instruction reads the values of one or more cells (we call these values the instruction's inputs) and produces a single value equal to $0$ or $1$ (we call this value the instruction's output). The output of instruction $i$ is stored in cell $H\cdot W + i$. The inputs of instruction $i$ can only be cells that store either pixels or outputs of previous instructions, i.e. cells $0$ to $H \cdot W + i - 1$.

There are four types of instructions:

• NOT: has exactly one input. Its output is $1$ if the input is $0$, otherwise its output is $0$.
• AND: has one or more inputs. Its output is $1$ if and only if all of the inputs are $1$.
• OR: has one or more inputs. Its output is $1$ if and only if at least one of the inputs is $1$.
• XOR: has one or more inputs. Its output is $1$ if and only if an odd number of the inputs are $1$.

The output of the last instruction of the program should be $1$ if the distance between the two black pixels is exactly $K$, and $0$ otherwise.

구현

You should implement the following procedure:

void construct_network(int H, int W, int K)
• $H, W$: dimensions of each image taken by the robot's camera
• $K$: a positive integer
• This procedure should produce a robot's program. For any image taken by the robot's camera, this program should determine whether the distance between the two black pixels in the image is exactly $K$.

This procedure should call one or more of the following procedures to append instructions to the robot's program (which is initially empty):

• Append a NOTANDOR, or XOR instruction, respectively.
• $N$ (for add_not): the index of the cell from which the appended NOT instruction reads its input
• $Ns$ (for add_andadd_oradd_xor): array containing the indices of the cells from which the appended ANDOR, or XOR instruction reads its inputs
• Each procedure returns the index of the cell that stores the output of the instruction. The consecutive calls to these procedures return consecutive integers starting from $H \cdot W$.

The robot's program can consist of at most $10\,000$ instructions. The instructions can read at most $1\,000\,000$ values in total. In other words, the total length of $Ns$ arrays in all calls to add_andadd_or and add_xor plus the number of calls to add_not cannot exceed $1\,000\,000$.

After appending the last instruction, procedure construct_network should return. The robot's program will then be evaluated on some number of images. Your solution passes a given test case if for each of these images, the output of the last instruction is $1$ if and only if the distance between the two black pixels in the image is equal to $K$.

The grading of your solution may result in one of the following error messages:

• Wrong Answer [3]: your procedure attempted to add more than $10\,000$ instructions.
• Wrong Answer [4]: the instructions read more than $1\,000\,000$ values in total.

예시

Assume $H=2$, $W=3$, $K=3$. There are only two possible images where the distance between the black pixels is $3$.

• Case 1: black pixels are $0$ and $5$
• Case 2: black pixels are $2$ and $3$

A possible solution is to build a robot's program by making the following calls:

1. add_and([0, 5]), which adds an instruction that outputs $1$ if and only if the first case holds. The output is stored in cell $6$.
2. add_and([2, 3]), which adds an instruction that outputs $1$ if and only if the second case holds. The output is stored in cell $7$.
3. add_or([6, 7]), which adds an instruction that outputs $1$ if and only if one of the cases above holds.

제한

• $1 \leq H \leq 200$
• $1 \leq W \leq 200$
• $2 \leq H \cdot W$
• $1 \leq K \leq H+W-2$

서브태스크

번호 배점 제한
1 10

$\max(H, W) \leq 3$

2 11

$\max(H, W) \leq 10$

3 11

$\max(H, W) \leq 30$

4 15

$\max(H, W) \leq 100$

5 12

$\min(H, W)=1$

6 8

Pixel in row $0$ and column $0$ is black in each image.

7 14

$K=1$

8 19

출처

• 문제를 만든 사람: Danylo Mysak

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

• 예제는 채점하지 않는다.