Bounce
SRM 141 · 2003-04-10 · by schveiguy
Problem Statement
You are at the top of a building that is 125 meters tall with a bouncy ball and a horizontal launcher. Across the street, your friend is waiting on top of a smaller building of a given height. You want to fire the ball with your launcher such that the ball will land on top of the building that your friend is standing on. The ball must bounce one or more times on the street before landing on the other building. The ball you happen to have is a prototype which is completely elastic. This means it does not lose any energy when it bounces, and every bounce is exactly the same height as the previous bounce, which is exactly the same height as the original launcher. Because you want to keep control of this ball, your goal is to fire the ball at the slowest horizontal speed and still have it reach the top of the other building.
Using simple laws of motion from physics, we can derive formulas for the X and Y position of the ball over time. The X position is given by the formula:
X = Vi*t
Here, Vi is the initial launch velocity of the ball, and t is the time elapsed since the launch.
After the ball bounces, the Y position is dictated by the formula:
Y = 50*b +g*b*b/2
In this formula, g is the acceleration constant for gravity, which is fixed at -10. b is the time since the most recent bounce occurred. Each time the ball bounces, b is reset to 0. If unobstructed, the ball bounces for the first time 5 seconds after being launched. If still unobstructed, each bounce will occur 10 seconds after the previous bounce. So with a very wide street, the bounces would be at 5 seconds, 15 seconds, 25 seconds, 35 seconds, etc. Note that this property, and the Y position in general, does not depend at all on the launch velocity.
Given an int height of the second building and an int distance of how wide the street is between the buildings, determine the lowest integral speed at which you can launch the ball such that it will bounce at least once, and reach the top of the other building. The ball must be at or over the top of the other building when it reaches it for the first time, otherwise it may go into a window, and you don't want to lose the only 100% elastic ball in existence! If there is no integral speed that will satisfy these requirements, return -1.
Notes
- Assume that as long as the ball is at the height of the building or higher when the other building is reached, it will land on the building. There is no risk of the ball bouncing completely over the other building.
- Assume that the ball has a negligible radius, and that no other forces besides gravity and bouncing off of the ground affect the ball.
Constraints
- height is between 1 and 124, inclusive.
- distance is between 5 and 500, inclusive.
- For all speeds up to and including the correct speed, the ball will not reach the second building within .000001 meters of the top of the building.
124 10 Returns: 1
By the time the ball reaches the other building, it is at its full height of 125 meters again, so all building heights that are 10 meters away will always return 1.
124 9 Returns: -1
Now that the building is 1 meter closer, the ball will not make it to the top of the building after the first bounce, and if we fire at 2 m/s, it will reach the building before bouncing.
124 99 Returns: 5
Firing the ball at 5 m/s, the ball will bounce twice before landing on the second building. The first bounce occurs 25 meters away from the first building, the second bounce at 75 meters away. When the ball reaches the second building, its height is 124.8 meters.
95 196 Returns: 2
It takes 10 bounces before the ball finally goes over the top of the building.
1 5 Returns: -1
Firing the ball at 1 m/s, the ball will land in the street just as it hits the other building, so it cannot be fired such that it bounces at least once and lands on the other building.
Submissions are judged against all 54 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Bounce with a public method int howFast(int height, int distance) · 54 test cases · 2 s / 256 MB per case