PROBLEM STATEMENT
A pursuit race is run on a circular track. The participants each start at
the same start line, but each at
a different time based upon their performance in earlier races. Whenever a
rider is passed by another rider, he is eliminated from the race. If a
previous rider circled the track and reached the start line at or before the
time when a contestant is scheduled to start, then that contestant is eliminated
at the time the rider reached the start line.
Suppose that the racers each go at a constant speed. Create a class BikeRace that
contains a method eliminated that is given track, the length of the track,
vector name, the names of the contestants, a vector start, the start times of
the contestants, and a vector speed, the speeds of the
contestants. It returns a vector giving the names of
the eliminated contestants in the order in which they were eliminated. In case of
simultaneous eliminations, list the simultaneously eliminated riders in alphabetical order.
track is in feet, speed is in feet per second, and start is in seconds. Element i
of speed, start, and name applies to contestant i.
DEFINITION
Class:BikeRace
Method:eliminated
Parameters:int, vector , vector , vector
Returns:vector
Method signature:vector eliminated(int track, vector name, vector start,
vector speed)
CONSTRAINTS
-track will be between 1000 and 5000 inclusive.
-name will contain between 2 and 50 elements inclusive.
-name, start, and speed will all contain the same number of elements.
-Each element of name will contain between 1 and 50 characters inclusive.
-Each character in each element of name will be an uppercase letter 'A'-'Z'.
-The elements of name will be distinct.
-Each element of start will be between 0 and 1000 inclusive.
-The elements of start will be distinct.
-Each element of speed will be between 1 and 50 inclusive.
EXAMPLES
0)
4800
{"A","B","C"}
{ 0, 100,180}
{30, 30, 30}
Returns: { "C" }
Rider A starts at time 0 and goes 3000 feet before B starts at time 100.
A passes the
start line at time 160, before C can start, thereby eliminating C. But B and
A can never catch each other since they are going the same speed so they are
never eliminated.
1)
3000
{"BO","JO", "AL"}
{ 10, 0, 15 }
{ 12, 2, 10 }
Returns: { "JO", "AL" }
JO goes 20 feet (10 seconds at 2 feet/sec) before BO starts at time 10.
JO is eliminated at time 12 since
both JO and BO have gone 24 feet. AL starts at time 15 but is eventually
caught by BO since BO is going at a higher speed.
2)
3000
{"BOBO","JOHNNY","ANNA"}
{67,0,15}
{50,45,3}
Returns: { "BOBO", "ANNA" }
3)
3000
{"B","J","A"}
{66,0,15}
{50,45,3}
Returns: { "A", "J" }
4)
5000
{"TOM","TOMMY","BILL","SPEEDY","JIMMY"}
{100,120,110,0,1000}
{50,50,50,50,50}
Returns: { "BILL", "JIMMY", "TOM", "TOMMY" }
SPEEDY just manages to circle the track before any of the others can start. So the other four are
all eliminated at the same time, and are listed in alphabetical order.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.