Setup
Several people need to cross from the east side of a bridge to the west side. The bridge is rickety, so no more than two people may be on the bridge at any time. It is also dark and treacherous, so whatever group of people is on the bridge must have with them the one available flashlight . As a result, the crossing must be of the form: • Two go west, • One comes back east, • Two go west, • One comes back east, • Two go west, • etc... For each person, it is known how many minutes it takes him or her to cross the bridge when traveling alone. When two people cross together, they cross at the rate of the slower person. The problem is to find the fastest way to get all the people across the bridge. |
Challenge
Write a program to solve this problem. Your program should be written in Java or C++. The input will consist of several sets of integers, one set per line. Each set gives the crossing times of the players in that instance. Each player’s crossing time will be in the range 1-100, and the number of players will be between 2 and 12 in each case. The output should be the total time needed in each instance to get across the bridge, one answer per line. Sample Input 1 2 4 7 10 1 2 3 4 2 3 6 12 1 2 3 4 5 Sample Output 2 21 11 23 16 |
Deadline
The deadline for submission is Monday, Sept. 26. Many contests and challenges offer cash awards to the winners, leaving them feeling cheap, as if their talent was available to anyone at any time for a price! This challenges offers you points! Each team or individual submitting a program is eligible for points. See rules for details. |
Submission
Email code to: challenge@cs.ecu.edu |