1348 - Rubik Exercise
Time Limit : 3 Second
Memory Limit : 128 MB
Submission: 35
Solved: 10
- Description
- Isun often tests his level of cubing by do consecutive 12(regarded as k) exercises & timing, then calculates the average time of all the result. You can refer to the following figure.
But sometimes Isun will do more exercise, say consecutive 100(regarded as n) times. The average time of these 100 results represents the level of Isun more exactly than average of 12.
But Isun finds the average of 100 is sometimes worse than expected, so he denies the above fact. Instead, Isun calculates the average of each consecutive 12 results, say:
Group1 : 1, 2, 3 …… 12
Group2 : 2, 3, 4 …… 13
Group3 : 3, 4, 5 …… 14
………………………………
Group89 : 89, 90, 91 …… 100
Then Isun says the shortest of these 89 averages is his real level. HaHa~
But……sometimes Isun still feels that the result is somewhat slower than expected. So Isun decides to delete at most 10(regarded as m) results, without changing the order of the remaining result, finally calculate 79 averages from the remaining 90 result, and says the shortest of these 79 is his real level.
Although this method is quite rubbish full of zhuangbility, Isun founds the result rather satisfactory, and begins to show off around.
The only thing left is how to choose the 10 results at most to make the final result best. Isun wants to know the key. Can you help him?
- Input
- The input will consist multiple cases terminates with EOF.
For each case, first line contains three integers: n, k, m.
(1<=n<=50000, 1<=k<=n, 0<=m<=n-k)
The second line contains n non-negative float numbers, indicating the result of each timing test in order (no larger than 100.0).
- Output
- For each case output the final result mentioned above with four digits after dot.
- sample input
-
5 3 0 30.0 31.0 29.0 40.0 28.0 5 3 1 30.0 31.0 29.0 40.0 28.0 5 3 2 30.0 31.0 29.0 40.0 28.0
- sample output
-
Case #1: 30.0000 Case #2: 29.3333 Case #3: 29.0000
- hint
- source
- Xu Han, HUST Campus 2009