TrainRobber
SRM 307 · 2006-06-14 · by Mike Mirzayanov
Problem Statement
A train is moving in the positive direction of the x-axis. The train consists of nCarriages carriages of equal length. Initially, at time 0, the coordinate of the rightmost end of the last carriage is length, the coordinate of the rightmost end of the second to last carriage is 2 * length, and so on. There is a robber located on the leftmost point of the roof of the last carriage.
Here is an example of a train with 4 carriages at time 0.
There are an infinite number of low bridges above the railway. Each bridge belongs to one bridge sequence. The k-th sequence consists of bridges located at the coordinates offset[k] + period[k] * j, for all non-negative integers j.
The blue bridges belong to sequence 0 and the red bridges belong to sequence 1. In this case, offset[0] = 3, period[0] = 4, offset[1] = 4, and period[1] = 2.
The train moves at a constant speed of trainSpeeed units per second, and the robber has a maximal speed of robberSpeed units per second. The robber cannot walk through the bridges when he is on the roof because they are too low. Therefore, whenever the robber is at the same coordinate as a bridge, he must either be between two carriages or at either end of the train. This allows him to duck and jump down into a safe area.
The robber's goal is to travel to the rightmost point of the first carriage as quickly as possible. He will stop walking and jump off the train when he reaches the rightmost point of the first carriage, or when nBridges have passed above him - whichever comes first. Return the position of the robber on the x-axis when he exits the train.
The offsets and periods of the bridge sequences are given in the
Notes
- It is possible for multiple bridges to be located in the same position.
- A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
Constraints
- length will be between 1 and 1000000, inclusive.
- nCarriages will be between 1 and 1000000, inclusive.
- offset will contain between 1 and 50 elements, inclusive.
- Each element of offset will contain between 1 and 50 characters, inclusive.
- period will contain between 1 and 50 elements, inclusive.
- Each element of period will contain between 1 and 50 characters, inclusive.
- Each element of offset and period will contain one or more integers without leading zeroes separated by single spaces.
- Each integer in offset and period will be between 1 and 1000000, inclusive.
- offset and period will contain the same number of integers.
- trainSpeed will be between 1 and 1000000, inclusive.
- robberSpeed will be between 1 and 1000000, inclusive.
- nBridges will be between 1 and 1000000, inclusive.
1
4
{"3 4"}
{"4", "2"}
1
1
100
Returns: 14.0
The robber will walk to the rightmost end of the last carriage and then duck down between carriages to avoid the first two bridges (at coordinates 3 and 4). He will then walk to the rightmost end of the next carriage and duck down to avoid the next three bridges (at coordinates 6, 7, and 8). He will repeat this procedure once more to avoid the next three bridges (at coordinates 10, 11, and 12). He will finally reach the rightmost point of the first carriage when he is at coordinate 14.
1
4
{"3 4"}
{"4 2"}
1
1
1
Returns: 3.0
The first bridge will pass when the robber is at coordinate 3.
5
10
{"8 23"}
{"15 13"}
10
10
10
Returns: 75.0
100
100
{"1 1"}
{"1 1"}
100
100
100
Returns: 50.0
1
1000000
{"10", "15 63"}
{"23 42 11"}
10
1000
1000
Returns: 6355.0
Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TrainRobber with a public method double finalPosition(int length, int nCarriages, vector<string> offset, vector<string> period, int trainSpeed, int robberSpeed, int nBridges) · 109 test cases · 2 s / 256 MB per case