로봇 회로를 구현하던 중 몇 가지 이상 현상을 발견했습니다. 로봇이 실행할 수 있는 프로그램은 $0$부터 $N-1$까지 번호가 매겨진 $N = 128$개가 있습니다. 일반적으로는 어느 순간에나 단 하나의 프로그램만 실행되어야 합니다. 그러나 알 수 없는 이유로 가끔 정확히 세 개의 프로그램이 동시에 실행되기도 합니다. 다행히 숙련된 프로그래머로서 당신은 이러한 상황을 처리하는 방법을 알고 있으며, 이러한 이상 현상을 감지하는 회로를 구현하기로 했습니다.
먼저 $N$개의 입력을 생성합니다. $i$번째 프로그램이 실행 중이지 않으면 $i$번째 입력은 $0$이고, 실행 중이면 $1$입니다. 그런 다음 $N$부터 시작하여 연속적으로 번호가 매겨진 게이트를 추가합니다. 각 게이트는 일정 개수의 입력을 받아 $0$ 또는 $1$인 단일 출력을 생성합니다. $i$번째 게이트의 입력은 $i$보다 작은 번호를 가진 게이트의 출력이나 초기 $N$개의 입력 중 하나가 될 수 있습니다.
게이트에는 세 가지 종류가 있습니다.
NOT: 정확히 하나의 입력을 받습니다. 입력이 $0$이면 출력은 $1$이고, 그렇지 않으면 $0$입니다.OR: 정확히 두 개의 입력을 받습니다. 두 입력이 모두 $0$이면 출력은 $0$이고, 그렇지 않으면 $1$입니다.AND: 정확히 두 개의 입력을 받습니다. 두 입력이 모두 $1$이면 출력은 $1$이고, 그렇지 않으면 $0$입니다.
마지막 게이트의 출력은 이상 현상이 감지되었을 때, 즉 처음 $N$개의 입력 중 정확히 세 개가 $1$일 때 $1$이어야 하며, 처음 $N$개의 입력 중 정확히 하나가 $1$일 때 $0$이어야 합니다.
처음 $N$개의 입력 중 $1$의 개수는 정확히 하나 또는 정확히 세 개임이 보장됩니다.
구현 세부사항
$\color{red}{N = 128}$에 대한 올바른 회로를 설명하는 출력 파일을 작성해야 합니다.
출력의 첫 번째 줄에는 사용된 게이트의 수를 나타내는 정수가 포함되어야 합니다.
나머지 출력의 각 줄은 다음 세 가지 형식 중 하나여야 합니다.
NOT in_1 OR in_1 in_2 AND in_1 in_2
각 줄은 각각 NOT, OR, AND 게이트를 추가합니다. NOT의 경우 in_1은 게이트 입력의 인덱스입니다. OR와 AND의 경우 in_1과 in_2는 게이트 입력의 인덱스입니다. 첫 번째 줄 이후 $i$번째 줄에 추가된 게이트의 인덱스는 $N-1 + i$입니다.
전체 게이트 수는 $1024$를 초과할 수 없습니다. 즉, 출력 파일의 총 줄 수는 $1025$를 초과할 수 없습니다.
서브태스크
- (100점) 추가 제한 없음.
채점
각 서브태스크에 대해 회로가 통과하지 못하는 사례가 존재하면 점수는 $0$점이 됩니다.
그렇지 않은 경우, 회로에서 사용된 게이트 수를 $K$라고 합니다. 점수는 $f(K) \times$ [서브태스크 점수]가 되며, 여기서 $f(K)$는 다음과 같습니다.
$$f(K) = \begin{cases} 0 & 1024 < K \\ 0.3 - 0.1 \times \frac {K - 384}{896} & 384 < K \le 1024 \\ 0.6 - 0.3 \times \frac {K - 256}{128} & 256 < K \le 384 \\ 1 - 0.40 \times \frac{K - 215}{41} & 215 < K \le 256 \\ 1 & K \le 215 \end{cases}$$
그림 1: 각 K 값에 대한 작업 점수
솔루션을 1.out 출력 파일에 작성한 다음, 출력 파일들을 하나의 .zip 파일로 압축하여 제출해야 합니다.
예제
$N = 4$인 단순화된 버전의 작업을 고려해 봅시다 ($N = 128$에 대한 솔루션만 제공하면 됨에 유의하십시오). 가능한 솔루션 중 하나는 다음과 같은 회로를 구성하는 것입니다.
입력 1
3 OR 0 1 OR 2 3 AND 4 5
출력 1
(이 예제는 회로의 구조를 설명하며, 실제 출력은 N=128에 대한 회로여야 합니다.)
참고
이 회로는 다음과 같습니다.
- 입력 $0$ 또는 $1$ 중 적어도 하나가 $1$이면 $1$을 출력하는 게이트 $4$;
- 입력 $2$ 또는 $3$ 중 적어도 하나가 $1$이면 $1$을 출력하는 게이트 $5$; 그리고
- 게이트 $4$와 게이트 $5$의 출력이 모두 $1$이면 $1$을 출력하는 게이트 $6$.
모든 가능한 입력에 대해 회로가 올바른 답을 제공함을 확인할 수 있습니다.