* Make Sure your Output file is %100 Correct* 1) Must use COMMAND PROMPT as prog
ID: 3545771 • Letter: #
Question
* Make Sure your Output file is %100 Correct*
1) Must use COMMAND PROMPT as program I/O
Example: program.exe<file.in>file.out
2) The input file CAN NOT BE "hard coded in" NOT ALLOWED: fin = fopen("filename.in", "r");
3) CAN NOT USE fscaf OR fprintf You May Use scanf OR printf
Given a set of numbers your goal is to add them all, while minimizing the cost of the addition. At any point, you may choose to add any two of the integers. The cost of doing so is simply the sum of the two numbers. For example, the cost of adding 1 and 10 is 11. 3, 6 and 2 can be added in several different ways. The minimum cost comes from adding 2+3 first to yield 5 and 5+6 to yield 11. The total cost for these two operations is 16 (5 + 11). Given a sequence of numbers calculate the minimum cost to add them into a single integer.
Input
First line of the input contains T the number of test cases. First line of each test case contains N the number of integers in the sequence. Second line contains N integers separated by a single space. N is between 1 and 500 inclusive. Each of the integers in the sequence will be between 1 and 500.
Output
For each test case output contains a single integer denoting the minimum cost.
Sample Input: save to a text file
===========================
http://www.cs.ucf.edu/courses/cop3502/fall2013/asgn/recprogs/addall.in
===========================
Sample Output: save to a text file
* Make Sure your Output file is %100 Correct*
===========================
http://www.cs.ucf.edu/courses/cop3502/fall2013/asgn/recprogs/addall.out
===========================
Explanation / Answer
#include<stdio.h>
void sorting(int arr[],int n)
{int i,j;
//using bubble sort
for(i=0;i<n-1;i++)
for(j=0;j<n-1;j++)
if(arr[j]>arr[j+1])
arr[j]=arr[j]+arr[j+1]-(arr[j+1]=arr[j]);//swap arr[j],arr[j+1]
}
int main()
{
int t,n,i,arr[500];
scanf("%d",&t);
while(t--)
{scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
//sort the array
if(n==1)
printf("%d ",0);
else
{sorting(arr,n);
long int cost=0;
i=0;
while(arr[n-2]!=0)
{cost=arr[i]+arr[i+1]+cost;
arr[i+1]=arr[i]+arr[i+1];
arr[i]=0;
sorting(arr,n);
i++;
}
printf("%ld ",cost);
}
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.