FoxSearchingRuins
Member SRM 501 · 2010-11-01 · by wrong
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]
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.
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. .......
497
503
989
647
100000
13
14
{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].
Submissions are judged against all 228 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FoxSearchingRuins with a public method long long theMinTime(int W, int H, int jewelCount, int LR, int goalValue, int timeX, int timeY, vector<int> seeds) · 228 test cases · 2 s / 256 MB per case