ACM ICPC Philippines 2008: Problem D

.
2nd Philippine National Inter-Collegiate Programming Competition
(ACM Philippines 2008)
22 November 2008, Cebu City

Problem D: “Soil Investigation”
Input File: d.in

Introduction:

For a mining company to investigate the existence of a mineral (such as gold or oil), it needs to drill several holes on the area it suspects to have the precious mineral and get the soil samples. Based on the laboratory test of the soil samples on a hole, the company can decide the degree of existence of the precious mineral and the level of confidence (between 0 and 1) from that hole.

However, it is not advisable to drill the whole area due to high cost of drilling. To do the soil investigation in a more systematic way, the company decides to take aerial photograph of the whole site and divides them into cells of equally distance grid. By ignoring the remaining boundary, the cell size of the grid can be assumed as a square. Then, the company starts to drill on selected cells and approximates the degree of existence of the precious mineral based on smoothing average of the neighboring cells. A cell that does not have drilling hole will have zero confidence.

The smoothing procedure goes as the summation of a product between the level of confidence and the degree of existence of the center cell and one minus the product between the level of confidence of the center cell and average degree of existence over 4 neighbors (up, down, left and right).

The iteration formula is

(a^0)(i,j) = b(i,j)*c(i,j) + (1 - c(i,j))*((b(i - 1, j) + b(i+1,j) + b(i, j - 1) + b(i, j+1))/4)

Task: Write a program to compute the approximation of the degree of existence of a precious mineral on a certain cell of interest (current row, current column) given the grid size (number of cells in a row, number of cells in a column) and results of laboratory test at certain cell (test row, test column, degree of existence of the precious mineral, the level of confidence). The coordinate system is assumed to start at (1, 1) on the top left cell.Input: The format of an input test case is as follows:

Number of cells in a row, number of cells in a column

List of results of laboratory test at certain cell (test row, test column, degree of existence of the precious mineral, the level of confidence)

List of coordinates of the cell of interest (current row, current column)

The input is terminated by a zero on a line by itself.

Output: List of the approximation of the degree of existence of the precious mineral on the cell of interest for each test case

Sample Input

3, 5
1, 1, 10, 1
1, 5, 5, 0.7
2, 2, 20, 0.8
3, 5, 6, 0.5
1, 1
1, 4
2, 2
3, 4
0
5, 4
3, 2, 7, 1
4, 4, 5, 1
4, 2
4, 3
0

Sample Output

Case 1
1, 1: 10
1, 4: 1.3
2, 2: 16
3, 4: 1.5

Case 2
4, 2: 1.8
4, 3: 1.3

------------------------------------------------------

Problem Category: Moderate

Number of teams which solved the problem: 8 (out 39)

Success rate: 21 %

For more information, contact: computingsoc@gmail.com

.