FoxSearchingRuins | Topcoder Archive

Problem Statement

Fox Ciel has a map of some underground ruins. It describes the position of several jewels and their values. She wants to collect some of the jewels. The map is a rectangle with width W and height H. It contains W*H cells. The cell in the upper left corner has the coordinates (0,0) and the cell in the lower right corner has coordinates (W-1,H-1). There are jewelCount jewels. The i-th jewel is located at coordinates (x[i],y[i]) and has a value of v[i]. 0, 1, 2 or more jewels may be in the same cell.

Ciel starts from any cell in the top row (any cell whose y-coordinate is 0 and x-coordinate is arbitrary). She has a super drill so she can move down any number of times, but she can move to the left or right at most LR times. Moving up is not allowed. She collects all the jewels in a cell by moving to that cell (or starting in that cell). Moving down takes timeY seconds and moving left or right takes timeX seconds. Collecting jewels takes no time.

Calculate and return the minimum time required to collect enough jewels so that the sum of the values of the collected jewels is greater than or equal to goalValue. If she can't collect enough jewels then return -1.

You can calculate x[i], y[i], and v[i] as follows:

    x[0] = (seeds[1] * seeds[0] + seeds[2]) mod W
    y[0] = (seeds[4] * seeds[3] + seeds[5]) mod H
    v[0] = (seeds[7] * seeds[6] + seeds[8]) mod seeds[9]
    for i=1 to jewelCount-1:
        x[i] = (seeds[1] * x[i-1] + seeds[2]) mod W
        y[i] = (seeds[4] * y[i-1] + seeds[5]) mod H
        v[i] = (seeds[7] * v[i-1] + seeds[8]) mod seeds[9]

Definition

Class:: FoxSearchingRuins
Method:: theMinTime
Parameters:: int, int, int, int, int, int, int, int[]
Returns:: long
Method signature:: long theMinTime(int W, int H, int jewelCount, int LR, int goalValue, int timeX, int timeY, int[] seeds)
(be sure your method is public)

Constraints

W will be between 1 and 1,000, inclusive.
H will be between 1 and 1,000,000,000, inclusive.
jewelCount will be between 1 and 1,000, inclusive.
LR will be between 0 and 1,000, inclusive.
timeX and timeY will each be between 1 and 100, inclusive.
goalValue will be between 1 and 1,000,000,000, inclusive.
seeds will contain exactly 10 elements.
for i=0..8, seeds[i] will be between 0 and 1,000,000,000, inclusive.
seeds[9] will be between 2 and 1,000,000, inclusive.

Examples

```
5
```
```
8
```
```
5
```
```
7
```
```
10
```
```
3
```
```
1
```
```
{979, 777, 878, 646, 441, 545, 789, 896, 987, 10}
```
```
Returns: 5
```
The map of the ruins is as follows: 3.... ...5. ....7 .9... ..... ..... ..... .1... Ciel's optimal moves: Start from (3, 0). (time = 0) Move to (3, 1) and collect the jewel whose value is 5. (time = 1) Move to (4, 1). (time = 4) Move to (4, 2) and collect the jewel whose value is 7. (time = 5)
```
7
```
```
8
```
```
10
```
```
3
```
```
10
```
```
3
```
```
10
```
```
{0, 1, 1, 0, 1, 3, 1011, 3033, 2022, 10}
```
```
Returns: 29
```
The map and Ciel's optimal moves: .1..... ...*... ...3... ...*... ......7 ...**** .55.... ....... ....1.. ....... 3...... ....... ..77... ....... .....5. .......
```
7
```
```
8
```
```
10
```
```
3
```
```
14
```
```
3
```
```
10
```
```
{0, 1, 1, 0, 1, 3, 1011, 3033, 2022, 10}
```
```
Returns: 59
```
Note that Ciel can move left or right at most 3 times. .1..... ...*... ...3... ...*... ......7 ...*... .55.... .***... ....1.. .*..... 3...... **..... ..77... ....... .....5. .......
```
7
```
```
8
```
```
10
```
```
4
```
```
14
```
```
3
```
```
10
```
```
{0, 1, 1, 0, 1, 3, 1011, 3033, 2022, 10}
```
```
Returns: 42
```
Now Ciel can move left or right at most 4 times. .1..... .***... ...3... ...*... ......7 ...*... .55.... .***... ....1.. ....... 3...... ....... ..77... ....... .....5. .......

{7613497, 5316789, 1334537, 2217889, 6349551, 978463, 1234567, 2345678, 3456789, 1000}

Returns: -1

Watch out for integer overflow when computing x[i], y[i] and v[i].

749613275

{224284427, 617001937, 294074399, 606566321, 202762619, 419798101, 200613401, 640663967, 417565817, 170000}

Returns: 3780225876

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.