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 »

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

WS Ayan
New poster
Posts: 1
Joined: Wed Mar 27, 2013 12:17 am

10954 time limit

Post by WS Ayan »

i am getting time limit in 10954 . :oops: I have tried it with priority queue and vector both. Some suggestions are badly needed. :( Here are the codes:
Using Priority Queue:

Code: Select all

#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
using namespace std;
int main()
{
    long long i,n,x,y,sum1,sum2;
    while(cin>>n && n)
    {
        priority_queue<long long>q;
        stack<long long>s;
        while(n--)
        {
            cin>>x;
            q.push(x);
        }
        sum1=0;
        sum2=0;
        while(q.size()!=1)
        {
            if(q.size()>2)
            {
                s.push(q.top());
                q.pop();
            }
            else
            {
                x=q.top();
                q.pop();
                y=q.top();
                q.pop();
                sum1=x+y;
                sum2=sum2+sum1;
                q.push(sum1);
                while(!s.empty())
                {
                    q.push(s.top());
                    s.pop();
                }
            }
        }
        cout<<sum2<<endl;
        /*FILE* fp;
        fp=fopen("G:\\g_output10954.txt","w");
        fprintf(fp,"%lld\n",sum2);*/

    }
return 0;
}


Using Stack:

Code: Select all

#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    long long i,n,x,y,sum1,sum2;
    while(cin>>n && n)
    {
        vector<long long>v;
		while(n--)
        {
            cin>>x;
            v.push_back(x);
        }
        sum1=0;
        sum2=0;
        while(v.size()!=1)
        {
           sort(v.begin(),v.end());
		   x=v[0];
			v.erase(v.begin()+0);
			if(!v.empty())
			{
				y=v[0];
				v.erase(v.begin()+0);
			}
			else
				y=0;
			
			sum1=x+y;
            sum2=sum2+sum1;
            v.push_back(sum1);
          }
        cout<<sum2<<endl;
       

    }
return 0;
}

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

Re: 10954 time limit

Post by brianfry713 »

Use just a priority_queue, you don't need a stack.
Check input and AC output for thousands of problems on uDebug!

Kaiser
New poster
Posts: 2
Joined: Tue Sep 03, 2013 8:56 pm

Re: 10954 time limit

Post by Kaiser »

I just use a vector and at first got TLE. :( then i optimize the code and get AC. :D But it took 2.8 sec.Probably the worst runtime.

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10954 - Add All

Post by uDebug »

brianfry713,

Thanks for all your thoughts on this thread. It really helped me out a bunch.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

sampad74
New poster
Posts: 29
Joined: Wed Jun 18, 2014 3:57 pm
Location: Bangladesh

Re: 10954 - Add All

Post by sampad74 »

I am getting WA.I tested my output,but did not find any mistake.Please,anybody help me.Thanks in advance.Here is my code...

Code: Select all

got ac
Last edited by sampad74 on Thu Jul 24, 2014 4:45 am, edited 1 time in total.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10954 - Add All

Post by lbv »

sampad74 wrote:I am getting WA.I tested my output,but did not find any mistake.Please,anybody help me.Thanks in advance.Here is my code...
I'd suggest you avoid using the "long" type in C/C++, since it behaves differently in different systems. In 32-bit systems it typically has 4-bytes, and in 64-bit systems it has 8. Consider if a 4-byte integer suffices to hold every possible answer for this problem.

Also, be careful with array overflows/underflows. Consider, for example, what happens when n=2 and this piece of code is executed:

Code: Select all

            for (i = 2; i < n; i++)
                a [i - 2] = a [i];
            i = n - 3;
            while (a [i] > key)   // ....

sampad74
New poster
Posts: 29
Joined: Wed Jun 18, 2014 3:57 pm
Location: Bangladesh

Re: 10954 - Add All

Post by sampad74 »

lbv wrote--
Also, be careful with array overflows/underflows. Consider, for example, what happens when n=2 and this piece of code is executed:

for (i = 2; i < n; i++)
a = a ;
i = n - 3;
while (a > key) // ....

i changed my code..
my code gives me right output for n=2.
I changed long to long long int ,but got WA again.
Last edited by sampad74 on Thu Jul 24, 2014 4:44 am, edited 1 time in total.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10954 - Add All

Post by lbv »

sampad74 wrote:i changed my code.. (..)
but got WA again.
Please post the full, latest version of your code. For people wanting to help you, combining code from different posts to keep track of the changes is not exactly fun :).

sampad74
New poster
Posts: 29
Joined: Wed Jun 18, 2014 3:57 pm
Location: Bangladesh

Re: 10954 - Add All

Post by sampad74 »

sorry...Here is my code.Thanks..

Code: Select all

got ac
Last edited by sampad74 on Thu Jul 24, 2014 4:44 am, edited 1 time in total.

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10954 - Add All

Post by lighted »

You must check your program for input in this thread. It fails on this one
Martin Macko wrote:
Nazmul Quader Zinnuree wrote:OK, Noboby is giving me some I/O that i wanted in another mail.

Now, would you just plz run my code, and say where I'm wrong!!!
Not working for this one:

Code: Select all

8
40952 13521 6223 42589 93489 22376 78730 38792
0
My AC's output:

Code: Select all

899661
Change line

Code: Select all

while (a [i] > key) {
It must be

Code: Select all

while (i > 0  &&  a[i] > key) {
Don't forget to remove your code after getting accepted. 8)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

sampad74
New poster
Posts: 29
Joined: Wed Jun 18, 2014 3:57 pm
Location: Bangladesh

Re: 10954 - Add All

Post by sampad74 »

My code gave right answer for the following test case before changing previous code at my computer :roll: ..i don't know why :o ...
8
40952 13521 6223 42589 93489 22376 78730 38792
0

My AC's output:
899661
Afterall,got AC.Thank you.

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

Re: 10954 - Add All

Post by bgcsaif »

It gives exact output for sample input and some other critical inputs. I don't know why this code gets WA. . . .

Code: Select all

#include <stdio.h>
int main()
{
    long long int n,sum,cost,i,a[99999],j,b;
    while(scanf("%lld",&n)==1&&n!=0)
    {
        for(i=1;i<=n;i++)
            scanf("%lld",&a[i]);

        for(i=1;i<=n-1;i++)
        {
            for(j=1;j<=n-i;j++)
            {
                if(a[j]>a[j+1])
                {
                    b=a[j];
                    a[j]=a[j+1];
                    a[j+1]=b;
                }
            }
        }

        sum=a[1],cost=0;
        for(i=2;i<=n;i++)
        {
            sum=sum+a[i];
            cost=cost+sum;
        }
        if(n==1)
        cost=sum;
        printf("%lld\n",cost);
    }
    return 0;
}

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

Re: 10954 - Add All

Post by brianfry713 »

Input:

Code: Select all

6
9 9 9 9 9 9
0
Correct output 144
Check input and AC output for thousands of problems on uDebug!

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

Re: 10954 - Add All

Post by bgcsaif »

Please help me with sample input analysis:
For the 2nd sample input-

4
1 2 3 4
1+2=3, cost=3
3+3=6, cost=6
6+4=10, cost=10
Total= 19

So, for your input-

6
9 9 9 9 9 9
9 + 9=18, cost=18
18+9=27, cost=27
27+9=36, cost=36
36+9=45, cost=45
45+9=54, cost=54
Total=180

Shouldn't it be like that? How that can be 144?

Post Reply

Return to “Volume 109 (10900-10999)”