10954 - Add All
Moderator: Board moderators
to valfiros
there exist priority queue implemented in STL ???
thanks Emilio
thanks for ur reply.
but one more isssue: implementing it using heap has no more advantage than this one, in speed or whatever ??
but one more isssue: implementing it using heap has no more advantage than this one, in speed or whatever ??
-
- Guru
- Posts: 647
- Joined: Wed Jun 26, 2002 10:12 pm
- Location: Hong Kong and New York City
- Contact:
Are there any trick cases? I also used a heap implementation.. ![:-?](./images/smilies/icon_confused.gif)
![:-?](./images/smilies/icon_confused.gif)
Check out http://www.algorithmist.com !
10954 - Add All
I don't know why I got WA...
help me...please.....
help me...please.....
Code: Select all
#include<stdio.h>
int n,all,que[5002];
int add(int in)
{
int index;
index=all;
all++;
while(index>0)
{
if(in<que[(index-1)/2])
{
que[index]=que[(index-1)/2];
index=(index-1)/2;
}
else
break;
}
que[index]=in;
return 0;
}
int del()
{
int index=0;
all--;
while(index<=(all-2)/2)
{
if(que[all]>que[index*2+1])
{
que[index]=que[index*2+1];
index=index*2+1;
}
else if(index*2+3<=all && que[all]>que[index*2+2])
{
que[index]=que[index*2+2];
index=index*2+2;
}
else
break;
}
que[index]=que[all];
return 0;
}
int main()
{
int k,i,out;
while(scanf("%d",&n)==1 && n!=0)
{
all=out=0;
for(i=0;i<n;i++)
{
scanf("%d",&k);
add(k);
}
while(all>1)
{
k=que[0];
del();
k+=que[0];
del();
add(k);
out+=k;
}
printf("%d\n",out);
}
return 0;
}
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Re: 10954 WA
Try this input:
My AC's output is:
Code: Select all
14
1 8 2 4 7 89 5 8 74 2 6 8 5 47
0
Code: Select all
717
-
- New poster
- Posts: 42
- Joined: Sun Jul 31, 2005 2:07 am
- Location: SUST. Bangladesh
- Contact:
I'm getting WA using priority queue (and long long data type)
My Input:
My Output:
These are right, I think. Somebody, give me some more I/O, plz...
Thanks...
My Input:
Code: Select all
5
2 2 2 2 3
5
1 1 1 1 1
14
1 8 2 4 7 89 5 8 74 2 6 8 5 47
4
1 2 3 4
5
1 2 3 4 5
2
1 1
0
Code: Select all
26
12
717
19
33
2
Thanks...
-
- New poster
- Posts: 42
- Joined: Sun Jul 31, 2005 2:07 am
- Location: SUST. Bangladesh
- Contact:
OK, Noboby is giving me some I/O that i wanted in another mail.
Now, would you just plz run my code, and say where I'm wrong!!!
Btw, I did not want to send my code. But, no way....
It matches the above test case and many other that I imagine.
Now, would you just plz run my code, and say where I'm wrong!!!
Btw, I did not want to send my code. But, no way....
Code: Select all
Code removed after AC
Last edited by Nazmul Quader Zinnuree on Sun Aug 27, 2006 1:36 am, edited 1 time in total.
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Not working for this one:Nazmul Quader Zinnuree wrote:OK, Noboby is giving me some I/O that i wanted in another mail.
Now, would you just plz run my code, and say where I'm wrong!!!
Code: Select all
8
40952 13521 6223 42589 93489 22376 78730 38792
0
Code: Select all
899661
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Yes, this output is correct... In the other thread (where you've posted your code) I've just posted a case your code doesn't work on.Nazmul Quader Zinnuree wrote:My Output:Code: Select all
26 12 717 19 33 2
-
- New poster
- Posts: 42
- Joined: Sun Jul 31, 2005 2:07 am
- Location: SUST. Bangladesh
- Contact:
Re: 10954 - Add All
I couldn't find out what's wrong in my code
I test all the data above and the answer was correct
but when I submit on UVa I got WA
could anyone can help me please... thank you very much~
I test all the data above and the answer was correct
but when I submit on UVa I got WA
could anyone can help me please... thank you very much~
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void createheap(int[],int num);
void heapsort(int[],int num);
void addheap(int number[],int addnum,int num);
int main(void) {
int number[5000+1],ans[5000+1]={0};
int i,num,m,count[3],k,answer=0;
scanf("%d",&num);
while(num!=0){
for(i=1;i<=num;i++){
scanf("%d",&number[i]);
}
createheap(number,num);
m=num;
k=1;
while(m>1){
SWAP(number[1], number[m]);
count[0]=number[m];
m--;
heapsort(number,m);
SWAP(number[1], number[m]);
count[1]=number[m];
m--;
heapsort(number,m);
count[2]=count[0]+count[1];
ans[k]=count[2];
k++;
m++;
addheap(number,count[2],m);
}
i=1;
while(ans[i]!=0){
answer+=ans[i];
i++;
}
printf("%d\n", answer);
answer=0;
scanf("%d",&num);
}
return 0;
}
void createheap(int number[],int num) {
int i, s, p;
int heap[5000+1] = {0};
for(i = 1; i <= num; i++) {
heap[i] = number[i];
s = i;
p = i / 2;
while(s >= 2 && heap[p] > heap[s]) {
SWAP(heap[p], heap[s]);
s = p;
p = s / 2;
}
}
for(i = 1; i <= num; i++)
number[i] = heap[i];
}
void addheap(int number[],int addnum,int num) {
int s, p;
number[num]=addnum;
s = num;
p = num / 2;
while(s >= 2 && number[p] > number[s]) {
SWAP(number[p], number[s]);
s = p;
p = s / 2;
}
}
void heapsort(int number[],int num) {
int p, s;
p = 1;
s = 2 * p;
while(s <= num) {
if(s < num && number[s+1] < number[s])
s++;
if(number[p] <= number[s])
break;
SWAP(number[p], number[s]);
p = s;
s = 2 * p;
}
}