Day 1 Question 3

Porous Stone

Input file: probc.in

Output file: probc.out

The following can be viewed as modeling the diffusion of a liquid (e.g. some toxic substance) through a porous medium (e.g. the ground) and asking whether it will reach some region (e.g. the water supply). However, we will simplify the presentation and pose the problem in just two dimensions.

We are given a (2k+1) by (2k+1) grid, say (G[i,j]: i=-k...k, j=-k...k). You are to write a program to determine by simulation, the probability that the boundary can be reached from the starting point (0,0). This is done by doing t trials, counting the number that succeed in reaching the boundary, and then dividing this by t to find the probabilty of escape. A boundary point is any point G[i,j] such that either i or j is k or -k.

On any one trial, the probability that there is a gap between a grid point (i,j) and its neighbour (i+1,j) is determined by p and this probability stays constant for one trial. This is also true for the other three neighbours of point (i,j). The value for p is to be input but the probability of a gap will be generated by a random number generator.

Note: Efficiency is of some concern here and re-initializing the grid for each trial may be too costly. Programs will only be allowed to run for 2 minutes.

Input

The input file will begin with a line containing a single positive integer, n, the number of cases to be run. This will be followed by n sets of 3 lines, each containing one value:
first -
k, a positive integer giving the grid size as (2k+1) by (2k+1)
second -
p, a real value giving the probability of being able to make a given move,
third -
t, a positive integer giving the number of trials to be run.

Output

Your output should consist of n lines of the form

where k, p, and t are as defined above, and esc is the proportion of trials that led to an escape, that is the probability of escape. You should give the value of esc to two decimal places.

Sample input

1
10
0.45
100

Possible Output for Sample Input

10 0.45 100 0.47

Note: If you run your program several times with the data given above, you would not expect to get exactly the same value of esc for each run.