TopCoder problem "PlatformJumper" used in SRM 353 (Division I Level Two , Division II Level Three)



Problem Statement

    

In an old school arcade video game, you have reached the following bonus level. There are a number of platforms containing coins, and you must jump from platform to platform collecting the coins. You may only jump to lower platforms, so your entire journey will be downward. You can select any platform as your starting platform.

Your jumping behavior is defined as follows. On each jump, your horizontal speed is constant and does not exceed v. Your fall down follows the standard laws of physics: your free fall acceleration is g and initially your speed is 0.

For simplicity, we will represent each platform as a single point. Each element of platforms represents a single platform and is formatted "X Y C" (quotes for clarity), where X and Y are the x and y coordinates of the platform and C is the number of coins on the platform. Greater values of y represent higher locations. Return the greatest number of coins you can collect.

 

Definition

    
Class:PlatformJumper
Method:maxCoins
Parameters:String[], int, int
Returns:int
Method signature:int maxCoins(String[] platforms, int v, int g)
(be sure your method is public)
    
 

Notes

-A dropped object without starting velocity will fall down g*t2/2 units in time t.
-Note, that you always can drop to the platform right below you.
 

Constraints

-platforms will contain between 1 and 50 elements, inclusive.
-Each element of platforms will be formatted as "X Y C", where X, Y and C are integers with no extra leading zeroes.
-In each element of platforms, X and Y will be between 0 and 5000, inclusive.
-In each element of platforms, C will be between 0 and 10000, inclusive.
-All platforms will have distinct locations.
-v and g will each be between 1 and 100, inclusive.
 

Examples

0)
    
{"3 10 7", "5 15 7", "8 9 12" }
2
10
Returns: 14
It is possible to jump from platform 1 to platform 0, thus we can earn 7+7=14 coins. It is impossible to jump from platform 1 to platform 2.
1)
    
{"0 0 1", "2 4 1", "4 0 1"}
1
2
Returns: 2
2)
    
{"0 0 1", "5000 5000 10"}
100
87
Returns: 10

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7847

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10710&pm=7847

Writer:

xOberon

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Problem categories:

Dynamic Programming, Search, Simple Math