提示: 欢迎访问OurACM平台。
Problem 2010 AekdyCoin’s loves

Accept: 71    Submit: 351
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Do you want to know AekdyCoin’s favorite thing? Of course, the answer is yes. He loves MM, math and so on.

Recently, AekdyCoin love giantarum so much. He likes eat konjac very much, but he wants to spend as little as may be and eat more giantarum. As we known, he is “** ** ** **, **** *** *** ***” and loves math. Now AekdyCoin would like to predict the price of giantarum (the price of giantarum is changing every day).

Based on data on the past daily prices, he plans to use a weighted average of the 5 most recent prices as the prediction. That is to say, if he wants to predict the price in day 13, then he must use the prices in day 8, 9, 10, 11, 12. He will choose the appropriate coefficients in the following 21 values.

-1.0, -0.9 ... 0.0 ..., 0.9, 1.0 (The gap is 0.1)

The coefficients must add up to exactly one (some of them may be negative). For example, if he chooses {0.5 , 0.5 , -0.5 , -0.5 , 1.0 } as the coefficients, and he wants to predict the price in day 13, and the price in day 8, 9, 10, 11, 12 is 3.0, 2.2, 1.5, 4.7, 5.2 , then the price he predicted (in day 13) is :

3.0 * 0.5 + 2.2 * 0.5 + 1.5 * (-0.5) + 4.7 * (-0.5) + 5.2 * 1.0

As the “** ** ** **, **** *** *** ***”, AekdyCoin define the “error” of a prediction to be the absolute value of the difference between the prediction and the price. He will evaluate a possible weighting by using it to predict each of the known prices. (Except for the first 5 days) He will then choose the weighting that has the smallest average error for its predictions.

Before he uses the best weighted averaging scheme to make his fortune on the market, he needs to have some idea of how well it predicted past data.

Input

There are multiple test cases. The first line in the input is an integer T (T<= 10) indicating the number of test cases.

For each test case:

The first line is an integer n (5 < n <= 50) indicating the number of data on past daily prices. The second line has n numbers.

Output

For each test case, print a line containing the test case number (beginning from 1) and the smallest average error (Accurate to 0.00).

Sample Input

2 6 10.0 10.0 10.0 10.0 10.0 10.0 12 50.0 10.0 50.0 10.0 50.0 10.0 50.0 10.0 50.0 10.0 50.0 10.0

Sample Output

Case 1: 0.00 Case 2: 0.00

Hint

In Case 1, he predicts the price in day 6 is exactly 10.00 no matter what coefficients he choose (He starts predict from day 6.)

In Case 2, a weighting of -1, 0,0,1,1 predicts price correctly every time (in the past).

Source

FOJ有奖月赛-2011年03月

Submit  Back  Status  Discuss