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
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
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!!
valfiros
New poster
Posts: 5 Joined: Wed May 25, 2005 3:31 pm
Location: south korea
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.
valfiros
New poster
Posts: 5 Joined: Wed May 25, 2005 3:31 pm
Location: south korea
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...
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.
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.
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
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
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
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 ^^