10954 - Add All

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10954 - Add All

Post by brianfry713 » Wed Apr 18, 2012 11:27 pm

Use a priority_queue.
Check input and AC output for thousands of problems on uDebug!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

Re: 10954 - Add All

Post by Hasselli » Tue Apr 24, 2012 6:44 pm

brianfry713 wrote:Use a priority_queue.
I don't know what is this?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10954 - Add All

Post by brianfry713 » Wed Apr 25, 2012 1:13 am

Check input and AC output for thousands of problems on uDebug!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

Re: 10954 - Add All

Post by Hasselli » Wed Apr 25, 2012 6:30 pm

Code: Select all

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
   int n;
   cin >> n;
   while (!n == 0){
		priority_queue<int> a;
		int b;
		int cost = 0;
		int sum = 0;
		if (n == 2){
			int c;
			cin >> b >> c;
			cout << b + c;
		}
		else{
			for (int i = 1; i <= n; i++){
				cin >> b;
				a.push(b);
			}
			for (int i = 3; i<= n; i++){
				sum += cost;
				cost += a.top();
				a.pop();
			}
			sum += cost;
			cout << sum << endl;
		}
		cin >> n;
   }
}
Why wrong?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10954 - Add All

Post by brianfry713 » Thu Apr 26, 2012 2:19 am

Your algorithm is wrong and the result doesn't match the sample input.

Push the input onto the priority_queue.
Add the sum of the two smallest numbers to the cost, push the sum back on the queue. Repeat until there is only one number left on the queue.
Check input and AC output for thousands of problems on uDebug!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

Re: 10954 - Add All

Post by Hasselli » Fri Apr 27, 2012 10:34 am

Code: Select all

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
   int n;
   cin >> n;
   while (!n == 0){
      priority_queue<int> a;
      int b;
      int cost = 0;
      int sum = 0;
      if (n == 2){
         int c;
         cin >> b >> c;
         cout << b + c;
      }
      else{
         for (int i = 1; i <= n; i++){
            cin >> b;
            a.push(b);
         }
		 while (a.size() > 1){
			 b = a.top();
			 a.pop();
			 a.push(a.top() + b); 
			 a.pop();
		 }
		 cout << a.top() << endl;
      }
      cin >> n;
   }
}
Do you mean this?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10954 - Add All

Post by brianfry713 » Fri Apr 27, 2012 8:53 pm

No. That doesn't match the sample input. First read the two smallest elements from the priority_queue. Then add the sum to the cost and place the sum back on the priority_queue. Don't output the final sum that should be on the priority_queue, but the cost.
Check input and AC output for thousands of problems on uDebug!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

Re: 10954 - Add All

Post by Hasselli » Sat Apr 28, 2012 5:26 am

How to find two smallest?

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

Re: 10954 - Add All

Post by Hasselli » Sun Apr 29, 2012 8:00 pm

error C2064: term does not evaluate to a function taking 2 arguments xutility

I got this error with this code:

Code: Select all

removed after AC
Last edited by Hasselli on Sat May 05, 2012 5:44 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10954 - Add All

Post by brianfry713 » Mon Apr 30, 2012 9:54 pm

priority_queue< int, vector<int>, greater<int> > a;
Check input and AC output for thousands of problems on uDebug!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

Re: 10954 - Add All

Post by Hasselli » Sat May 05, 2012 5:43 pm

Thank you very much Brian.

sumon sarker
New poster
Posts: 4
Joined: Tue Mar 20, 2012 7:58 am
Location: Dhaka,Bangladesh
Contact:

Re: 10954 - Add All

Post by sumon sarker » Mon Jul 16, 2012 6:16 pm

I am getting wrong answer! Please give me some other sample input/output.........

shuvrothpol1
New poster
Posts: 17
Joined: Wed Aug 15, 2012 12:37 pm

Re: 10954 - Add All

Post by shuvrothpol1 » Wed Aug 15, 2012 1:14 pm

6
9 9 9 9 9 9
how can it possible that the answer is 144 ? The answer should be 180. Shouldn't it ? If I am wrong please inform me where is my mistake.Because, i got WA of it.Besides, I use bubble sort to solve the problem ..

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10954 - Add All

Post by brianfry713 » Wed Aug 15, 2012 9:50 pm

9,9,9,9,9,9
9+9=18, total cost=18
9,9,9,9,18
9+9=18, total cost=36
9,9,18,18
9+9=18, total cost=54
18,18,18
18+18=36, total cost=90
18,36
18+36=54, total cost=144
Check input and AC output for thousands of problems on uDebug!

CyberPunk
New poster
Posts: 7
Joined: Sat Mar 02, 2013 11:11 pm

Re: 10954 - Add All

Post by CyberPunk » Tue Mar 19, 2013 5:39 pm

Code: Select all

#include <stdio.h>
#include <string.h>
void sort(long long int array[], long long int length)
{
    long long int i,j,count,pos,min[10000][2];

    for(i=0;i<length;i++) {
        min[i][1]=0;
    }
    for(i=0;i<length;i++) {
        count=0;
        for(j=0;j<length;j++) {
            if(array[i]<array[j]) count++;
        }
        pos=++min[count][1];
        min[count+pos-1][0]=array[i];
    }
    for(i=0;i<length;i++) array[i]=min[i][0];
}

int main()
{
    long long int num[10000],N,i,j,k,l,sum,temp;
    while(scanf("%lld",&N)==1 && N) {
        i=0;
        for(i=0;i<N;i++) scanf("%lld",&num[i]);
        sort(num,N);
        sum=0,temp=0;
        if(N==1) printf("%lld\n",num[0]);
        else {
            for(i=N-1;i-1>=0;i--) {
                temp=num[i-1]+num[i];
                sum+=temp;
                num[i-1]=temp;
                num[i]=0;
                sort(num,N);
            }

            printf("%lld\n",sum);
        }
        memset(num,0,sizeof(num));
    }
    return 0;
}
why do i get TLE? any suggestions?

Post Reply

Return to “Volume 109 (10900-10999)”