Raining
Time limit: 20 seconds
Problem
It is an old problem:
-
One day, it was raining.
There were 4 people in Building A. They wanted
to go to another Building B that was far away
from Building A. (See the figure.)
-
Some of them could walk faster and some slower,
so they might require different times to walk from
one building to another. In particular,
the times required by them were 10 mins,
5 mins, 2 mins and 1 mins.
We call the four people p10, p5, p2 and p1, respectively.
-
They had only one umbrella, which could allow
at most 2 people to walk together at a time.
When 2 people walked together, the
time required to walk from one building to
another is the maximum of the times required by
them. E.g., when p2 and p5 walked together with
the umbrella, they required 5 mins.
The umbrella
could be moved from one building to another
only if at least one person carried it.
-
No people want to get wet.
What is the shortest time for all the
four people to reach Building B?
A possibe schedule is: p1 & p2 -> B (that means p1 & p2 walked
to Building B, using 2 mins),
p1 -> A (1 mins), p1 & p5 -> B (5 mins),
p1 -> A (1 mins), p1 & p10 -> B (10 mins). The total time for this schedule is 19 mins.
Some schedule can take
17 mins. (p1 & p2 -> B,
p1 -> A, p10 & p5 -> B, p2 -> A, p1 & p2 -> B).
This problem considers the situations
when the number of people and their
walking times are arbitrary.
Input
The input consists of a number of test cases.
Each test case starts with a line containing a single integer 1 <= n <= 10.
The next line contains n integers s1, s2, ..., sn
where 1 <= si <= 1000 is the time required for the person pi
to walk from one building to another when he walked alone.
The last test case starts with a line containing '0', and
no further lines. Do not process this case.
Output
For each test case, output a single line containing the minimum time
for all the people to reach Building B.
Sample Input
4
10 5 2 1
3
30 20 20
0
Sample Output
17
70
Author
Chan Ho Leung