2013年7月6日 星期六

1377 - Ruler

小明想要製作一把特別的尺,而這個只能直接地量測到幾個給定的長度。小明希望找到一個方法,盡可能使用最少的刻度在尺上。對於每個給定的長度,要必須能在其中兩個刻度間的距離中被量測。要求刻度個數越少越好,如果相同時輸出尺最短長度的那一組。

輸入格式 Input 

測資只有少數幾筆。每一組測資有兩行,第一行有一個整數 n($1{\leq}n{\leq}50$)表示有幾個給定的長度需要被量測,第二行包含 n  個整數數字 $d_1, d_2, ... , d_n$ 表示被量測的長度( $1{\leq} d_i{\leq}10^{6}, i{\in}[1,n]$)。
最後一筆包含一個整數零,不用對此行處理。

輸出格式Output 

對於每組測資輸出三行。 第一行包含測資組數,第二行輸出整數 表示少用只用的刻度個數,第三行輸出 M 個整數表示刻度的位置。

注意:輸出的刻度由小排到大,且第一個刻度一定為 0。你可以假設所有的 M 不超過 7,即 $M{\leq}7$。


範例輸入Sample Input 

6
5 15 20 25 35 40
0

範例輸出Sample Output 

Case 1:
4
0 5 25 40