Statistics

Problem Statement for "BridgeCrossing"

Problem Statement

A well-known riddle goes like this: Four people are crossing an old bridge. The bridge cannot hold more than two people at once. It is dark, so they can't walk without a flashlight, and they only have one flashlight! Furthermore, the time needed to cross the bridge varies among the people in the group. For instance, let's say that the people take 1, 2, 5 and 10 minutes to cross the bridge. When people walk together, they always walk at the speed of the slowest person. It is impossible to toss the flashlight across the bridge, so one person always has to go back with the flashlight to the others. What is the minimum amount of time needed to get all the people across the bridge?

In this instance, the answer is 17. Person number 1 and 2 cross the bridge together, spending 2 minutes. Then person 1 goes back with the flashlight, spending an additional one minute. Then person 3 and 4 cross the bridge together, spending 10 minutes. Person 2 goes back with the flashlight (2 min), and person 1 and 2 cross the bridge together (2 min). This yields a total of 2+1+10+2+2 = 17 minutes spent.

You want to create a computer program to help you solve new instances of this problem. Given an int[] times, where the elements represent the time each person spends on a crossing, your program should return the minimum possible amount of time spent crossing the bridge.

Definition

Class:
BridgeCrossing
Method:
minTime
Parameters:
int[]
Returns:
int
Method signature:
int minTime(int[] times)
(be sure your method is public)

Notes

  • In an optimal solution, exactly two people will be sent across the bridge with the flashlight each time (if possible), and exactly one person will be sent back with the flashlight each time. In other words, in an optimal solution, you will never send more than one person back from the far side at a time, and you will never send less than two people across to the far side each time (when possible).

Constraints

  • times will have between 1 and 6 elements, inclusive.
  • Each element of times will be between 1 and 100, inclusive.

Examples

  1. { 1, 2, 5, 10 }

    Returns: 17

    The example from the text.

  2. { 100, 100, 100, 100, 100, 100 }

    Returns: 900

  3. { 1, 2, 3, 4, 5 }

    Returns: 16

    One solution is: 1 and 2 cross together (2min), 1 goes back (1min), 4 and 5 cross together (5min), 2 goes back (2min), 1 and 3 cross together (3min), 1 goes back (1min), 1 and 2 cross together (2min). This yields a total of 2 + 1 + 5 + 2 + 3 + 1 + 2 = 16 minutes spent.

  4. { 100 }

    Returns: 100

    Only one person crosses the bridge once.

  5. { 1, 2, 3, 50, 99, 100 }

    Returns: 162

  6. { 2, 2 }

    Returns: 2

  7. { 99, 13, 67, 32, 5, 17 }

    Returns: 202

  8. { 44, 63, 30, 1, 9, 53 }

    Returns: 154

  9. { 57 }

    Returns: 57

  10. { 12, 52 }

    Returns: 52

  11. { 6, 9, 94, 31 }

    Returns: 127

  12. { 70 }

    Returns: 70

  13. { 18, 48, 73 }

    Returns: 139

  14. { 81, 24, 50 }

    Returns: 155

  15. { 65 }

    Returns: 65

  16. { 52, 28 }

    Returns: 52

  17. { 25, 36, 21, 45, 11 }

    Returns: 155

  18. { 85, 64, 2, 11, 37 }

    Returns: 159

  19. { 32, 30, 98, 76, 92 }

    Returns: 330

  20. { 45, 35, 26 }

    Returns: 106

  21. { 31, 28, 27, 44 }

    Returns: 155

  22. { 5, 61, 50, 21, 57 }

    Returns: 184

  23. { 73, 14, 91 }

    Returns: 178

  24. { 20, 6, 96, 50, 28, 20 }

    Returns: 222

  25. { 25, 97, 50, 57, 85, 94 }

    Returns: 464

  26. { 8, 7, 10, 55 }

    Returns: 86

  27. { 66, 84, 39, 2, 91 }

    Returns: 278

  28. { 44, 63, 30, 1, 9, 53 }

    Returns: 154

  29. { 57 }

    Returns: 57

  30. { 12, 52 }

    Returns: 52

  31. { 6, 9, 94, 31 }

    Returns: 127

  32. { 70 }

    Returns: 70

  33. { 18, 48, 73 }

    Returns: 139

  34. { 81, 24, 50 }

    Returns: 155

  35. { 65 }

    Returns: 65

  36. { 52, 28 }

    Returns: 52

  37. { 25, 36, 21, 45, 11 }

    Returns: 155

  38. { 85, 64, 2, 11, 37 }

    Returns: 159

  39. { 32, 30, 98, 76, 92 }

    Returns: 330

  40. { 45, 35, 26 }

    Returns: 106

  41. { 31, 28, 27, 44 }

    Returns: 155

  42. { 5, 61, 50, 21, 57 }

    Returns: 184

  43. { 73, 14, 91 }

    Returns: 178

  44. { 20, 6, 96, 50, 28, 20 }

    Returns: 222

  45. { 25, 97, 50, 57, 85, 94 }

    Returns: 464

  46. { 8, 7, 10, 55 }

    Returns: 86

  47. { 66, 84, 39, 2, 91 }

    Returns: 278

  48. { 100, 2, 3, 50, 99, 1 }

    Returns: 162

  49. { 11, 2, 8, 50, 2, 100 }

    Returns: 125

  50. { 1, 2 }

    Returns: 2

  51. { 100, 99, 98, 3, 2, 1 }

    Returns: 210

  52. { 1, 2, 25, 50, 99, 100 }

    Returns: 162

  53. { 1, 2, 3 }

    Returns: 6

  54. { 1, 2, 90, 91, 92, 93 }

    Returns: 196

  55. { 10, 10, 1, 10, 10 }

    Returns: 43

  56. { 1, 2, 91, 92, 93, 94 }

    Returns: 198

  57. { 100, 55, 33, 77, 22, 1 }

    Returns: 257

  58. { 1, 1, 100, 100, 100, 100 }

    Returns: 207

  59. { 1, 2, 10, 10, 10, 10 }

    Returns: 32

  60. { 1, 5, 5, 5 }

    Returns: 17

  61. { 1, 100, 100, 100, 100, 100 }

    Returns: 504

  62. { 43, 8, 62, 74, 75, 76 }

    Returns: 362

  63. { 100, 2, 3, 50, 99, 1 }

    Returns: 162

  64. { 11, 2, 8, 50, 2, 100 }

    Returns: 125

  65. { 1, 2 }

    Returns: 2

  66. { 100, 99, 98, 3, 2, 1 }

    Returns: 210

  67. { 1, 2, 25, 50, 99, 100 }

    Returns: 162

  68. { 1, 2, 3 }

    Returns: 6

  69. { 1, 2, 90, 91, 92, 93 }

    Returns: 196

  70. { 10, 10, 1, 10, 10 }

    Returns: 43

  71. { 1, 2, 91, 92, 93, 94 }

    Returns: 198

  72. { 100, 55, 33, 77, 22, 1 }

    Returns: 257

  73. { 1, 1, 100, 100, 100, 100 }

    Returns: 207

  74. { 1, 2, 10, 10, 10, 10 }

    Returns: 32

  75. { 1, 5, 5, 5 }

    Returns: 17

  76. { 1, 100, 100, 100, 100, 100 }

    Returns: 504

  77. { 43, 8, 62, 74, 75, 76 }

    Returns: 362

  78. { 100, 2, 3, 50, 99, 1 }

    Returns: 162

  79. { 11, 2, 8, 50, 2, 100 }

    Returns: 125

  80. { 1, 2 }

    Returns: 2

  81. { 100, 99, 98, 3, 2, 1 }

    Returns: 210

  82. { 1, 2, 25, 50, 99, 100 }

    Returns: 162

  83. { 1, 2, 3 }

    Returns: 6

  84. { 1, 2, 90, 91, 92, 93 }

    Returns: 196

  85. { 10, 10, 1, 10, 10 }

    Returns: 43

  86. { 1, 2, 91, 92, 93, 94 }

    Returns: 198

  87. { 100, 55, 33, 77, 22, 1 }

    Returns: 257

  88. { 1, 1, 100, 100, 100, 100 }

    Returns: 207

  89. { 1, 2, 10, 10, 10, 10 }

    Returns: 32

  90. { 1, 5, 5, 5 }

    Returns: 17

  91. { 1, 100, 100, 100, 100, 100 }

    Returns: 504

  92. { 43, 8, 62, 74, 75, 76 }

    Returns: 362

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: