1058 - Baking Cakes
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 31
Solved: 7
- Description
- Tom’s birthday is coming up, and you have been put in charge of baking cakes for his monstrous birthday
party. However, you have a great number of cakes to make, and a very short amount of time, so you are not
sure that you will even finish before the party!
You have a list of different cakes to make, each requiring a certain amount of time to bake. You also
have exactly 3 ovens to bake the cakes in, and each oven can only bake one cake at a time. Assuming that
the time required to take a cake out and put another one in is negligible, can you determine the smallest
amount of time you will need to spend baking, given the list of cakes to make?
- Input
- The input test file will contain multiple cases, with each case on a single line. The line begins with an integer
n (where 1 ≤ n ≤ 40), the number of cakes to bake. Following are n integers, t1 , . . . , tn (where 1 ≤ ti ≤ 30),
indicating the time in minutes required to bake each of your cakes. End-of-input is marked by a single line
containing 0; do not process this line.
- Output
- For each test case, output on a single line the smallest amount of time, in minutes, that you need to bake
all of your cakes.
- sample input
-
1 30 3 15 10 20 5 6 7 8 9 10 0
- sample output
-
30 20 15
- hint
- source
- Stanford Local 2007