Statistics

Problem Statement for "GPS"

Problem Statement

You are working at an emergency medical dispatch station and have been asked to write a program that uses a Global Positioning System (GPS) to determine the closest ambulance to a caller's location. This program must take roads and their speed limits into account.

A road will be thought of as a line segment connecting 2 points (X1,Y1) and (X2,Y2) in the cartesian plane. It will have an associated speed limit S. All speed limits will be multiples of 5. Such a road will be given as a String formatted "X1 Y1 X2 Y2 S". All roads will be horizontal or vertical. An ambulance at location (X,Y) will be given as the String "X Y". A caller at location (X,Y) will be given as the String "X Y". The caller location and all ambulances will be on roads.

Create a class GPS which contains a method closest that takes as arguments a String[] roads (the locations and speed limits of the roads), a String[] ambulances (the locations of the ambulances), and a String caller (the location of the caller). The method should return the index (0-based) of the ambulance who can arrive the quickest, breaking ties by choosing the one that appears earlier in the given list. All ambulances will take the quickest path possible.

Ambulances always travel at the speed limit so the following formula will come in handy: TimeSpentOnRoad = DistanceOnRoad/RoadSpeedLimit

Note that roads can intersect, allowing an ambulance to switch roads at the point of intersection. For example:


roads = {"5 10 5 0 30",
         "0 5 10 5 45",
         "10 5 10 0 60"}
ambulances = {"5 10"}
caller = "10 0"

Speed limit of AB = 30, CD = 45, DE = 60


                  A (5,10)
                  |
                  |
      (0,5) C------------D (10,5)
                  |      |
                  |      |
            (5,0) B      E (10,0)

Assume the ambulance is at point A and the caller is at point E. The ambulance can head downward, change to CD at the intersection and then take DE to the caller. The total time will be (5/30)+(5/45)+(5/60) = 13/36. Note that the distance between two points is the cartesian distance.

Definition

Class:
GPS
Method:
closest
Parameters:
String[], String[], String
Returns:
int
Method signature:
int closest(String[] roads, String[] ambulances, String caller)
(be sure your method is public)

Notes

  • Units of speed, distance, and time are irrelevant, as long as they are considered consistent throughout the problem.
  • There may be multiple ambulances in the same location.
  • Ambulances may only travel on the given roads.

Constraints

  • roads will contain between 2 and 30 elements, inclusive.
  • each element of roads will be formatted "X1 Y1 X2 Y2 S", where X1, Y1, X2, and Y2 each represent a non-negative integer between 0 and 99, inclusive, with a single space between them. Leading zeros are not allowed. S will represent the speed, which shall be an integer multiple of 5 between the values of 30 and 60, inclusive. The road is considered to connect the 2 locations "X1 Y1" and "X2 Y2", which will be distinct points.
  • roads will be vertical or horizontal.
  • no two roads will intersect at more than a single point.
  • ambulances will contain between 1 and 20 elements, inclusive.
  • each element of ambulances will be formatted "X Y" where X and Y each represent a non-negative integer between 0 and 99, inclusive, with a single space between them. Leading zeros are not allowed.
  • caller shall follow the same format restrictions as the elements of ambulances.
  • the locations of the caller and the ambulances shall all be on a road (endpoints are considered on the road).
  • at least one ambulance will be able to reach the caller by some route.

Examples

  1. {"5 10 5 0 30","0 5 10 5 45","10 5 10 0 60"}

    {"5 10"}

    "10 0"

    Returns: 0

    This is the example from the problem statement. There is only one ambulance, and it is closest.

  2. {"0 5 10 5 30","5 0 5 10 30"}

    {"0 5","9 5","5 3","5 3"}

    "5 5"

    Returns: 2

    The streets form a plus sign with the caller in the middle. The ambulances are, respectively, 5, 4, 2, and 2 units away from the caller. Since the speed limit is the same throughout, the third and fourth ambulances are closest, and the first of those (index 2) is chosen.

  3. {"0 5 10 5 60","5 0 5 10 30"}

    {"0 5","9 5","5 3","5 8"}

    "5 5"

    Returns: 1

    This is the same road configuration as before, but now the ambulances that are farther away have double the speed limit. The second and third ambulances can reach the call in the same amount of time, so the method returns the first one (index 1).

  4. {"10 0 10 80 60","20 0 20 80 60","10 70 20 70 30"}

    {"10 10","20 70"}

    "20 10"

    Returns: 1

    Here we see that the second ambulance, although physically 6 times farther away from the call than the first ambulance, still is closer due to the road configuration.

  5. {"10 0 10 80 60","20 0 20 80 60","10 70 20 70 30","10 10 20 10 30"}

    {"10 10","20 70"}

    "20 10"

    Returns: 0

    The same setup as before, with a new street connecting the first ambulance's location to the caller location, making it the closest.

  6. {"0 0 0 24 55","2 0 2 24 45","4 0 4 24 45", "5 0 5 24 60","7 0 7 24 30","9 0 9 24 60", "10 0 10 24 60","12 0 12 24 60","14 0 14 24 50", "15 0 15 24 50","17 0 17 24 45","19 0 19 24 35", "20 0 20 24 60","22 0 22 24 55","24 0 24 24 45", "0 0 24 0 45","0 2 24 2 50","0 4 24 4 60", "0 5 24 5 40","0 7 24 7 35","0 9 24 9 45", "0 10 24 10 40","0 12 24 12 35","0 14 24 14 50", "0 15 24 15 55","0 17 24 17 60","0 19 24 19 40", "0 20 24 20 30","0 22 24 22 55","0 24 24 24 40"}

    {"7 22","9 4","5 7","17 0","0 19","20 22","19 14","17 15","2 0","2 7", "9 22","2 9","17 17","10 4","15 2","5 12","17 24","19 4","4 24","22 2"}

    "2 4"

    Returns: 9

  7. {"0 0 0 99 30","0 99 99 99 30","99 99 99 0 30","99 0 1 0 30","1 0 1 98 30","1 98 98 98 30","98 98 98 1 30","98 1 2 1 30","2 1 2 97 30","2 97 97 97 30","97 97 97 2 30","97 2 3 2 30","3 2 3 96 30","3 96 96 96 30","96 96 96 3 30","96 3 4 3 30","4 3 4 95 30","4 95 95 95 30","95 95 95 4 30","95 4 5 4 30","5 4 5 94 30","5 94 94 94 30","94 94 94 5 30","94 5 6 5 30","6 5 6 93 30","6 93 93 93 30","93 93 93 6 30","93 6 7 6 30","7 6 7 92 30","7 92 92 92 30"}

    {"0 0","1 1","2 2","3 3","4 4","5 5","6 6"}

    "92 92"

    Returns: 6

  8. {"0 0 0 24 60", "1 0 1 24 60", "2 0 2 24 60", "3 0 3 24 60", "4 0 4 24 60", "5 0 5 24 60", "6 0 6 24 60", "7 0 7 24 60", "8 0 8 24 60", "9 0 9 24 60", "10 0 10 24 60", "11 0 11 24 60", "12 0 12 24 60", "13 0 13 24 60", "14 0 14 24 60", "0 0 24 0 30", "0 1 24 1 30", "0 2 24 2 30", "0 3 24 3 30", "0 4 24 4 30", "0 5 24 5 30", "0 6 24 6 30", "0 7 24 7 30", "0 8 24 8 30", "0 9 24 9 30", "0 10 24 10 30", "0 11 24 11 30", "0 12 24 12 30", "0 13 24 13 30", "0 14 24 14 30"}

    {"1 0"}

    "0 0"

    Returns: 0

  9. {"0 0 0 24 60", "1 0 1 24 60", "2 0 2 24 60", "3 0 3 24 60", "4 0 4 24 60", "5 0 5 24 60", "6 0 6 24 60", "7 0 7 24 60", "8 0 8 24 60", "9 0 9 24 60", "10 0 10 24 60", "11 0 11 24 60", "12 0 12 24 60", "13 0 13 24 60", "14 0 14 24 60", "0 0 24 0 30", "0 1 24 1 30", "0 2 24 2 30", "0 3 24 3 30", "0 4 24 4 30", "0 5 24 5 30", "0 6 24 6 30", "0 7 24 7 30", "0 8 24 8 30", "0 9 24 9 30", "0 10 24 10 30", "0 11 24 11 30", "0 12 24 12 30", "0 13 24 13 30", "0 14 24 14 30"}

    {"23 0"}

    "24 0"

    Returns: 0

  10. {"0 0 0 24 35","1 0 1 24 60","2 0 2 24 30","3 0 3 24 50","4 0 4 24 50","5 0 5 24 35","6 0 6 24 60","7 0 7 24 30","8 0 8 24 35","9 0 9 24 35","10 0 10 24 40","11 0 11 24 40","12 0 12 24 60","13 0 13 24 35","14 0 14 24 40","0 0 24 0 40","0 1 24 1 30","0 2 24 2 30","0 3 24 3 55","0 4 24 4 35","0 5 24 5 45","0 6 24 6 35","0 7 24 7 50","0 8 24 8 45","0 9 24 9 50","0 10 24 10 45","0 11 24 11 55","0 12 24 12 60","0 13 24 13 45","0 14 24 14 40"}

    {"12 12","14 10","12 9","13 3","12 8","14 4","14 4","5 3","7 5","6 9","10 4","13 2","6 0","3 5","9 8","4 9","1 11","6 11","0 7","5 5"}

    "0 12"

    Returns: 16

  11. {"0 0 0 24 60","1 0 1 24 60","2 0 2 24 55","3 0 3 24 55","4 0 4 24 60","5 0 5 24 40","6 0 6 24 30","7 0 7 24 50","8 0 8 24 40","9 0 9 24 35","10 0 10 24 50","11 0 11 24 55","12 0 12 24 50","13 0 13 24 40","14 0 14 24 50","0 0 24 0 50","0 1 24 1 60","0 2 24 2 40","0 3 24 3 35","0 4 24 4 40","0 5 24 5 50","0 6 24 6 40","0 7 24 7 50","0 8 24 8 30","0 9 24 9 35","0 10 24 10 60","0 11 24 11 40","0 12 24 12 30","0 13 24 13 55","0 14 24 14 60"}

    {"1 8","1 0","7 8","3 10","10 2","0 12","9 3","11 12","14 9","2 9","9 4","11 2","10 1","6 8","11 2","5 1","2 4","4 12","7 1","10 10"}

    "7 12"

    Returns: 2

  12. {"0 0 0 24 30","1 0 1 24 60","2 0 2 24 55","3 0 3 24 40","4 0 4 24 45","5 0 5 24 30","6 0 6 24 45","7 0 7 24 50","8 0 8 24 30","9 0 9 24 40","10 0 10 24 60","11 0 11 24 60","12 0 12 24 35","13 0 13 24 45","14 0 14 24 60","0 0 24 0 45","0 1 24 1 55","0 2 24 2 50","0 3 24 3 35","0 4 24 4 40","0 5 24 5 40","0 6 24 6 55","0 7 24 7 55","0 8 24 8 55","0 9 24 9 35","0 10 24 10 60","0 11 24 11 40","0 12 24 12 50","0 13 24 13 45","0 14 24 14 40"}

    {"7 13","7 0","5 4","12 5","12 2","13 3","11 2","2 2","8 10","5 13","13 0","6 13","6 12","11 5","1 12","0 6","13 7","14 14","3 4","7 11"}

    "0 3"

    Returns: 7

  13. {"0 0 0 24 30","1 0 1 24 50","2 0 2 24 40","3 0 3 24 60","4 0 4 24 50","5 0 5 24 50","6 0 6 24 30","7 0 7 24 50","8 0 8 24 55","9 0 9 24 35","10 0 10 24 35","11 0 11 24 40","12 0 12 24 40","13 0 13 24 30","14 0 14 24 30","0 0 24 0 35","0 1 24 1 50","0 2 24 2 40","0 3 24 3 60","0 4 24 4 35","0 5 24 5 30","0 6 24 6 45","0 7 24 7 45","0 8 24 8 35","0 9 24 9 40","0 10 24 10 45","0 11 24 11 30","0 12 24 12 40","0 13 24 13 55","0 14 24 14 45"}

    {"5 2","1 6","4 0","1 6","0 9","8 11","13 14","14 14","5 6","1 9","13 13","4 5","6 9","8 0","13 12","0 4","2 1","7 10","10 10","11 5"}

    "6 8"

    Returns: 12

  14. {"0 0 0 24 40","1 0 1 24 40","2 0 2 24 50","3 0 3 24 35","4 0 4 24 55","5 0 5 24 45","6 0 6 24 40","7 0 7 24 45","8 0 8 24 50","9 0 9 24 50","10 0 10 24 60","11 0 11 24 50","12 0 12 24 50","13 0 13 24 30","14 0 14 24 60","0 0 24 0 60","0 1 24 1 50","0 2 24 2 50","0 3 24 3 35","0 4 24 4 50","0 5 24 5 50","0 6 24 6 55","0 7 24 7 45","0 8 24 8 45","0 9 24 9 40","0 10 24 10 35","0 11 24 11 50","0 12 24 12 35","0 13 24 13 30","0 14 24 14 50"}

    {"9 1","5 10","12 8","13 1","9 14","2 0","0 11","12 13","9 12","4 1","8 6","2 12","8 12","7 6","6 12","5 3","3 4","12 5","5 8","8 10"}

    "11 6"

    Returns: 17

  15. {"0 0 0 24 55","1 0 1 24 55","2 0 2 24 40","3 0 3 24 40","4 0 4 24 35","5 0 5 24 60","6 0 6 24 45","7 0 7 24 45","8 0 8 24 60","9 0 9 24 30","10 0 10 24 55","11 0 11 24 35","12 0 12 24 50","13 0 13 24 60","14 0 14 24 60","0 0 24 0 50","0 1 24 1 40","0 2 24 2 45","0 3 24 3 45","0 4 24 4 55","0 5 24 5 30","0 6 24 6 55","0 7 24 7 30","0 8 24 8 55","0 9 24 9 45","0 10 24 10 30","0 11 24 11 60","0 12 24 12 35","0 13 24 13 55","0 14 24 14 40"}

    {"0 1","9 2","10 9","6 8","1 9","11 4","7 13","8 14","14 2","9 8","9 6","10 9","0 9","0 3","1 3","2 5","4 13","2 1","4 7","11 9"}

    "4 9"

    Returns: 3

  16. {"0 0 0 24 35","1 0 1 24 35","2 0 2 24 30","3 0 3 24 50","4 0 4 24 55","5 0 5 24 35","6 0 6 24 40","7 0 7 24 40","8 0 8 24 35","9 0 9 24 60","10 0 10 24 50","11 0 11 24 45","12 0 12 24 35","13 0 13 24 40","14 0 14 24 45","0 0 24 0 40","0 1 24 1 35","0 2 24 2 60","0 3 24 3 60","0 4 24 4 35","0 5 24 5 45","0 6 24 6 35","0 7 24 7 35","0 8 24 8 30","0 9 24 9 50","0 10 24 10 55","0 11 24 11 35","0 12 24 12 45","0 13 24 13 60","0 14 24 14 45"}

    {"9 6","8 4","11 5","13 5","8 12","8 12","13 4","0 3","9 0","11 9","9 2","5 1","6 8","8 3","6 1","11 11","12 1","6 14","9 9","6 2"}

    "6 6"

    Returns: 12

  17. {"0 0 0 24 35","1 0 1 24 35","2 0 2 24 30","3 0 3 24 50","4 0 4 24 55","5 0 5 24 35","6 0 6 24 40","7 0 7 24 40","8 0 8 24 35","9 0 9 24 60","10 0 10 24 50","11 0 11 24 45","12 0 12 24 35","13 0 13 24 40","14 0 14 24 45","0 0 24 0 40","0 1 24 1 35","0 2 24 2 60","0 3 24 3 60","0 4 24 4 35","0 5 24 5 45","0 6 24 6 35","0 7 24 7 35","0 8 24 8 30","0 9 24 9 50","0 10 24 10 55","0 11 24 11 35","0 12 24 12 45","0 13 24 13 60","0 14 24 14 45"}

    {"9 6","8 4","11 5","13 5","8 12","8 12","13 4","0 3","9 0","11 9","9 2","5 1","6 8","8 3","6 1","11 11","12 1","6 14","9 9","6 2"}

    "6 6"

    Returns: 12

  18. {"0 0 0 24 35","1 0 1 24 35","2 0 2 24 30","3 0 3 24 50","4 0 4 24 55","5 0 5 24 35","6 0 6 24 40","7 0 7 24 40","8 0 8 24 35","9 0 9 24 60","10 0 10 24 50","11 0 11 24 45","12 0 12 24 35","13 0 13 24 40","14 0 14 24 45","0 0 24 0 40","0 1 24 1 35","0 2 24 2 60","0 3 24 3 60","0 4 24 4 35","0 5 24 5 45","0 6 24 6 35","0 7 24 7 35","0 8 24 8 30","0 9 24 9 50","0 10 24 10 55","0 11 24 11 35","0 12 24 12 45","0 13 24 13 60","0 14 24 14 45"}

    {"9 6","8 4","11 5","13 5","8 12","8 12","13 4","0 3","9 0","11 9","9 2","5 1","6 8","8 3","6 1","11 11","12 1","6 14","9 9","6 2"}

    "6 6"

    Returns: 12

  19. {"0 0 0 24 55","1 0 1 24 30","2 0 2 24 40","3 0 3 24 50","4 0 4 24 55","5 0 5 24 60","6 0 6 24 60","7 0 7 24 55","8 0 8 24 30","9 0 9 24 30","10 0 10 24 55","11 0 11 24 45","12 0 12 24 45","13 0 13 24 55","14 0 14 24 40","0 0 24 0 60","0 1 24 1 45","0 2 24 2 50","0 3 24 3 55","0 4 24 4 40","0 5 24 5 50","0 6 24 6 45","0 7 24 7 55","0 8 24 8 50","0 9 24 9 55","0 10 24 10 30","0 11 24 11 55","0 12 24 12 30","0 13 24 13 40","0 14 24 14 50"}

    {"12 2","7 7","3 4","3 14","0 6","5 2","14 3","4 11","6 12","2 9","0 3","10 8","7 4","9 11","6 8","2 13","4 1","9 7","7 10","11 11"}

    "4 13"

    Returns: 7

  20. {"0 0 0 24 55","1 0 1 24 30","2 0 2 24 40","3 0 3 24 50","4 0 4 24 55","5 0 5 24 60","6 0 6 24 60","7 0 7 24 55","8 0 8 24 30","9 0 9 24 30","10 0 10 24 55","11 0 11 24 45","12 0 12 24 45","13 0 13 24 55","14 0 14 24 40","0 0 24 0 60","0 1 24 1 45","0 2 24 2 50","0 3 24 3 55","0 4 24 4 40","0 5 24 5 50","0 6 24 6 45","0 7 24 7 55","0 8 24 8 50","0 9 24 9 55","0 10 24 10 30","0 11 24 11 55","0 12 24 12 30","0 13 24 13 40","0 14 24 14 50"}

    {"12 2","7 7","3 4","3 14","0 6","5 2","14 3","4 11","6 12","2 9","0 3","10 8","7 4","9 11","6 8","2 13","4 1","9 7","7 10","11 11"}

    "4 13"

    Returns: 7

  21. {"0 0 0 24 40","1 0 1 24 60","2 0 2 24 55","3 0 3 24 35","4 0 4 24 35","5 0 5 24 45","6 0 6 24 45","7 0 7 24 35","8 0 8 24 40","9 0 9 24 50","10 0 10 24 35","11 0 11 24 50","12 0 12 24 60","13 0 13 24 50","14 0 14 24 50","0 0 24 0 35","0 1 24 1 45","0 2 24 2 50","0 3 24 3 55","0 4 24 4 30","0 5 24 5 55","0 6 24 6 60","0 7 24 7 55","0 8 24 8 55","0 9 24 9 35","0 10 24 10 35","0 11 24 11 55","0 12 24 12 40","0 13 24 13 55","0 14 24 14 35"}

    {"8 8","7 5","1 9","14 10","2 0","1 12","5 3","4 13","13 3","11 11","1 9","6 2","8 9","10 14","5 12","7 5","1 2","13 14","14 2","6 6"}

    "9 6"

    Returns: 19

  22. {"0 0 0 24 40","1 0 1 24 30","2 0 2 24 40","3 0 3 24 50","4 0 4 24 35","5 0 5 24 40","6 0 6 24 55","7 0 7 24 60","8 0 8 24 50","9 0 9 24 55","10 0 10 24 60","11 0 11 24 40","12 0 12 24 45","13 0 13 24 40","14 0 14 24 55","0 0 24 0 40","0 1 24 1 55","0 2 24 2 30","0 3 24 3 40","0 4 24 4 30","0 5 24 5 50","0 6 24 6 60","0 7 24 7 30","0 8 24 8 40","0 9 24 9 45","0 10 24 10 40","0 11 24 11 55","0 12 24 12 55","0 13 24 13 30","0 14 24 14 40"}

    {"6 13","9 13","5 11","5 5","2 7","3 13","2 8","14 4","14 3","4 8","10 6","11 13","5 3","10 9","6 11","7 4","13 5","14 0","10 13","6 6"}

    "1 2"

    Returns: 12

  23. {"0 0 0 24 40","1 0 1 24 30","2 0 2 24 40","3 0 3 24 50","4 0 4 24 35","5 0 5 24 40","6 0 6 24 55","7 0 7 24 60","8 0 8 24 50","9 0 9 24 55","10 0 10 24 60","11 0 11 24 40","12 0 12 24 45","13 0 13 24 40","14 0 14 24 55","0 0 24 0 40","0 1 24 1 55","0 2 24 2 30","0 3 24 3 40","0 4 24 4 30","0 5 24 5 50","0 6 24 6 60","0 7 24 7 30","0 8 24 8 40","0 9 24 9 45","0 10 24 10 40","0 11 24 11 55","0 12 24 12 55","0 13 24 13 30","0 14 24 14 40"}

    {"6 13","9 13","5 11","5 5","2 7","3 13","2 8","14 4","14 3","4 8","10 6","11 13","5 3","10 9","6 11","7 4","13 5","14 0","10 13","6 6"}

    "1 2"

    Returns: 12

  24. {"0 0 0 24 40","1 0 1 24 30","2 0 2 24 40","3 0 3 24 50","4 0 4 24 35","5 0 5 24 40","6 0 6 24 55","7 0 7 24 60","8 0 8 24 50","9 0 9 24 55","10 0 10 24 60","11 0 11 24 40","12 0 12 24 45","13 0 13 24 40","14 0 14 24 55","0 0 24 0 40","0 1 24 1 55","0 2 24 2 30","0 3 24 3 40","0 4 24 4 30","0 5 24 5 50","0 6 24 6 60","0 7 24 7 30","0 8 24 8 40","0 9 24 9 45","0 10 24 10 40","0 11 24 11 55","0 12 24 12 55","0 13 24 13 30","0 14 24 14 40"}

    {"6 13","9 13","5 11","5 5","2 7","3 13","2 8","14 4","14 3","4 8","10 6","11 13","5 3","10 9","6 11","7 4","13 5","14 0","10 13","6 6"}

    "1 2"

    Returns: 12

  25. {"0 0 0 24 50","1 0 1 24 55","2 0 2 24 35","3 0 3 24 60","4 0 4 24 50","5 0 5 24 35","6 0 6 24 60","7 0 7 24 30","8 0 8 24 30","9 0 9 24 45","10 0 10 24 30","11 0 11 24 55","12 0 12 24 50","13 0 13 24 35","14 0 14 24 45","0 0 24 0 60","0 1 24 1 40","0 2 24 2 50","0 3 24 3 55","0 4 24 4 50","0 5 24 5 35","0 6 24 6 55","0 7 24 7 40","0 8 24 8 40","0 9 24 9 50","0 10 24 10 60","0 11 24 11 40","0 12 24 12 40","0 13 24 13 30","0 14 24 14 60"}

    {"14 7","5 13","2 3","4 3","2 5","5 3","13 6","0 4","9 10","10 7","10 5","12 2","7 3","1 1","8 10","4 1","7 11","12 12","3 1","14 8"}

    "9 3"

    Returns: 12

  26. {"0 0 0 24 40","1 0 1 24 30","2 0 2 24 40","3 0 3 24 60","4 0 4 24 45","5 0 5 24 50","6 0 6 24 30","7 0 7 24 45","8 0 8 24 55","9 0 9 24 35","10 0 10 24 50","11 0 11 24 30","12 0 12 24 30","13 0 13 24 40","14 0 14 24 30","0 0 24 0 40","0 1 24 1 30","0 2 24 2 60","0 3 24 3 30","0 4 24 4 50","0 5 24 5 60","0 6 24 6 40","0 7 24 7 55","0 8 24 8 60","0 9 24 9 35","0 10 24 10 45","0 11 24 11 30","0 12 24 12 35","0 13 24 13 40","0 14 24 14 50"}

    {"13 12","13 13","10 11","9 3","7 12","8 0","8 4","1 4","7 10","12 7","6 10","3 4","2 14","14 9","4 3","6 2","1 12","6 11","9 1","0 11"}

    "4 5"

    Returns: 11

  27. {"0 0 0 24 40","1 0 1 24 40","2 0 2 24 35","3 0 3 24 40","4 0 4 24 55","5 0 5 24 45","6 0 6 24 35","7 0 7 24 40","8 0 8 24 50","9 0 9 24 40","10 0 10 24 55","11 0 11 24 30","12 0 12 24 35","13 0 13 24 35","14 0 14 24 30","0 0 24 0 35","0 1 24 1 45","0 2 24 2 30","0 3 24 3 35","0 4 24 4 30","0 5 24 5 40","0 6 24 6 45","0 7 24 7 45","0 8 24 8 40","0 9 24 9 55","0 10 24 10 55","0 11 24 11 55","0 12 24 12 55","0 13 24 13 60","0 14 24 14 50"}

    {"14 5","8 14","8 11","8 0","14 5","14 10","2 10","14 10","1 3","10 3","11 8","11 14","5 5","7 4","8 7","2 3","2 12","5 12","4 4","1 13"}

    "12 2"

    Returns: 9

  28. {"0 0 0 24 30","1 0 1 24 40","2 0 2 24 45","3 0 3 24 50","4 0 4 24 55","5 0 5 24 55","6 0 6 24 35","7 0 7 24 60","8 0 8 24 30","9 0 9 24 30","10 0 10 24 35","11 0 11 24 60","12 0 12 24 45","13 0 13 24 35","14 0 14 24 40","0 0 24 0 50","0 1 24 1 30","0 2 24 2 50","0 3 24 3 55","0 4 24 4 45","0 5 24 5 35","0 6 24 6 55","0 7 24 7 50","0 8 24 8 40","0 9 24 9 30","0 10 24 10 45","0 11 24 11 40","0 12 24 12 35","0 13 24 13 55","0 14 24 14 30"}

    {"4 11","14 5","1 6","1 3","10 10","14 10","5 3","10 4","10 6","12 12","4 11","9 9","13 14","2 6","5 6","8 0","10 2","12 6","11 0","14 6"}

    "10 2"

    Returns: 16

  29. {"0 0 0 24 50","1 0 1 24 50","2 0 2 24 30","3 0 3 24 30","4 0 4 24 60","5 0 5 24 30","6 0 6 24 35","7 0 7 24 30","8 0 8 24 35","9 0 9 24 60","10 0 10 24 60","11 0 11 24 55","12 0 12 24 35","13 0 13 24 45","14 0 14 24 50","0 0 24 0 55","0 1 24 1 40","0 2 24 2 50","0 3 24 3 45","0 4 24 4 35","0 5 24 5 60","0 6 24 6 40","0 7 24 7 50","0 8 24 8 45","0 9 24 9 60","0 10 24 10 45","0 11 24 11 60","0 12 24 12 45","0 13 24 13 45","0 14 24 14 55"}

    {"14 9","2 10","2 10","8 4","1 10","10 8","6 8","8 7","14 12","6 4","13 3","13 12","13 12","10 12","13 8","8 14","10 6","0 7","11 1","6 8"}

    "2 13"

    Returns: 4

  30. {"0 0 0 24 30","1 0 1 24 30","2 0 2 24 35","3 0 3 24 40","4 0 4 24 55","5 0 5 24 30","6 0 6 24 60","7 0 7 24 35","8 0 8 24 35","9 0 9 24 50","10 0 10 24 40","11 0 11 24 55","12 0 12 24 50","13 0 13 24 30","14 0 14 24 55","0 0 24 0 60","0 1 24 1 60","0 2 24 2 35","0 3 24 3 55","0 4 24 4 35","0 5 24 5 35","0 6 24 6 60","0 7 24 7 30","0 8 24 8 30","0 9 24 9 35","0 10 24 10 30","0 11 24 11 60","0 12 24 12 60","0 13 24 13 60","0 14 24 14 55"}

    {"7 10","11 14","7 5","6 13","12 1","14 13","14 4","5 9","4 12","0 9","14 5","13 8","14 4","4 0","0 9","11 0","1 0","4 6","4 13","10 8"}

    "9 8"

    Returns: 19

  31. {"0 0 0 99 30", "7 0 7 99 35", "14 0 14 99 40", "21 0 21 99 45", "28 0 28 99 50", "35 0 35 99 55", "42 0 42 99 60", "49 0 49 99 55", "56 0 56 99 50", "63 0 63 99 45", "70 0 70 99 40", "77 0 77 99 35", "99 0 99 99 30", "0 0 99 0 35", "0 2 99 2 40", "0 5 99 5 45", "0 7 99 7 50", "0 10 99 10 55", "0 62 99 62 60", "0 65 99 65 60", "0 67 99 67 60", "0 70 99 70 60", "0 72 99 72 60", "0 75 99 75 60", "0 77 99 77 60", "0 80 99 80 55", "0 85 99 85 50", "0 90 99 90 45", "0 95 99 95 40", "0 99 99 99 35"}

    {"99 0"}

    "0 0"

    Returns: 0

  32. {"0 0 3 0 30", "0 0 0 1 50", "0 1 1 1 50", "1 1 1 2 50", "1 2 2 2 50", "2 2 2 3 50"}

    {"3 0", "2 3"}

    "0 0"

    Returns: 0

  33. {"0 0 10 0 60","0 0 0 1 30"}

    {"0 0","10 0"}

    "10 0"

    Returns: 1

    Ambulance 1 is already at the caller

  34. {"10 10 10 20 60","10 21 10 30 60","10 30 99 30 30"}

    {"10 10","99 30"}

    "10 30"

    Returns: 1

  35. { "0 0 11 0 60", "0 0 0 10 55" }

    { "11 0", "0 10" }

    "0 0"

    Returns: 1

  36. { "0 0 11 0 60", "0 0 0 10 55" }

    { "11 0", "0 10" }

    "0 0"

    Returns: 1

  37. { "0 0 11 0 60", "0 0 0 10 55" }

    { "11 0", "0 10" }

    "0 0"

    Returns: 1

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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: