Moderator: Board moderators

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 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*(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:
Try this test case

5
2 2 2 2 3

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 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
It should be

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

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

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 am
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...

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

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:
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
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. SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan
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. Is this problem like huffman 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
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
Also you can use multiset Impossible is nothing

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan
tywok wrote:Also you can use multiset thank you an array is enough 