BOJ 12704 Cheating a Boolean Tree (Large)

문제 링크:

문제 내용

$M$개의 노드로 이루어진 논리 회로가 주어집니다. 이 논리 회로는 이진 트리 모양으로, 1부터 $M$까지 각 노드에 번호를 매겼을 때 $\frac{M-1}{2}$번 이하의 노드는 논리 게이트이고, 나머지 노드는 입력 노드입니다. $x$번 논리 게이트는 $2x$번과 $2x+1$번 노드를 입력으로 받습니다.

각 게이트는 AND 또는 OR 게이트입니다. 당신은 이 논리 회로에서 몇 개의 게이트를 골라 AND를 OR로, 또는 OR를 AND로 바꿀 수 있습니다.

이때, 최종 출력값이 $V$가 되도록 하기 위해 바꿔야 하는 게이트의 최소 개수를 구하세요. 이미 최종 출력값이 $V$라면 답은 0입니다.

입력

첫 번째 줄에 테스트 케이스의 개수 $N$이 주어집니다. ($2 \le N \le 20$)

각 테스트 케이스에 대해, 첫 줄에 $M$과 $V$가 주어집니다. ($3 \le M \le 9999$, $0 \le V \le 1$)

다음 $\frac{M-1}{2}$개의 줄에 걸쳐서, 1번부터 $\frac{M-1}{2}$번 노드의 정보가 $G$와 $C$의 두 값으로 주어집니다. ($0 \le G, C \le 1$) $G$가 1이면 AND, 0이면 OR 게이트이고, $C$가 1이면 이 게이트를 바꿀 수 있음, 0이면 바꿀 수 없음을 의미합니다.

다음 $\frac{M+1}{2}$개의 줄에 걸쳐서, $\frac{M+1}{2}$번 노드부터 $M$번 노드까지의 입력 노드의 값이 주어집니다.

출력

각 테스트 케이스에 대해, Case #{테스트 케이스 번호}: {문제의 정답}의 형식으로 출력합니다. 게이트를 어떻게 바꾸더라도 출력값을 $V$로 만들 수 없다면 문제의 정답 대신 IMPOSSIBLE을 출력합니다.

문제 풀이