Connection Status:
Competition Arena > TestingCar

TestingCar

SRM 276 · 2005-12-08 · by Olexiy

SRM 276 · 2005-12-08 · by Olexiy · Brute Force, Math
Class Name: TestingCar
Return Type: double
Method Name: maximalSpeed
Arg Types: (vector<string>, int, int)
Problem Statement

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).

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
0)
{"30 0 200"}
100
25
Returns: 30.0

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

1)
{"30 0 200"}
4
5
Returns: 20.0

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

2)
{"50 0 40", "50 60 50"}
100
10
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.

3)
{"50 30 10", "50 60 50"}
100
10
Returns: 175.0
4)
{"50 30 10", "50 60 50"}
100
14
Returns: 235.0

Submissions are judged against all 222 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TestingCar with a public method double maximalSpeed(vector<string> restrictions, int duration, int acceleration) · 222 test cases · 2 s / 256 MB per case

Submitting as anonymous