BPRED - Branch Prediction

no tags 

As most of you might already know, the Intel-class hi-tech processors of today do a series of parallel tasks to help speedup instruction execution. The most complicated of those tasks is branch prediction. Since the instruction chunks on a modern processor are broken down into independent chunks and executed for a speed up, there is always a requirement to predict what branch an execution path will take (before the actual operands required for the condition to be evaluated to select the branch, are available). This complex task, is not addressed to fullest level today, but heuristics (as always) have helped.

The task we are going to consider now is much more simple compared to the actual branch prediction task. For our modelling, let us suppose that every instruction has the following syntax:

    <current-label> <branched-label>

All labels are strings of letters only. Labels are case-sensitive.

Moreover the probability that a certain branch will be taken is P (it is equal for all branches). If a branch is taken, the point of execution (control) goes to the branched-label. Otherwise the next statement in that order is executed. Control starts at the "start" (lowercase) label and control ends at the "end" (lowercase) label. The branch-label of start and end are themselves, and when start is executed, the control goes to the next instruction, and when end is executed, processing ends, with 100% probability. The last statement in the program is always an “end”.

It is required to find the expected number of times a statement executes.

Input

T – the number of test cases;
For each test case:
1st line contains one integer N (the number of lines to follow), one real P and one label L.
Each of the N lines that follow consist of instructions (two labels).

Output

For each test case, output one line containing:
"Expected number of times label L is executed is R",
where L - is the label given in the input
R - is the number of times the label is expected to be executed. It must be printed with exactly five decimal places.

Constraints:
T <= 20
3 <= N <= 120.
P lies between 0.01 and 0.99, i.e. no jump is 100% sure.
Also you can assume no label occurs on the jump side, without being defined throughout the program.
Each label is less than 10 characters in length.
Also each line has a distinct label associated with it.

Example

Input:
3
5 .5 B
C start
start start
B C

D C
end end
5 .99 C
start start
A B
B A

C end
end end
3 .5 label
start start
label label
end end

Output:
Expected number of times label B is executed is 4.00000
Expected number of times label C is executed is 1.00000
Expected number of times label label is executed is 2.00000

hide comments
SccsAtmtn: 2012-04-03 07:16:46

Why the answer of test 1 is 4.00000?I think it should be 15.00000.

Last edit: 2012-04-04 00:51:41
ASEMBL: 2010-11-10 10:20:55

the "start" can appears twice

:D: 2010-07-07 05:05:23

Long double should be used for any "non-integer" problem. Using float often results in WA because of lack of precision.

Last edit: 2010-07-21 13:32:59
刘启鹏: 2010-06-15 08:02:02

long double is recommended

:D: 2010-05-08 20:27:48

The expected value as fromalized in probability theory:
http://en.wikipedia.org/wiki/Expected_value

蓝细菌: 2010-02-11 01:33:30

what's the meaning of "the number of times the label is expected to be executed"?


Added by:Prasanna
Date:2006-01-13
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource: ByteCode '06