UVa 10037

From Algorithmist
Jump to navigation Jump to search

10037 - Bridge[edit]

Summary[edit]

  • there is a number of people n on the one side of a brigde
  • they want to get to the other side
  • bridge can hold at most 2 people at the same time
  • people need light to get throught the bridge
  • they have only one flashlight
  • one can travel through the bridge with a given speed defined as a time required to get to the other side
  • speed of a group of people is defined by the speed of its slowest member
  • find the optimal time for all people crossing the bridge

Explanation[edit]

  • this one is interesting problem based on quite simple logic
  • let 'A' be the fastest member and 'B' second fastest
  • let 'a' be the slowest member and 'b' second slowest
  • main problem is to get the slowest members (a and b) of the group to the other side, how can this be done?
    1. The fastest member goes back and forth (twice)
      • The fastest member takes the slowest member across and comes back - time = a + A
      • To take the two slowest - time = 2*A + a + b
    2. The two fastest members go, allowing the two slowest two to go together
      1. A and B go to the other side - time = B
      2. A goes back - time = A
      3. a and b cross - time = a
      4. B goes back - time = B
      • time needed: 2*B + A + a
  • So which method do we choose? Simply constructing an inequality: if (2*A + a + b < 2*B + A + a) the first is better; else second is better; for simplicity one can observe that 2*A + a + b < 2*B + A + a is the same as b + A < 2*B

Input[edit]

1

4
1
2
5
10

Output[edit]

17
1 2
1
5 10
2
1 2