PRLOVE - Expected Time to Love

no tags 

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