진리트리 > 문제은행

본문 바로가기


문제은행

1055 : 진리트리

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 8 회    시도횟수: 21 회   



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

 

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

 

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

 

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


입력의 첫번째에는 정수 M(1<=M<=10,000) V가 공백을 사이에 두고 입력된다. M은 트리의 노드의 개수를 뜻하며 V는 만들고자 하는 루트의 값을 뜻한다. 그 다음 M개의 줄에는 트리내의 M개의 노드를 뜻하며 1번 노드부터 M번 노드까지 순서대로 입력이 들어온다. 여기서 루트 노드의 번호는 1번이다. 처음 (M-1)/2개의 줄에는 2개의 정수가 입력되는데 하나는 게이트의 종류(0일 경우 OR 1일 경우 AND)와 해당 게이트를 변경 가능한지여부를 나타내는 숫자(0일 경우 변경 불가 1일 경우 변경 가능)를 나타낸다. X번 노드의 자식은 2 * X번 노드와 2 * X + 1 번 노드이다. 그리고 그 다음 (M+1)/2 줄에는 맨 아래에 위치한 끝단 노드(leaf-node)에 할당된 값(1혹은 0)이 입력된다.



루트 노드의 값을 V로 만들 수 있는 경우에 최소 게이트 변경 횟수를 출력한다. 만약 불가능할 경우 "IMPOSSIBLE"을 출력한다.


[Copy]
9 1
1 0
1 1
1 1
0 0
1
0
1
0
1
[Copy]
1



출처 : GCJ 2008 R2


GCJ 2008 R2 A_Cheating a Boolean Tree

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.