|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
Random Algorithms are very popular now. For example, it's widely used in cryptography (primality test and etc.).
Different from the normal definite algorithms, random algorithms may not have a definite running trace. Sometimes, it comes to some point, flips a coin, and decides where to go according to the result of the coin flipping.
The following command may be such a point:
x=random(1); // random(1) returns a random number from [0..1) uniformly
IF x > 0.3 GOTO ...
When the random program comes here, it generates a random number and assigns it to x, if x is greater than 0.3 it goes to somewhere; otherwise, it goes straight ahead. So, the program goes somewhat like a drunk man walking a long the street. You can't predict where the program should go beforehand.
Your task in this problem is to create a simple Random Program Evaluator, which can calculate the expected running time of some random algorithms.
A simple random program is described as follows:
The Evaluator takes one random program as input; return the expected runtime of some procedures upon requests, with an accuracy of 3 digits after the decimal point.
To make your lives easier, we have the following simplification:
The input file contains one random program described as above with one or more random procedures, and one or more requests. The requests are following the program. Each request is a line with one string, which is the name of the requested procedure. The request list ends with a line containing "REQUEST_END" (there is no procedure with a name as "REQUEST_END")
For each request, output a line with a number presents the expected running time of the requested procedure. The accuracy is up to 3 digits after decimal point.
PROG_START PROC A IF x>0.5 GOTO 3; NOP; END; PROC B IF x<0.5 PROC A; NOP; END; PROG_END B A REQUEST_END