Submit Best Submissions All Submissions

194. Connecting Ropes

Problem Statement:
Omar is a smart boy who likes to play with anything around him. One day his father got some ropes. Unfortunately, Omar found these ropes and decided to play with them by connecting all of the ropes with each other to get one rope.

When Omar connects 2 ropes with each other he loses one unit from each rope, so he wonders what is the length of the resulting final rope.

For example if he got 3 ropes of lengths 3, 4 and 6. He can connect 3 and 4 to get a rope of length 5, then he can connect the ropes of length 5 and 6 to get the final rope of length 9.

He will keep selecting any pair of ropes and will connect them together until there is only 1 rope left. Which ropes to connect first and which order doesn't really matter, at the end the resulting rope will be the same length regardless his decisions.

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 <= T <= 100). Followed by the test cases, each test case starts with a line containing one integer N (1 <= N <= 100) representing the number of ropes, followed by a line which contains N integers separated by a single space, representing the ropes' lengths. Each rope length will not be less than 2 and will not be greater than 100.

Output Format:
For each test case, print a single line which contains a single integer representing the length of the final resulting rope.

Sample Input:
3 3 3 4 6 2 2 2 3 10 11 12

Sample Output:
9 2 29

Added by: abdelkarim
Added at: 2014-08-09 14:00:02 UTC
Time Limit: 1 second
Partial score: No
Source:A2OJ FCI-CU Tournament 2014 - Qualification Round