Statistics

Problem Statement for "Crossroads"

Problem Statement

You are watching a car race. Each car starts a different point on the x-axis, travels at the same speed, and starts at the same time. However, each car is travelling along a different road (which extends to infinity in one direction, and is stopped by the x-axis in the other direction), and each road has its own direction specified by an angle between 1 and 179, inclusive. An angle of 90 indicates that the road heads directly in the positive y direction, while an angle of 1 indicates that the road heads just a little bit north of the positive x direction. Note that cars never head in the negative y direction.



Sometimes, two or more roads intersect at some point. When this happens, the car that reaches the intersection first is able to block the intersection so that no other cars can pass through it. If two cars reach an intersection at the same time, the one with the lower index passes, while the other one is blocked.


In this picture, the cars following the red paths make it through all of the intersections, while the cars on the gray paths are blocked.
You will be given a int[] angles, where the ith element of angles is the angle between the x-axis and the road that the ith car drives on, in degrees. The order of the elements of angles corresponds to the order of the cars along the x-axis (no two cars start at the exact same location), with the first element of angles corresponding to the car with the leftmost starting position on the x-axis.

Your method should return a int[] containing the 0-based indices of all the cars that will pass all of the intersections along their roads. Your return should be sorted in ascending order.

Note that the exact locations of the cars along the x-axis do not matter. All that matters is their order, and the directions in which they head.

Definition

Class:
Crossroads
Method:
getOut
Parameters:
int[]
Returns:
int[]
Method signature:
int[] getOut(int[] angles)
(be sure your method is public)

Constraints

  • angles will contain between 1 and 50 elements, inclusive.
  • Each elemtent of angles will be between 1 and 179, inclusive.

Examples

  1. {105, 75, 25, 120, 35, 75}

    Returns: { 0, 1, 5 }

    The example from the problem statement.

  2. {1, 1, 1, 1, 1, 1}

    Returns: { 0, 1, 2, 3, 4, 5 }

    No two cars' paths will ever intersect, so they all pass all intersections.

  3. {13}

    Returns: { 0 }

    Only one car.

  4. {90, 123, 1, 23, 132, 11, 28, 179, 179, 77, 113, 91}

    Returns: { 0 }

    The first car passes all intersections. The last car will be stopped by the first car. All other cars are between those two, and will be stopped by one of them.

  5. {179, 89, 90, 91, 1}

    Returns: { 0, 2, 4 }

    Neither the first nor the last car will intersect with any other car. Car 1 and car 3 will both be stopped by car 2.

  6. {89, 91}

    Returns: { 0 }

    Both cars reach the intersection at the same time, and hence only the first one passes.

  7. {179, 178, 101, 91, 90, 89, 1}

    Returns: { 0, 1, 2, 3, 4, 5, 6 }

  8. {38, 140, 152, 179, 110, 71, 48, 54, 151, 5, 68, 17, 122, 11, 2, 165, 50, 49, 106, 124, 150, 131, 87, 37, 134, 84, 83, 170, 20, 108, 69, 132, 103, 65, 28, 41, 77, 144, 93, 178, 135, 62, 31, 118}

    Returns: { 1, 4, 18, 22, 41 }

  9. {12, 126, 91, 27, 171, 26, 163, 125, 55, 77, 13, 174, 123, 28, 158, 148, 105, 35, 32, 147, 86, 132, 73, 51, 102, 136}

    Returns: { 1, 2, 20 }

  10. {86, 23, 66, 150, 7, 93, 119, 77, 19, 170, 165, 99, 62, 85, 68, 152, 57, 82, 49, 177, 54, 133, 102, 36, 137, 151, 72, 90, 160, 5, 179, 103, 10, 96, 35, 113, 118}

    Returns: { 5, 27 }

  11. {151, 23, 20, 134, 57, 169, 52, 61, 26, 132, 150}

    Returns: { 0, 3, 7 }

  12. {108, 134, 46, 26, 1, 11, 145, 153, 38, 21, 100, 3, 82, 135, 123, 98, 14, 79, 37, 125, 52, 42, 104, 96, 113, 29, 91, 173, 166, 35, 61, 32, 179, 18, 112, 17}

    Returns: { 0, 10, 23, 26, 35 }

  13. {167, 9, 161, 52, 41, 138, 74, 37, 113, 109, 81, 84, 108, 114, 154, 149, 112, 130, 102, 68, 33, 133, 100}

    Returns: { 0, 2, 11 }

  14. {44, 34, 109, 126, 105, 63, 89, 15, 133, 110, 112, 124, 145, 27, 104, 156, 164, 111, 131, 8, 120, 175, 57, 102, 55, 32, 20, 153, 134, 28, 59, 14, 115, 147, 98, 81, 74, 54, 84, 90, 58, 149, 172, 157, 130, 170}

    Returns: { 2, 4, 39, 40 }

  15. {12, 141, 94, 110, 172, 13, 157, 118}

    Returns: { 1, 2 }

  16. {19, 91, 41, 52, 165, 99, 119, 21, 89, 68, 143, 92, 69, 124, 96, 109, 71}

    Returns: { 1, 8, 16 }

  17. {127, 19}

    Returns: { 0, 1 }

  18. {155, 89, 134, 69, 141, 99, 64, 172, 113, 32, 68, 24, 171, 110, 5, 60, 11, 115, 152, 107, 130, 153, 3, 23, 127, 111, 39, 12, 31, 112, 62, 58}

    Returns: { 0, 1, 30, 31 }

  19. {119, 144, 145, 95, 110, 143, 162, 26, 113, 73, 46, 25, 154, 12, 77, 103, 55, 99, 41, 56}

    Returns: { 0, 3, 19 }

  20. {145, 25, 51, 142, 161, 134, 111}

    Returns: { 0, 6 }

  21. {154, 41, 155, 42, 45, 98, 177, 10, 15, 94, 77, 17, 47, 160, 27, 23, 167, 9, 11}

    Returns: { 0, 5, 9, 10, 12, 14, 15, 18 }

  22. {164, 72, 78, 170, 150, 96, 151, 125, 47, 1, 95, 171, 44, 105, 46, 123, 160, 2}

    Returns: { 0, 5, 10, 17 }

  23. {108, 141, 104, 26, 40, 69, 1, 75, 15, 119, 154, 12, 146, 124, 144, 95, 123, 131, 140, 6, 156, 116, 127, 16, 99, 170, 11, 50, 176, 112, 53, 166, 66, 125, 28, 44, 94, 162, 20, 80, 31, 175, 139, 38, 82, 135, 21, 73}

    Returns: { 0, 2, 15, 36, 44, 47 }

  24. {178, 7, 46, 34, 45, 28, 112, 159, 169, 36, 140, 116, 118, 163, 82, 165, 119}

    Returns: { 0, 6, 14 }

  25. {114, 102, 76, 169, 97, 104, 46, 72, 63}

    Returns: { 0, 1, 4, 7, 8 }

  26. {143, 36, 13}

    Returns: { 0, 1, 2 }

  27. {106, 13, 36, 28, 116, 82, 109, 125, 80, 123, 72, 150, 107, 171, 157, 71, 177, 34, 161, 103, 113}

    Returns: { 0, 5, 8 }

  28. {9, 52, 47, 73, 161, 128, 131, 71, 72, 162, 56, 70, 103, 64, 132, 134, 133, 25, 36, 49, 122, 164, 66, 93, 20, 163, 37, 118, 79, 124, 17, 15, 14, 5, 125, 26}

    Returns: { 12, 23, 28, 35 }

  29. {13, 121, 130, 36, 125, 111, 118, 98, 18, 9, 175, 84, 174, 131, 96, 122, 67, 70, 145, 31, 11}

    Returns: { 1, 5, 7, 11, 17, 19, 20 }

  30. {141, 39, 58, 87, 2, 79, 91, 109, 136, 72, 63, 151, 169, 112, 179, 10, 101}

    Returns: { 0, 6 }

  31. {70, 55, 51, 5, 110, 71, 4, 6, 82, 154, 168, 72, 131, 145, 157, 105, 107, 15, 143, 83, 106, 102, 147, 121, 62, 2, 48, 42, 139, 67, 156, 21, 130, 113, 161, 33, 96, 162, 140, 173, 36, 171, 152, 160}

    Returns: { 36, 40 }

  32. {34, 111, 48, 45, 132, 142, 31, 128, 87, 15, 145, 154, 23, 56, 103, 85, 137, 35, 131, 179, 3, 116, 124, 32, 13, 50, 122, 151, 100, 67, 140, 42}

    Returns: { 1, 8, 15, 29, 31 }

  33. {42, 37, 174, 51, 5, 138, 28, 9, 2, 63, 116, 62, 75, 17, 98, 126, 61, 118, 157, 96, 103, 10, 84, 47, 77, 155, 88, 16, 102, 128, 140, 153, 53}

    Returns: { 10, 14, 19, 26, 32 }

  34. {116, 134, 149, 138, 157, 163, 164, 94, 79, 20, 64, 148, 77, 31, 1, 118, 139, 12, 17, 70, 123, 145, 28, 26, 9, 62, 4, 176, 10, 115, 78, 44, 71, 141, 5, 25, 114, 99, 177, 83, 39, 54, 87, 109}

    Returns: { 0, 7, 42 }

  35. {177, 136, 28, 82, 128, 179, 139}

    Returns: { 0, 1, 3 }

  36. {112, 170, 124, 52, 102, 99, 128, 45, 98, 89, 171, 120, 138, 80, 144, 134, 178, 37, 113, 163, 106, 165, 91, 88, 81, 160, 169, 33, 46, 131, 8, 115, 7}

    Returns: { 0, 4, 5, 8, 9, 23, 24, 32 }

  37. {98, 80, 11, 179, 23, 108, 10, 31, 119, 60, 57, 118, 74, 77, 40, 122, 30, 90, 91, 144, 78, 1, 61, 68, 24, 149, 132, 160, 116}

    Returns: { 0, 17, 20, 23 }

  38. {93, 132, 172, 84, 66, 21, 162, 148, 82, 20, 156, 137, 8, 75, 168, 13, 30, 38, 106, 22, 111, 104, 124, 131, 164, 120, 54, 145, 68, 179, 139, 37, 31}

    Returns: { 0, 3, 8, 28, 31, 32 }

  39. {33, 105, 36, 172, 35, 69, 55, 22, 9, 139, 137, 158, 1, 81, 77, 144, 83, 89, 135, 43, 101}

    Returns: { 1, 17 }

  40. {166, 161, 154, 11, 88, 114}

    Returns: { 0, 1, 2, 4 }

  41. {136, 46, 163, 142, 36, 99, 10, 94, 127, 5, 132, 100, 164, 157, 143, 55, 71, 87, 117, 1, 138, 40, 28, 11, 121, 6, 62, 125, 79, 176, 114, 53, 86, 15, 19, 26, 165, 56}

    Returns: { 0, 5, 7, 17, 32, 37 }

  42. {146, 9, 43, 161, 46, 49, 38, 42, 152, 157, 159, 110, 8, 32, 33, 64, 81, 34, 112, 98}

    Returns: { 0, 11, 19 }

  43. {94, 131, 179, 174, 156, 151, 27, 68, 51, 31, 175, 133, 129, 6, 116, 146, 132, 147, 23, 117, 164, 160, 139, 81, 2, 41, 75, 29, 165, 90, 44, 136, 163, 39, 100, 145, 153, 60, 97, 178, 67, 66, 7, 101, 72, 22}

    Returns: { 0, 29, 44, 45 }

  44. {161, 37, 169, 23, 153, 80, 40, 114, 101, 112, 76, 3, 155, 26, 48, 53, 123}

    Returns: { 0, 5, 10 }

  45. {172, 109, 142, 76, 147, 133, 25, 93, 4, 2, 134, 60, 162, 83, 138, 10, 113, 5, 123, 174, 90, 127, 48, 148, 116, 107, 152, 63, 3}

    Returns: { 0, 1, 7, 20, 27, 28 }

  46. {113, 73, 69, 5, 52, 107, 159, 78, 167, 96, 2, 175, 155, 79, 126, 60, 108, 90, 101, 7, 68, 42, 168, 154, 173}

    Returns: { 0, 9, 17, 20, 21 }

  47. {105, 14, 73, 55, 90, 15, 157, 140, 168, 106, 39, 51, 101, 45, 54, 131, 156, 42, 35, 81, 160, 103, 6, 179, 11, 111, 47, 31, 21, 89, 172}

    Returns: { 0, 4, 29 }

  48. {15, 61, 51, 93}

    Returns: { 3 }

  49. {74, 166, 108, 53, 86, 72, 171, 99, 150, 143, 144, 107, 156, 57, 169, 48, 129, 23, 139, 85, 32, 5, 8, 82, 155, 25}

    Returns: { 4, 19, 23, 25 }

  50. {39, 147}

    Returns: { 0 }

  51. {140, 118, 54, 166, 151, 44, 90, 5, 14, 6, 64, 129, 74, 33, 134, 25, 11, 95, 65, 145, 29, 162, 24, 147, 45, 103, 63, 97, 120, 156, 167, 170, 19, 28, 100, 144, 161, 13, 157, 148}

    Returns: { 0, 1, 6 }

  52. {121, 81, 51, 171, 176, 131, 107, 49, 24, 36, 108, 88, 64, 42, 86, 124, 170, 43, 92, 161, 87, 59, 97, 103, 61, 63, 31, 52}

    Returns: { 0, 11, 20, 25, 27 }

  53. {166, 133, 145, 117, 123, 49, 138, 12, 130, 154, 62, 8}

    Returns: { 0, 1, 3, 10, 11 }

  54. {4, 151, 111, 97, 109, 102, 140, 115, 125, 137, 156, 29, 76, 141, 79, 8, 91, 49, 13, 44, 176, 66, 172, 155, 61}

    Returns: { 1, 2, 3, 16, 21, 24 }

  55. {52, 10, 178, 31, 13, 40, 54, 141, 117, 15, 48, 25, 39}

    Returns: { 8, 10, 12 }

  56. { 140, 118, 54, 166, 151, 44, 90, 5, 14, 6, 64, 129, 74, 33, 134, 25, 11, 95, 65, 145, 29, 162, 24, 147, 45, 103, 63, 97, 120, 156, 167, 170, 19, 28, 100, 144, 161, 13, 157, 148 }

    Returns: { 0, 1, 6 }

  57. { 140, 118, 54, 166, 151, 44, 90, 5, 14, 6, 64, 129, 74, 33, 134, 25, 11, 95, 65, 145, 29, 162, 24, 147, 45, 103, 63, 97, 120, 156, 167, 170, 19, 28, 100, 144, 161, 13, 157, 148 }

    Returns: { 0, 1, 6 }

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: