Problemas
셰릴은 논리 회로 설계 수업에서 디지털 신호(0과 1의 서열)를 생성하는 장치를 설계하라는 과제가 나왔다.
며칠을 밤새서 셰릴은 아래 그림1 처럼 완전 이진트리와 비슷한 모양새를 띄고 있는 부울회로를 완성 할 수 있었다. 트리 상의 모든 노드는 자신의 자식(직접 연결 되어 있는 하부 노드)를 입력 삼아, 자신의 부모(직접 연결되어 있는 상위 노드)에게 주어진 연산을 하여 출력을 넘겨주는 부울 연산 유닛(BAU)이다.
BAU의 입력은 1혹은 0이며, 출력은 노드에 할당 되어 있는 연산의 형식이 ∨인지 ∧인지에 따라 결정된다. 오른쪽 아래의 그림은 2개의 연산 형식에 대한 진리표를 뜻한다. 셰릴의 회로에서의 INPUT은 가장 낮은 레벨의 BAU 노드들을 뜻하고, OUTPUT은 BAU의 가장 높은 레벨의 BAU노드를 뜻한다.
과제를 완성하기 위해서 셰릴은 원하는 신호를 출력하기 위해 INPUT을 수동으로 설정해야 한다. 예를 들어, 셰릴의 회로가 그림 1과 같고, (0,0,0,1,1,1)이 출력되기를 원하면, INPUT은 다음과 같이 설정 되어야 한다: (0,0,0,0) -> (0,0,1,1) -> (1,1,0,0) -> (1,1,1,1) -> (1,0,1, 0) -> (0,1,0,1) 하지만 이 경우에 셰릴이 INPUT을 14번(2+4+2+2+4) 바꿔야 하기 때문에 너무 복잡하다(여기서 바꾼 다는 것은 해당 위치의 0을 1로, 1을 0으로 바꾸는 것을 뜻한다)! 따라서 조금 더 머리를 쓴 결과 (0,0,0,0)->(0,0,0,0)->(0,0,0,0)->(0,1,0,1)->(0,1,0,1)-> (0,1,0,1)로 하면 원하는 신호도 나오며 교환횟수는 2번(0+0+2+0+0)으로 줄어든다.
셰릴의 회로가 주어지고, 원하는 신호가 주어졌을 때, INPUT의 최소 교환횟수를 찾는 프로그램을 작성한다. 처음의 INPUT은 0으로 시작한다.
Entrada
입력의 처음은 정수 N(N≤10,000)으로 시작하는데, 셰릴의 회로에 입력되는 INPUT의 개수를 뜻한다. N은 2^k와 동일하며, k는 정수이다.
다음 줄에는 만들고자하는 신호가 입력되는데, 이는 0과 1로만 입력된다. 신호의 길이는 10,000을 넘지 않는다.
그 다음 줄부터 들어오는 N-1개의 숫자는 트리 내에서의 BAU의 형식을 뜻하는데, 0은 ∨, 1은 ∧을 뜻하며, 순서는 맨 윗단의 레벨(top level)부터 맨 아랫단의 레벨(bottom level)의 노드순이다. 입력되는 회로는 트리이며, 완전 이진 트리의 형태임을 유의하자.
Salida
최소의 교환 횟수를 출력한다.
Ejemplo
4
010101
0 0 0
5
Debes iniciar sesión para escribir código.