이 문제에서는 진리트리라고 부르는 이진트리를 하나 정의한다. 진리트리란 마지막 행만 제외하고는 모두 완전한 트리이며 마지막 행에서도 왼쪽 노드에서부터 차례대로 채워져 있다. 또한 모든 노드의 자식의 수는 0 또는 2이다.

이러한 트리가 진리트리라고 불리는 이유는 각 노드마다 0 또는 1의 값을 가지기 때문이다. 또한 내부 노드는 AND/OR 게이트를 포함한다. 어떤 노드가 AND 게이트를 가지고 있다면 두 개의 자식노드의 AND값을 갖게 되고 OR 게이트를 가지고 있다면 두 자식노드의 OR값을 갖게 되는 것이다.

우리는 이 트리의 루트(가장 맨 위에 위치한 노드)값에 흥미가 있다. 진리 트리이기 때문에 당연히 루트값도 0 또는 1일 것이다. 하지만 이 트리로부터 우리가 원하는 루트값을 얻지 못할 수도 있다. 운좋게도 당신에게는 진리 트리의 어떤 노드들은 AND/OR 게이트를 변경할 수 있다는 사실을 알고 있었다.

진리트리의 정보와 변경 가능한 내부노드의 정보가 입력으로 주어질 때 최소한의 게이트 변경을 통하여 당신이 원하는 루트값을 얻고자 한다. 만약 불가능하다면 "IMPOSSIBLE"을 출력한다.

#1055 upload 46 done 13 how_to_reg 12

진리트리 timer 1s memory 128MB

#1055

진리트리 1s 128MB