2013年7月12日 星期五

11158 - Elegant Permuted Sum


E
Next Generation Contest 3
Time Limit: 2 seconds
Elegant Permuted Sum

給 n 個整數  <A1A2A3...An> 找到一種 n 個數字的排列方式,其中相鄰兩數字的差取絕對值加總後要最大。

假設 n = 4,這四個整數為 <4 2 1 5>,而排列 <2 5 1 4> 為最大的總和,
其總和為
sum = abs(2-5) + abs(5-1) + abs(1-4) = 3+4+3 = 10

所有的排列共有 24 種並不會有其他的總和大於 10。
因此稱這個值為 elegant permuted sum。
Input
每組第一行會有一個整數 T (T < 100) 表示測資組數。

每組測資第一個整數 n (1 < n < 51) 表示接下來會有 n 個非負整數,且每個數字不超過 1000。
Output
對於每組測資,輸出測資組編號以及  elegant permuted summation。

Sample Input
Output for Sample Input
3
4 4 2 1 5
4 1 1 1 1
2 10 1
Case 1: 10
Case 2: 0
Case 3: 9

Problem Setter: Sohel Hafiz
Special Thanks: Jane Alam Jan