Canadian Computing Competition: 1997 Stage 2, Day 1, Problem 3

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 \dots k, j=-k \dots 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 probability 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.

Input Specification

There will be ~3~ lines, each containing one value:

First, ~k~ ~(2 \le k \le 50)~, a positive integer giving the grid size as ~(2k+1)~ by ~(2k+1)~.

Second, ~p~ ~(0.0 \le p < 1.0)~, a real value giving the probability that there is a gap between ~2~ neighbours (a gap allows the liquid to flow between neighbours).

Third, ~t~ ~(100 \le t \le 50\,000)~, a positive integer giving the number of trials to be run.

Output Specification

Output the number of trials that led to an escape.

Sample Input

10
0.40
100

Sample Output

18

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