Page 1 of 6

10954 - Add All

Posted: Sun Oct 30, 2005 12:55 am
by Deno
I absolutely no idea why I am getting a WA.
I got WA even after changing uint to double, sorting the numbers...

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	typedef unsigned int uint;
	int N;
	while(cin>>N && N!=0) {
		vector<uint> table(N);
		for (N--;N!=-1;--N)
			cin>>table[N];
		sort(table.begin(), table.end());
		uint total=table[0]*(table.size()-1);
		for (vector<uint>::size_type z=1; z<table.size(); z++) {
			total+=table[z]*(table.size()-z);
		}
		cout<<total<<endl;
	}
}

Posted: Sun Oct 30, 2005 1:08 am
by mf
Try this test case

5
2 2 2 2 3

Posted: Sun Oct 30, 2005 2:41 am
by Deno
My program outputs 29 for that test case.

2+2=4
4+2=6
6+2=8
8+3=11

4+6+8+11=29

Posted: Sun Oct 30, 2005 2:46 am
by tywok
It should be

2 + 2 = 4
2 + 2 = 4
3 + 4 = 7
4 + 7 = 11

So, it is 4 + 4 + 7 + 11 = 26 :wink:

Posted: Sun Oct 30, 2005 3:13 am
by Deno
OH........why was I that stupid...>.<||

Thank you sooooo much~~
I got AC now!! :)

Oh my god...

Posted: Sun Oct 30, 2005 4:05 am
by valfiros
Oh my god...I did absolutely same mistake...
(and got WA over 20 time, about 4 hours, saying "what the @%^"...)
thx alotttt!

-JSKim-

Posted: Sun Oct 30, 2005 4:22 am
by Bj
You can solve this problem in very few lines with a min priority queue.

thx

Posted: Sun Oct 30, 2005 5:15 am
by valfiros
yup, in first time, i used quick sort & insertion sort, but TLE...

and i used priority_queue (stl) and got AC.

THX alot!!

-JSKim/valfiros-

Posted: Sun Oct 30, 2005 5:28 am
by jan_holmes
why :
5
2 2 2 2 3

the output :
2+2 = 4
2+2 = 4
4+3 = 7
7+4 = 11

4+4+7+11 = 26

why ??? could anyone explain it?? Thx...

Posted: Sun Oct 30, 2005 6:03 am
by shamim
Another way of staing the problem is ,
add two numbers from the list, add the result to the cumulative cost, remove the two numbers from the list and insert the sum to the list.
The answer will be the minimum cumulative value obtainable.

so,
2 2 2 2 3 -> (2+2=4)
4 2 2 3 -> (2+2=4)
4 4 3 ->(4+3=7)
7 4->(7+4=11)
11

and
4 +4 + 7 + 11 = 26. :wink:

Posted: Sun Oct 30, 2005 6:13 am
by SRX
shamim wrote:Another way of staing the problem is ,
add two numbers from the list, add the result to the cumulative cost, remove the two numbers from the list and insert the sum to the list.
The answer will be the minimum cumulative value obtainable.

so,
2 2 2 2 3 -> (2+2=4)
4 2 2 3 -> (2+2=4)
4 4 3 ->(4+3=7)
7 4->(7+4=11)
11

and
4 +4 + 7 + 11 = 26. :wink:
Is this problem like huffman :oops:
I use like insert and got ac 3.xxx seconds
What method can run faster ?

Posted: Sun Oct 30, 2005 6:52 am
by Deno
I used a priority queue (implemented by heap) and the program runs 0.2s

Posted: Sun Oct 30, 2005 12:58 pm
by tywok
Also you can use multiset :wink:

Posted: Sun Oct 30, 2005 1:14 pm
by SRX
tywok wrote:Also you can use multiset :wink:
thank you :)
I need to learn more stl

Posted: Mon Oct 31, 2005 3:02 am
by Tamagodzi
an array is enough :-)

first solver under 0.1 s with scanf ^^