PRLOVE - Expected Time to Love
Alice has a problem. She loves Bob but is unable to face up to him. So she decides to send a letter to Bob expressing her feelings. She wants to send it from her computer to Bob's computer through the internet.
The internet consists of $N$ computers, numbered from $1$ to $N$. Alice's computer has the number $1$ and Bob's computer has the number $N$.
Due to some faulty coding, the computers start behaving in unexpected ways. On recieving the file, computer $i$ will forward it to computer $j$ with probability $P_{ij}$. The time taken to transfer the file from computer $i$ to computer $j$ is $T_{ij}$.
Find the expected time before Bob finds out about Alice's undying love for him.
Note: Once the letter is recieved by Bob's computer, his computer will just deliver it to Bob and stop forwarding it.
Input
First line contains $T$, the total test cases.
Each test case looks as follows:
First line contains $N$, the total number of computers in the network.
The next $N$ lines contain $N$ numbers each. The $j$'th number on the $i$'th line is the value $P_{ij}$ in percents.
The next $N$ lines contain $N$ numbers each. The $j$'th number on the $i$'th line is the value $T_{ij}$.
Output
Output a single line with a real number - The expected time of the transfer.
Your output will be considered correct if each number has an absolute or relative error less than $10^{-6}$.
Constraints
$N \le 100$
$T \le 5$
For all $i$, $P_{i1} + P_{i2} + \ldots + P_{iN} = 100$
$P_{NN} = 100$
For all $i$, $j$, $0 \le T_{ij} \le 10000$
You can safely assume that from every computer, the probability of eventually reaching Bob's computer is greater than $0$.
Example
Sample Input: 2 4 0 50 50 0 0 0 0 100 0 0 0 100 0 0 0 100 0 2 10 0 0 0 0 0 0 0 0 0 0 0 0 0 2 99 1 0 100 10 2 0 0 Sample Output: 6.000000 992.000000
hide comments
akshay:
2018-05-23 09:10:29
@thomas underflow... log sum exp trick is your friend ... |
|
Thomas Dybdahl Ahle:
2017-12-16 23:55:08
Say you have a chain, where each computer has probability 1% of sending to the next computer, and 99% of sending to the first. Then the message would have to travel more than 100^100 times to get to Bob, in expectation. With the bounds on T, that means the answer can be as large as 10^204. Is that correct? Getting 10^-6 absolute precision on numbers that large is pretty difficult. Last edit: 2017-12-16 23:55:44 |
|
The Mundane Programmer:
2013-03-08 11:45:04
Can anyone explain test cases......
|
Added by: | Aditya |
Date: | 2013-02-03 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | BASH C C++ 4.3.2 CPP FORTRAN HASK JAVA PAS-GPC PAS-FPC PYTHON PYTHON3 PY_NBC RUBY SCALA WHITESPACE |
Resource: | ByteCode '13 |