Kaylin loves mushrooms. Put them on her plate and she'll eat them up! In this problem she's eating a plate of mushrooms, and Bartholomew is putting more pieces on her plate.
In this problem, we'll look at how many pieces of mushroom are on her plate at -second intervals. Bartholomew could put any non-negative integer number of mushroom pieces down at any time, and the only way they can leave the plate is by being eaten.
Figure out the minimum number of mushrooms that Kaylin could have eaten using two different methods of computation:
- Assume Kaylin could eat any number of mushroom pieces at any time.
- Assume that, starting with the first time we look at the plate, Kaylin eats mushrooms at a constant rate whenever there are mushrooms on her plate.
For example, if the input is 10 5 15 5
:
With the first method, Kaylin must have eaten at least mushroom pieces: first she eats , then more are put on her plate, then she eats another 10. There's no way she could have eaten fewer pieces.
With the second method, Kaylin must have eaten at least mushroom pieces. We can determine that she must eat mushrooms at a rate of at least piece per second. She starts with pieces on her plate. In the first seconds, she eats pieces, and more are put on her plate. In the next seconds, she eats pieces, then her plate stays empty for seconds, and then Bartholomew puts more pieces on her plate. Then she eats pieces in the last seconds.
Input Specification
The first line of the input gives the number of test cases, . test cases follow. Each will consist of one line containing a single integer , followed by a line containing space-separated integers ; the number of mushrooms on Kaylin's plate at the start, and at -second intervals.
Output Specification
For each test case, output one line containing Case #x: y z
, where is the test case number (starting from 1), is the minimum number of mushrooms Kaylin could have eaten using the first method of computation, and is the minimum number of mushrooms Kaylin could have eaten using the second method of computation.
Limits
Memory limit: 1 GB.
.
Small Dataset
Time limit: 30 seconds.
.
.
Large Dataset
Time limit: 60 seconds.
.
.
Sample Input
4
4
10 5 15 5
2
100 100
8
81 81 81 81 81 81 81 0
6
23 90 40 0 100 9
Sample Output
Case #1: 15 25
Case #2: 0 0
Case #3: 81 567
Case #4: 181 244
Note
This problem has different time limits for different batches. If you exceed the Time Limit for any batch, the judge will incorrectly display >60.000s
regardless of the actual time taken. Refer to the Limits section for batch-specific time limits.
This problem originally had a much higher time limit. However, as reference solutions were much faster, the Time Limit was been reduced accordingly.
Comments