The 4th(2009) ACM Programming Contest of HUST - Onsite Contest

From: 2009-12-06 12:00:00 To: 2009-12-06 17:00:00 Now: 2017-09-20 01:09:01 Status: Public

H - Rubik Exercise

Time Limit: 3s Memory Limit: 128MB

Submissions: 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