Connection Status:
Competition Arena > RoadCrossing

RoadCrossing

SRM 373 · 2007-10-23 · by Vedensky

SRM 373 · 2007-10-23 · by Vedensky · Simple Math, Simulation
Class Name: RoadCrossing
Return Type: double
Method Name: passTime
Arg Types: (vector<string>, int, int, int)
Problem Statement

Problem Statement

Some pedestrians are crossing a road. A car arrives at the crosswalk and wants to pass through, but can only get by if there's an empty gap of at least carWidth centimeters. The road is roadWidth centimeters wide. All the pedestrians are walking in the same direction.

You are given a String[] pedestrians, each element of which is formatted as "T V" (quotes for clarity), where T is the time that one pedestrian starts crossing the road (in seconds), and V is his walking speed (in centimeters per second). The car arrives at time carArrival seconds. The car can pass through at any time after its arrival (including the moment of arrival), when there is sufficient free space to pass through. Return a double indicating the earliest time (in seconds) the car can pass through.

Notes

  • The returned value must have an absolute or relative error less than 1e-9.
  • The car passes through instantly, i.e., it takes no time for the car to pass through.

Constraints

  • pedestrians will contain between 0 and 50 elements, inclusive.
  • Each element of pedestrians will be formatted as "T V" (quotes for clarity), where T and V are integers with no extra leading zeros.
  • Each T will be between 0 and 1000, inclusive.
  • Each V will be between 1 and 1000, inclusive.
  • roadWidth will be between 1 and 1000, inclusive.
  • carWidth will be between 1 and roadWidth, inclusive.
  • carArrival will be between 1 and 1000, inclusive.
Examples
0)
{"0 1", "2 5"}
8
4
3
Returns: 3.5

At time 3.5, the pedestrians are 3.5 and 7.5 centimeters from the side of the road. The car can pass through the 4 centimeter gap between the pedestrians. This is the earliest time it can pass through.

1)
{"40 1"}
100
100
41
Returns: 140.0

The pedestrian starts crossing the road at time 40. At time 41, the car arrives, and the pedestrian is 1 cm from the side of the road. The car needs the entire width of the road to pass through, and therefore, it must wait until the pedestrian finishes crossing. The pedestrian reaches the other side of the road at time 140.

2)
{"0 1", "0 2", "0 4", "0 8", "0 16", "0 32", "0 64", "0 128", "0 256"}
100
50
3
Returns: 3.125
3)
{"0 1", "0 2", "0 4", "0 8", "0 16", "0 32", "0 64", "0 128", "0 256"}
100
51
3
Returns: 51.0
4)
{"1000 1", "100 1"}
1000
1000
1000
Returns: 2000.0

Maximal possible answer.

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

Coding Area

Language: C++17 · define a public class RoadCrossing with a public method double passTime(vector<string> pedestrians, int roadWidth, int carWidth, int carArrival) · 102 test cases · 2 s / 256 MB per case

Submitting as anonymous