GetToTheTop
SRM 404 · 2008-06-05 · by ivan_metelsky
Problem Statement
Little John has found a set of stairs where each stair might contain a number of sweets. He wants to collect as many of these sweets as possible. Each stair can be described as a line segment in the Cartesian plane parallel to the x-axis and having a positive y-coordinate. These segments don't overlap and don't have common endpoints. When John is on a stair, he can move freely between its two endpoints and can collect all sweets on it. He can jump from a point on one stair to a point on another stair (including endpoints of stairs) if the Euclidean distance between them is less than or equal to K. He can only jump to stairs where the y-coordinate is greater than or equal to his current y-coordinate.
You are given a
Notes
- The Euclidean distance between points (x1, y1) and (x2, y2) is equal to the square root of (x1 - x2)^2 + (y1 - y2)^2.
Constraints
- K will be between 1 and 10000, inclusive.
- sweets will contain between 1 and 50 elements, inclusive.
- sweets, x, y and stairLength will all contain the same number of elements.
- Each element of sweets will be between 0 and 9999, inclusive.
- Each element of x will be between 1 and 10000, inclusive.
- Each element of y will be between 1 and 10000, inclusive.
- Each element of stairLength will be between 1 and 1000, inclusive.
- No stairs will overlap or share endpoints. More formally, for each i and j, where y[i] is equal to y[j], either x[i] + stairLength[i] will be less than x[j] or x[j] + stairLength[j] will be less than x[i].
20
{9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999}
{2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 114, 118, 122, 126, 130, 134, 138, 142, 146, 150, 154, 158, 162, 166, 170, 174, 178, 182, 186, 190, 194, 198}
{20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20}
{2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}
Returns: 499950
2
{1, 3, 6, 2, 8, 2}
{2, 4, 7, 8, 6, 9}
{6, 5, 6, 4, 7, 3}
{1, 2, 7, 5, 6, 9}
Returns: 0
4
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}
Returns: 15
9
{7, 8, 3}
{4, 8, 2}
{9, 2, 1}
{5, 5, 5}
Returns: 18
3
{3, 3, 3, 3}
{7, 2, 9, 1}
{1, 2, 3, 5}
{7, 7, 7, 7}
Returns: 12
2
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}
{2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 6}
{2, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 8, 2, 3, 4, 5, 6, 7}
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Returns: 170
ladder
2
{1, 2, 3, 4, 3, 5}
{1, 1, 1, 4, 5, 5}
{1, 3, 4, 1, 2, 3}
{2, 1, 1, 2, 1, 1}
Returns: 13
From the start position (0, 0) John can jump on stair 0 (all stair indices are 0-based) and collect 1 sweet. Then he can move to the rightmost point of this stair and jump on stair 3 (the one with the leftmost coordinate (4, 1)). There he collects 4 sweets. Now he has two options: go back to stair 0, jump on stair 1 to collect 2 sweets and then jump on stair 2 to collect 3 sweets; jump from stair 3 to stair 4 to collect 3 sweets and then to stair 5 to collect 5 sweets. Obviously the second option gives more sweets, so he will choose it and collect 1+4+3+5=13 sweets.
4
{2, 8, 7, 4, 1, 4, 7, 5, 11, 4}
{2, 9, 4, 6, 10, 5, 2, 8, 1, 10}
{1, 1, 3, 3, 3, 5, 6, 6, 8, 9}
{2, 2, 1, 2, 2, 2, 4, 3, 2, 2}
Returns: 47
John can make his first jump on stair 0 or on stair 1 (all stair indices are 0-based). Both choices allow him to visit the same set of stairs afterwards. It is better to jump on stair 1, because it contains 8 sweets. Then he can visit stairs 2, 3, ..., 7 collecting 1+4+7+4+7+5=28 sweets. Finally, he should choose between stairs 8 and 9. Stair 8 contains more sweets, so he will jump on it and collect 11 more sweets.
10
{0, 10, 11, 2, 0}
{1, 26, 29, 22, 3}
{1, 83, 88, 22, 5}
{11, 1, 23, 15, 8}
Returns: 0
John can not collect any sweets.
10000
{9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999}
{10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}
{10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987,9986,9985,9984,9983,9982,9981,9980,9979,9978,9977,9976,9975,9974,9973,9972,9971,9970,9969,9968,9967,9966,9965,9964,9963,9962,9961,9960,9959,9958,9957,9956,9955,9954,9953,9952,9951}
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
Returns: 499950
max answer
Submissions are judged against all 71 archived test cases, of which 10 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GetToTheTop with a public method int collectSweets(int K, vector<int> sweets, vector<int> x, vector<int> y, vector<int> stairLength) · 71 test cases · 2 s / 256 MB per case