## CCO '97 P3 - Porous Stone

View as PDF

Points: 10
Time limit: 10.0s
Memory limit: 1G

Problem types
##### 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 by grid, say . You are to write a program to determine by simulation, the probability that the boundary can be reached from the starting point . This is done by doing trials, counting the number that succeed in reaching the boundary, and then dividing this by to find the probability of escape. A boundary point is any point such that either or is or .

On any one trial, the probability that there is a gap between a grid point and its neighbour is determined by and this probability stays constant for one trial. This is also true for the other three neighbours of point . The value for 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 lines, each containing one value:

First, , a positive integer giving the grid size as by .

Second, , a real value giving the probability that there is a gap between neighbours (a gap allows the liquid to flow between neighbours).

Third, , 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.