Problem F
Decisions, Decisions
Let
A BDD is a rooted binary tree such that all internal
vertices
![\includegraphics[width=0.6\textwidth ]{bdd_v2.pdf}](/problems/decisions/file/statement/en/img-0001.png)
Given input
-
let
be the root vertex -
let
-
while
is not a leaf do-
replace
with the child vertex of by traversing the edge labelled -
increase
by
-
-
output the label of leaf vertex
Consider the function
A BDD is minimal if there is no way to replace any
subtree of an internal vertex of the BDD by a single leaf
vertex to get a new BDD defining the same boolean function. The
BDD depicted above is minimal. It is a fact that for each
boolean function
In this problem, you are given an
Input
The first line of input consists of a single integer
We think of these values as being indexed from
The third sample input below corresponds to the BDD depicted above.
Output
Output consists of a single integer
Sample Input 1 | Sample Output 1 |
---|---|
2 1 1 0 1 |
5 |
Sample Input 2 | Sample Output 2 |
---|---|
2 0 0 0 0 |
1 |
Sample Input 3 | Sample Output 3 |
---|---|
3 1 0 1 0 1 1 1 0 |
7 |