StripMine | Topcoder Archive

Problem Statement

We want to maximize the profit from strip-mining. We have laid out the mine in a rectangular grid of squares that shows a vertical cross-section. Each successive row shows the next deeper level, and each column shows a different location. Each square represents the volume of earth at the given depth and location that can be removed with our equipment. (The third dimension is the fixed width of our earth-removal equipment.)

Our equipment will excavate whole squares from this cross-section. Of course it cannot excavate a square unless it has already excavated the one above it. We have the geologist's report, which estimates the value of the minerals in each square. Our total profit will be the sum of the values of the excavated squares, minus a cost of 3 for each square excavated. However, we also must satisfy environmental restrictions. We are given a maximum number of squares that we may legally remove. Furthermore, we cannot leave a slope of more than 3:1. That means that for two adjacent columns the number of squares removed cannot differ by more than 3. It also means that we cannot remove more than 3 squares from either of the end columns.

Create a class StripMine that contains the method maxProfit that takes an int limit, the most squares that we may legally remove, and the String[] report, showing the value of each square, as inputs and returns the maximum profit that we can legally achieve. The profit is the sum of the values of the excavated squares, minus a cost of 3 for each square excavated.

The first element of report indicates the values of the squares in the first (topmost) row in the cross-section. For each location it gives a letter indicating the estimated value, where 'A'=0, 'B'=1, ... , 'Z'=25. Successive elements of report indicates the values of successively deeper rows in the cross-section.

Definition

Class:: StripMine
Method:: maxProfit
Parameters:: int, String[]
Returns:: int
Method signature:: int maxProfit(int limit, String[] report)
(be sure your method is public)

Constraints

limit will be between 0 and 100 inclusive
report will contain between 1 and 50 elements, inclusive
Each element of report will have length between 1 and 50 inclusive
Each element of report has the same length as each other element
Each element of report will contain only the uppercase letters 'A'-'Z'

Examples

```
13
```
```
{"AACEC","CCBDD","AGHED","ULCCZ"}
```
```
Returns: 7
```
0 0 2 4 2 2 2 1 3 3 0 6 7 4 3 20 11 2 2 25 We can achieve a profit of 7 by excavating one square from the first column, 4 squares from the second column, 3 squares from the third column, 3 squares from the fourth column, and 0 squares from the last column. That makes a total value of 0 + (0+2+6+11) + (2+1+7) + (4+3+4) = 40 with an excavation cost of 11*3. Notice that we are not required to excavate all 13 allowed by the limit. We needed to excavate the square at the top of the first column so that we could legally get down to the 11 in the next column. We could not extract the 20 or 25 because that would cause a slope of 4 between the adjacent property and our mine.
```
3
```
```
{"ZZZZZZZ","ZZZZZZZ"}
```
```
Returns: 66
```
```
0
```
```
{"ZZZZZZZ","ZZZZZZZ"}
```
```
Returns: 0
```
It's a rich mine, but the environmentalists won't let us dig here.

{"DDDE","DDDD","FEDD","DDGH"}

Returns: 5

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.