Ciel and Earthquake
All submissions for this problem are available.
The country in which Chef Ciel lives has many earthquakes.
Since Ciel's restaurant is far away from an evacuation center, Ciel is afraid of earthquakes.
So, Ciel would like to know the probability that Ciel can reach from Ciel's restaurant to the evacuation center when an earthquake occurs.
Your task is calculating the probability under the following assumptions.
Ciel's city has R*C junctions (i, j) for 1 ≤ i ≤ R, 1 ≤ j ≤ C.
There is a two-way road between the junctions (r1, c1) and (r2, c2) if and only if |r1 - r2| + |c1 - c2| = 1.
When an earthquake occurs, each road is destroyed with probability p, and these events are statistically independent of each other.
Ciel's restaurant is in the junction (1, 1), and the evacuation center is in the junction (R, C).
Ciel only considers a big earthquake, so you can assume that p is not less than 0.1.
The first line contains an integer T, the number of test cases.
Then T test cases follow.
Each test case has 3 numbers R, C and p, where R and C are integers.
For each test case output the required probability.
Your answer must have an absolute error no more than 0.000001 (10-6).
1 ≤ T ≤ 50
1 ≤ R ≤ 8
1 ≤ C ≤ 1000000000000000000 (1018)
0.1 ≤ p ≤ 1
p has at most four digits after the decimal point.
5 2 2 0.5 3 2 0.7 2 3 0.7 1 1 0.2 7 7 0.8
0.4375 0.0768204 0.0768204 1 0.000003962379607
|Tags||hard, laycurse, march12|
|Time Limit:||0.88149 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.