ObjectFall
SRM 289 · 2006-02-14 · by esteban
Problem Statement
An object is placed in the xy-plane at coordinates (x,y), where x > 0 and y > 0. The object begins falling straight down toward the x-axis at a speed of one unit per second. Along the way, it may encounter some obstacles. Each obstacle is a horizontal line segment, and the object hits an obstacle when their y-coordinates are equal and the object's x-coordinate is between the x-coordinates of the obstacle's endpoints (inclusive). Each time the object hits an obstacle, it will be delayed 5 seconds. During this delay, the object will travel to the right endpoint of the obstacle (the one with the greater x-coordinate). The object will then continue to fall straight down from that point.
You are given the object's initial position (x,y) and a
Constraints
- x will be between 1 and 1000, inclusive.
- y will be between 1 and 1000, inclusive.
- obstacles will contain between 0 and 50 elements, inclusive.
- Each element of obstacles will be formatted "y x1 x2" (quotes for clarity only).
- Each y, x1 and x2 in obstacles will be an integer between 001 and 999, inclusive, and contain exactly 3 digits.
- In each element of obstacles, x1 will be less than or equal to x2.
- obstacles will contain no duplicate y values.
15
10
{"005 010 020"}
Returns: 15
The object starts at (15,10), and when it reaches (15,5), it hits the obstacle and is delayed 5 seconds.
15
12
{"010 010 020","015 010 020","005 020 050"}
Returns: 22
The object hits the obstacle at y = 10 and moves to (20,10). From there it continues to fall until it hits the object at y = 5. Finally, it falls to the x-axis at (50,0). The total time is: 2 seconds before hitting the first obstacle + 5 seconds of delay + 5 seconds until hitting the next obstacle + 5 seconds of delay + 5 seconds until hitting the x-axis = 22 seconds.
50
85
{"020 001 100","010 100 100","005 100 200"}
Returns: 100
The object hits all three obstacles, even the one that is a point.
10
1000
{}
Returns: 1000
A free-fall to the x-axis.
500
800
{"800 001 500","400 001 499","401 501 999"}
Returns: 805
Submissions are judged against all 127 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ObjectFall with a public method int howLong(int x, int y, vector<string> obstacles) · 127 test cases · 2 s / 256 MB per case