UnitsMoving
SRM 278 · 2005-12-19 · by Vedensky
SRM 278 · 2005-12-19 · by Vedensky · Graph Theory
Problem Statement
Problem Statement
You are to write a procedure for a computer game that will move groups of units.
You are given aString[] start containing the starting positions of all the units. Each element is formatted as "X Y V", where (X, Y) are integer coordinates, and V is an integer velocity in meters per second. You are also given a String[] finish containing the ending positions for all the units. Each element is formatted as "X Y", where (X, Y) are integer coordinates, and each element is distinct from the other elements. The ith element of start represents a single unit which must be moved from the coordinates in start[i] to the coordinates in some element of finish at the velocity given in start[i]. Each unit must be moved to a different location (that means, each two different units from start must be moved to different ending positions). Return a double representing the minimal time (in seconds) in which all the units will reach their destinations.
You are given a
Notes
- The returned value must be accurate to 1e-9 relative or absolute.
Constraints
- start will contain between 1 and 50 elements, inclusive.
- finish will contain the same number of elements as start.
- Each element of start will be formatted as "X Y V", where X, Y and V are integers without leading zeroes.
- Each element of finish will be formatted as "X Y", where X and Y are integers without leading zeroes.
- All X and Y will be between 0 and 1000, inclusive.
- All V will be between 1 and 10, inclusive.
- All elements of finish will be different.
Examples
0)
{"0 0 1", "0 1 1"}
{"1 1", "1 0"}
Returns: 1.0
The first unit moves to the second location for 1 second, and the second unit moves to the first location also for 1 second.
1)
{"0 0 1", "0 1 1"}
{"1 1", "2 1"}
Returns: 2.0
In this case, it is better to move the fist unit to the first location and the second unit - to the second one.
2)
{"0 0 10", "0 1 1"}
{"1 1", "2 1"}
Returns: 1.0
3)
{"0 0 1", "0 2 1"}
{"0 1", "0 4"}
Returns: 2.0
4)
{"0 0 3", "0 2 1"}
{"0 1", "0 4"}
Returns: 1.3333333333333333
Submissions are judged against all 84 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class UnitsMoving with a public method double bestTime(vector<string> start, vector<string> finish) · 84 test cases · 2 s / 256 MB per case