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

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 am

10954 - Add All

Post by Deno » Sun Oct 30, 2005 12:55 am

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;
	}
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Oct 30, 2005 1:08 am

Try this test case

5
2 2 2 2 3

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 am

Post by Deno » Sun Oct 30, 2005 2:41 am

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

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Sun Oct 30, 2005 2:46 am

It should be

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

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

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 am

Post by Deno » Sun Oct 30, 2005 3:13 am

OH........why was I that stupid...>.<||

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

User avatar
valfiros
New poster
Posts: 5
Joined: Wed May 25, 2005 3:31 pm
Location: south korea

Oh my god...

Post by valfiros » Sun Oct 30, 2005 4:05 am

Oh my god...I did absolutely same mistake...
(and got WA over 20 time, about 4 hours, saying "what the @%^"...)
thx alotttt!

-JSKim-
Onesama daisuki!

Bj
New poster
Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden

Post by Bj » Sun Oct 30, 2005 4:22 am

You can solve this problem in very few lines with a min priority queue.

User avatar
valfiros
New poster
Posts: 5
Joined: Wed May 25, 2005 3:31 pm
Location: south korea

thx

Post by valfiros » Sun Oct 30, 2005 5:15 am

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-
Onesama daisuki!

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sun Oct 30, 2005 5:28 am

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...

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Oct 30, 2005 6:03 am

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:

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Sun Oct 30, 2005 6:13 am

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 ?
studying @ ntu csie

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 am

Post by Deno » Sun Oct 30, 2005 6:52 am

I used a priority queue (implemented by heap) and the program runs 0.2s

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Sun Oct 30, 2005 12:58 pm

Also you can use multiset :wink:
Impossible is nothing

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Sun Oct 30, 2005 1:14 pm

tywok wrote:Also you can use multiset :wink:
thank you :)
I need to learn more stl
studying @ ntu csie

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

Post by Tamagodzi » Mon Oct 31, 2005 3:02 am

an array is enough :-)

first solver under 0.1 s with scanf ^^

Post Reply

Return to “Volume 109 (10900-10999)”