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 »

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 »

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 »

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 »

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 »

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

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

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

Oh my god...

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

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

Post by Bj »

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

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

thx

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

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

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

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

Post 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:

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

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

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

Post by Deno »

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 »

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 »

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 »

an array is enough :-)

first solver under 0.1 s with scanf ^^

Post Reply

Return to “Volume 109 (10900-10999)”