TwoLadders
TCO19 Round 3B · 2019-04-15 · by misof
Problem Statement
You are playing a platform game. At the beginning, your x-coordinate is sx and your y-coordinate is 0. There is an infinite horizontal platform at each positive integer y-coordinate. There are two infinite vertical ladders. One starts at the point (lx1,0), the other at the point (lx2,0).
In one second you can walk one step left or right. If you are at a ladder, you can also climb one floor up in one second. Once you climb up, there is no way back down.
There are some coins scattered around the level: for each valid i, there is a coin that can be picked up when you reach the coordinates (X[i], Y[i]).
Calculate and return the minimum time to pick up all coins.
Constraints
- sx, lx1, and lx2 will all be between 0 and 10^9, inclusive.
- lx1 will be smaller than lx2.
- The number of elements in X will be between 1 and 100, inclusive.
- X and Y will have the same number of elements.
- All values in X and Y will be be between 0 and 10^9, inclusive.
- The points (sx, 0), (lx1, 0), (lx2, 0), and the locations of all coins will all be distinct.
10
0
100
{47, 42}
{0, 0}
Returns: 37
You start at (10, 0). You simply start walking right. After 32 seconds you'll pick up the coin at (42, 0) and after another 5 seconds the coin at (47, 0).
10
8
11
{10, 12}
{1, 1}
Returns: 5
Go right, up, left, right, right. Alternately, go right, up, right, left, left.
10
8
42
{10, 12}
{1, 1}
Returns: 7
This time you should go two steps left, then up, then four steps right.
10
8
42
{10, 100, 12}
{1, 0, 1}
Returns: 181
You have to pick up the coin at (100, 0) first. Then, once you are that far right, you might as well take the ladder at x=42 and continue walking left until you pick up both coins.
500000000
1
999999999
{0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000}
{1, 1, 2, 2, 3, 3, 4, 4, 7, 7, 999999947, 999999947, 900000047, 900000047}
Returns: 8499999959
In one variant of the philosophical problem by Jean Buridan, a donkey starves to death when you place it exactly halfway between two identical piles of hay. Don't let that happen to you in this nice symmetric level!
Submissions are judged against all 211 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TwoLadders with a public method long long minSteps(int sx, int lx1, int lx2, vector<int> X, vector<int> Y) · 211 test cases · 2 s / 256 MB per case