Connect The Ropes

Time Limit: 3 sec

 

The Problem

Here is a simple problem .

 

There are given n ropes of different lengths. You need to tie these ropes into one rope. The cost of connecting two ropes is equal to sum of their lengths. You need to tie the ropes with minimum cost.

 

For example if you are given 4 ropes of lengths 4, 3, 2 and 6. You can connect the ropes in

following ways:

1) First connect ropes of lengths 2 and 3. Now you have three ropes of lengths 4, 6 and 5.

2) Now connect ropes of lengths 4 and 5. Now you have two ropes of lengths 6 and 9.

3) Finally connect the two ropes and all ropes have been connected.

Total cost for connecting all ropes is 5 + 9 + 15 = 29. This is the optimized cost for connecting

ropes. Other ways of connecting ropes would always have same or more cost.

 

For example, if you connect 4 and 6 first (you get three ropes of 3, 2 and 10), then connect 10 and 3 (you get two ropes of 13 and 2). Finally you connect 13 and 2. Total cost in this way is 10 + 13 + 15 = 38.

 

The Input

There will be several test cases T (0<T<=100) given in first line. Each case contains N (0<N<100) denoting the number of ropes.Then there will be space separated N integers to follow in the next line (All integer are positive and not greater than 100).

 

The Output

For each case you have to print “Case X: Cost=Y” in a separate line. Here X is case number start from 1 to T and Y is the cost of connecting the ropes.

 

Sample Input

1

4

4 3 2 6

 

Sample Output

Case 1: Cost=29 

 

 

 

[School & College Level]

Inter School & College Programming Contest (ISCPC) 2017

Problem Setter: Parag Paul