TopCoder problem "TestingCar" used in SRM 276 (Division I Level Two)

Problem Statement

A test driver in a car company tests a new prototype. For each test drive, he is given a list of restrictions, limiting his speed at certain moments in time. The test driver wants to reach as fast a speed as possible. You should write a program which will find the maximal speed he can reach without violating the restrictions.

You will be given a String[] restrictions, giving you the restrictions for the test-drive. Each element of restrictions will contain three integers S, T and D separated by single spaces. The restriction becomes active T seconds after the start of the test-drive and stays active for D seconds. While the restriction is active the car can not go faster than S meters per second. If two or more restrictions are applicable at the same time, the restriction with the minimal speed should be taken into account.

At the start of the test drive, the car is motionless. Given two ints, duration, the total duration of the test drive in seconds, and acceleration, the maximal possible acceleration of the car in meters per second squared, return the maximal speed allowed by the test-drive restrictions. Please note that acceleration applies both to increasing and decreasing speed (braking).

Definition

Class:	TestingCar
Method:	maximalSpeed
Parameters:	String[], int, int
Returns:	double
Method signature:	double maximalSpeed(String[] restrictions, int duration, int acceleration)
(be sure your method is public)

Notes

The car does not have to come to a complete stop at the final moment of the test drive. It can still be moving.

For the purposes of the problem you may assume the car has no speed limit at all.

Your return value must have an absolute or relative error less than 1e-9.

Constraints

restrictions will contain between 0 and 50 elements, inclusive.

Each element of restrictions will be formatted as "S T D".

In each element of restrictions, S, T and D will be separated by single spaces and contain no leading zeroes.

In each element of restrictions, S will be an integer between 0 and 100, inclusive.

In each element of restrictions, T will be an integer between 0 and duration, inclusive.

In each element of restrictions, D will be an integer between 0 and 1000, inclusive.

duration will be between 1 and 1000, inclusive.

acceleration will be between 1 and 25, inclusive.

Examples

{"30 0 200"}

Returns: 30.0

The restriction doesn't allow us to go faster than 30 meters per second.

{"30 0 200"}

Returns: 20.0

We only have enough time to reach 20 meters per second.

{"50 0 40", "50 60 50"}

Returns: 150.0

The car can go above 50 meters per second only between the 40th and 60th second. Accelerating from the 40th to 50th second, and braking from the 50th to 60th allows you to reach 150 meters per second.

{"50 30 10", "50 60 50"}

Returns: 175.0

{"0 0 100", "0 200 100", "0 400 100", "0 600 100", "0 800 100"}

Returns: 2000.0

{"0 0 100", "0 200 100", "0 400 100", "0 600 100", "0 800 100", "0 1000 100"}

Returns: 1000.0

{"44 422 129", "45 1 29", "72 290 80", "2 1 331", "76 445 16", 
"76 204 429", "8 372 737", "21 159 538", "71 266 707", "99 73 933",
 "38 457 879", "42 24 299", "54 349 882", "6 352 909", "26 419 428",
 "51 327 311", "10 52 898", "75 10 702", "54 263 762", "75 404 223",
 "43 383 127", "86 433 521", "58 394 306", "33 379 514", "58 239 973",
 "89 301 765", "47 235 777", "75 355 190", "52 425 38", "59 140 347",
 "89 220 810", "47 72 724", "3 398 283", "0 224 266", "88 222 615",
 "25 149 85", "59 221 838", "14 87 86", "44 227 252", "73 330 936",
 "71 198 138", "54 186 141", "6 128 454", "5 123 719", "7 442 930",
 "59 174 505", "37 0 581", "9 198 168", "40 391 692", "49 320 419"}

Returns: 7.5

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8073&pm=4634

Writer:

Olexiy

Testers:

PabloGilberto , lbackstrom , brett1479 , timmac

Problem categories:

Brute Force, Math