비전 프로그램

당신은 로봇의 비전 프로그램을 구현하고 있다. 로봇이 찍는 흑백 사진은 $H \times W$ 픽셀 격자이며 행은 $0$부터 $H-1$, 열은 $0$부터 $W-1$까지 번호가 붙는다. 각 사진에는 검은 픽셀이 정확히 두 개 있고 나머지는 흰색이다.

양의 정수 $K$가 주어진다. 두 검은 픽셀 $(r_1,c_1)$과 $(r_2,c_2)$ 사이의 거리를 $|r_1-r_2|+|c_1-c_2|$로 정의할 때, 이 거리가 정확히 $K$인지 판별하는 로봇 프로그램을 만들어야 한다.

로봇 메모리는 $0$부터 번호가 붙은 충분히 큰 셀 배열이다. 각 셀은 한 번 정해진 $0$ 또는 $1$을 저장한다. 사진은 행 순서대로 $0$번부터 $H\cdot W-1$번 셀에 저장된다. 픽셀 $(i,j)$가 검으면 셀 $i\cdot W+j$의 값은 $1$, 아니면 $0$이다.

로봇 프로그램은 $0$번부터 차례로 실행되는 명령의 수열이다. 명령 $i$의 출력은 셀 $H\cdot W+i$에 저장되며, 입력으로 픽셀 셀 또는 이전 명령의 출력만 사용할 수 있다. 명령 종류는 다음 네 가지다.

• NOT: 입력 하나가 $0$이면 $1$, 아니면 $0$을 출력한다.
• AND: 모든 입력이 $1$일 때만 $1$을 출력한다.
• OR: 적어도 한 입력이 $1$이면 $1$을 출력한다.
• XOR: 값이 $1$인 입력의 수가 홀수일 때만 $1$을 출력한다.

마지막 명령은 두 검은 픽셀의 거리가 $K$일 때만 $1$을 출력해야 한다.

구현 세부 사항

다음 함수를 구현해야 한다.

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

이 함수는 다음 함수들을 한 번 이상 호출하여 처음에는 비어 있는 프로그램에 명령을 추가해야 한다.

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

• add_not의 $N$은 입력 셀 번호다.
• 나머지 함수의 $Ns$는 입력 셀 번호 배열이다.
• 각 함수는 새 명령의 출력이 저장된 셀 번호를 반환한다. 반환 값은 $H\cdot W$부터 연속해서 증가한다.
• 프로그램은 최대 $10\,000$개 명령을 가질 수 있다.
• 모든 명령이 읽는 입력의 총수는 $1\,000\,000$ 이하여야 한다.

그레이더는 다음 오류를 보고할 수 있다.

• Instruction with no inputs: add_and, add_or, add_xor에 빈 배열을 전달했다.
• Invalid index: 올바르지 않은 셀 번호를 전달했다.
• Too many instructions: 명령을 $10\,000$개보다 많이 추가하려 했다.
• Too many inputs: 읽는 입력의 총수가 $1\,000\,000$을 넘었다.

예제

$H=2$, $W=3$, $K=3$이면 두 검은 픽셀 사이의 거리가 $3$인 사진은 두 가지뿐이다.

• 경우 1: 픽셀 $0$과 $5$가 검다.
• 경우 2: 픽셀 $2$와 $3$이 검다.

다음과 같이 프로그램을 만들 수 있다.

1. add_and([0,5])를 호출해 첫째 경우일 때만 $1$인 값을 셀 $6$에 저장한다.
2. add_and([2,3])을 호출해 둘째 경우일 때만 $1$인 값을 셀 $7$에 저장한다.
3. add_or([6,7])을 호출해 두 경우 중 하나일 때만 $1$을 출력한다.

제한

• $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점) 모든 사진에서 $(0,0)$ 픽셀이 검다.
7. (14점) $K=1$
8. (19점) 추가 제한이 없다.

• 첫째 줄: $H\;W\;K$
• 이어지는 각 줄: $r_1[i]\;c_1[i]\;r_2[i]\;c_2[i]$
• 마지막 줄: $-1$

• 각 사진에 대해 마지막 명령의 출력 값 $0$ 또는 $1$을 한 줄씩 출력한다.
• 그레이더는 각 사진 처리 후의 전체 메모리 값을 현재 디렉터리의 log.txt에도 기록한다.