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

taha
New poster
Posts: 12
Joined: Mon Oct 31, 2005 10:17 am
Location: Egypt

to valfiros

Post by taha » Mon Oct 31, 2005 1:20 pm

there exist priority queue implemented in STL ???

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Mon Oct 31, 2005 1:46 pm


taha
New poster
Posts: 12
Joined: Mon Oct 31, 2005 10:17 am
Location: Egypt

thanks Emilio

Post by taha » Mon Oct 31, 2005 2:09 pm

thanks for ur reply.
but one more isssue: implementing it using heap has no more advantage than this one, in speed or whatever ??

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Mon Oct 31, 2005 4:34 pm

The STL priority_queue is implemented as a heap in a vector<T>.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Nov 03, 2005 8:13 pm

Are there any trick cases? I also used a heap implementation.. :-?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Nov 03, 2005 8:15 pm

Nevermind, I missed the N=0 for ending.. I'm an idiot. :lol:

Jeff
New poster
Posts: 7
Joined: Mon May 02, 2005 5:39 pm

10954 - Add All

Post by Jeff » Mon Dec 12, 2005 7:12 am

I don't know why I got WA...
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;
}

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10954 WA

Post by Martin Macko » Mon Dec 12, 2005 2:19 pm

Try this input:

Code: Select all

14
1 8 2 4 7 89 5 8 74 2 6 8 5 47
0
My AC's output is:

Code: Select all

717

Jeff
New poster
Posts: 7
Joined: Mon May 02, 2005 5:39 pm

Post by Jeff » Mon Dec 12, 2005 3:15 pm

Thanks~
I got AC... :D

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by Nazmul Quader Zinnuree » Thu Aug 24, 2006 8:07 am

I'm getting WA using priority queue (and long long data type)

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
My Output:

Code: Select all

26
12
717
19
33
2
These are right, I think. Somebody, give me some more I/O, plz...
Thanks...

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by Nazmul Quader Zinnuree » Sat Aug 26, 2006 8:20 pm

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

Code: Select all

Code removed after AC
It matches the above test case and many other that I imagine.
Last edited by Nazmul Quader Zinnuree on Sun Aug 27, 2006 1:36 am, edited 1 time in total.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Aug 26, 2006 9:31 pm

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!!!
Not working for this one:

Code: Select all

8
40952 13521 6223 42589 93489 22376 78730 38792
0
My AC's output:

Code: Select all

899661

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Aug 26, 2006 10:27 pm

Nazmul Quader Zinnuree wrote:My Output:

Code: Select all

26
12
717
19
33
2
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
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by Nazmul Quader Zinnuree » Sun Aug 27, 2006 1:35 am

The bug was in my extract_min() function. AC now.
Thanks to Martin Macko

tom76925
New poster
Posts: 2
Joined: Tue Aug 12, 2008 3:56 am

Re: 10954 - Add All

Post by tom76925 » Tue Aug 12, 2008 4:05 am

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~

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

Post Reply

Return to “Volume 109 (10900-10999)”