Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3343
Accident Tree

Time Limit: 1 Second      Memory Limit: 32768 KB

Yesterday, our training room 218 caught fire! One of the electric outlets suddently burnt when all of our intelligent zju programmers were focusing on training. Luckily, due to the quick response, the small fire was handled on time, nobody was hurt.

As a curious and clever person, you are eager to know why this fire happened. You hire little Frozen to work for you. After careful study, Frozen draws an accident tree, and give it to you in his specific XML style file.

An accident tree is a tree whose leaf presents a cause of the accident and the probability of that cause will happen. The intermediate nodes in the tree means the relation of the causes, we call the intermediate node "event". To simplify the problem, we only consider the "and relation" and "or relation". "and relation" means the event will happen when and only when all the son events happen, "or relation" means the event will happen when and only when some son event happens. We say an accident happens when and only when the top(the root of the tree) event happen. A simple accident tree is as the graph below.

The XML file which Frozen was used to present the tree is defined as below:

	Root := <root><value></value>List</root>
	List := Node | Leaf | List List
	Node := <node><value></value>List</node>
	Leaf := <leaf><name></name><probability></probability></leaf>

which means:

  1. The content of the tree is always between the tag <root> and </root>
  2. The content between <value> and </value> is "and" or "or" only, which present the node's relation.
  3. The information of an intermediate node is included between tag<node> and </node>, it can be nested.
  4. The leaf of the tree is presenting as:
    where p is a real number with range [0,1].

Now given the XML representation of the accident tree, your task is to calculate the probability that the accident will happen.


There are multiple test cases. Each test case is an XML style file as the description described, ends with a single line "###"("###" will never be a name of the cause of an accident).

The name of the cause is a string which contains only lower-case letters and '_' and does not contain any spaces. The maximum length of the name is 32 character. There are at most 10 different causes of an accident and at most 200 nodes in the corresponding accident tree.

It is guaranteed that the XML file is valid and the same cause has the same the probability of occurrence and occurs at the same time. The height of the accident tree is less than 8.


For each test case, output a line containing the probability that the accident will happen(accurate to three fractional digits).

Sample Input


Sample Output



This XML file describes the graph in the description. From the accident tree, we know that there are 3 causes of this accident, we donate them as {aging_lines,someone_sets_fire,weather_too_hot}. Thus 8 situations will happen, they are {0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}, where 0 means doesn't happen and 1 means happens. And from the accident tree, we know that {1,1,0},{0,1,0},{0,0,1},{1,0,1},{0,1,1},{1,1,1} will cause the top event, so the probability of occurrence we want is 0.7*0.01*0.5+0.3*0.01*0.5+0.3*0.99*0.5+0.7*0.99*0.5+0.3*0.01*0.5+0.7*0.01*0.5=0.505.

Author: FU, Changlin
Contest: ZOJ Monthly, June 2010
Submit    Status