10930 - A-Sequence

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

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Wed Aug 30, 2006 10:34 am

Thnx .
I got accepted.
Actually I was a little bit confused by some of the posts in the other threads
Thank u once again.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

Waaaaaaa

Post by Shuvra(CSE-BUET) » Thu Aug 31, 2006 2:10 pm

My code gives nasty WA.... Help me pls.(Posting code is bad I know)
........................................................................................................

#include <stdio.h>
bool a[1020];
long p[1200];
void main(){
long cas=1,i,j,x,prev;
int flag;
while(scanf("%ld",&x)==1){
prev=0;
flag=1;
for(i=0;i<=1000;i++)
a[0]=0;
for(i=0;i<x;i++)
{

scanf("%ld",&p);
if(p<=prev)
flag=0;
prev=p;

}
if(flag==0)
{
printf("Case #%ld:",cas);
cas++;
for(i=0;i<x;i++)
printf(" %ld",p);
printf("\nThis is not an A-sequence.\n");
continue;
}
//by dp I calculate all the sums
for(j=0;j<x && flag;j++){
for(i=1000;i>=1 && flag;i--)
{
if(i==p[j] && a==1)
{
flag=0;
break;
}
else if(i==p[j] && a==0)
a=1;
else if(i!=p[j] && a==1)
{
if(i + p[j] <=1000)
a[i+p[j]]=1;

}

}
}//for
if(flag==1)
{
printf("Case #%ld:",cas);
cas++;
for(i=0;i<x;i++)
printf(" %ld",p);
printf("\nThis is an A-sequence.\n");
continue;

}
else{
printf("Case #%ld:",cas);
cas++;
for(i=0;i<x;i++)
printf(" %ld",p);
printf("\nThis is not an A-sequence.\n");
continue;
}



}//while
}
Life is a challenge.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Aug 31, 2006 4:48 pm

try
4 200 500 600 900

This is not an A-sequence, 200 + 900 = 500 + 600. Why did you limit to 1000? And shouldn't main() return int?

(Above is obviously wrong, but I'll leave it there, so the response below makes sense)
Last edited by Darko on Fri Sep 01, 2006 7:54 am, edited 1 time in total.

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

I can't understand

Post by Shuvra(CSE-BUET) » Fri Sep 01, 2006 7:38 am

Hi, I don't understand what u say. You say that
200 500 600 900 is not an A sequence, as 200 + 900 = 500 + 600.
But from prob 'For this problem an A-sequence is a sequence of positive integers ai satisfying 1 ≤ a1 < a2 < a3 < ... and every ak of the sequence is not the sum of two or more distinct earlier terms of the sequence. '
So why did you say that ?

2nd thing is that bool size 1000 is enough as the prob says -'each integer is greater than or equal to 1 and less than or equal to 1000.'

And the 3rd thing is that is it wrong if I write void main()? Actually as you write always int main() ,.....return 0, you may think all other things are wrong or may not like other things.

I can't get ac even now. Pls help me after examining my code in the previous page.
Life is a challenge.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Sep 01, 2006 7:53 am

Sorry about that case, I got some problems mixed up - yes, you are right.
And my solution does have sums[30000] in it (no idea why I put it there). I didn't mean to mislead you on purpose, sorry again.

About the int main() - it's not what I'm used to or whatever (I submit Java code), but my C++ compiler complained about it. If void works, return void.

As I mentioned before - I got AC after recoding this seamingly easy problem from scratch 4-5 times. Maybe it will work for you, too.

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

Re: Waaaaaaa

Post by Martin Macko » Fri Sep 01, 2006 1:14 pm

Shuvra(CSE-BUET) wrote:My code gives nasty WA.... Help me pls.(Posting code is bad I know)
You don't reinitialize the array a[]:
Shuvra(CSE-BUET) wrote:
  • for(i=0;i<=1000;i++)
    • a[0]=0;            <-- I think you should change it to a[i]=0

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

the order matters of course

Post by Sedefcho » Wed Jan 03, 2007 3:42 pm

The order matters in my opinion. I am pretty sure actually.

The problem is not talking about sets but about
sequences. So any interpretations that we should
rearrange or sort the sequence before even starting
to process it are wrong.

At least this is my opinion and this is what the
common math sense says.
The definition given here also confirms that:
http://mathworld.wolfram.com/A-Sequence.html

Good luck to everyone.

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

Post by abhiramn » Sat Aug 04, 2007 1:20 pm

Code: Select all

#include<stdio.h>
#include<iostream>
using namespace std;
bool flags[30001];
int main()
{
	int a[30],i,j,k,count=0,n,max,prev;
	bool flag;
	char ans[2][30]={"\nThis is not an A-sequence.\n","\nThis is an A-sequence.\n"};
	for(i=0;i<30001;flags[i]=0,++i);
	while(scanf("%d",&n)==1)
	{
		printf("Case #%d:",++count);
		scanf("%d%d",&a[0],&a[1]);
		printf(" %d %d",a[0],a[1]);
		if(a[0]>0&&a[1]>a[0])
			flag=1;
		else
			flag=0;
		flags[a[0]+a[1]]=1;
		max=a[0]+a[1];
		prev=a[1];
		for(i=2;i<n;++i)
		{
			scanf("%d",&a[i]);
			printf(" %d",a[i]);
			if(flag)
			{
				if(prev>=a[i])
					flag=0;
				prev=a[i];
				for(j=0;j<=max;++j)
					if(flags[j])
						flags[j+a[i]]=1;
				for(j=0;j<i;flags[a[j]+a[i]]=1,++j);
				if(flags[a[i]])
					flag=0;
			}
			max+=a[i];
		}
		printf(ans[flag]);
		for(i=0;i<=max;flags[i]=0,++i);
	}
	return 0;
}
I don't know what is wrong with this code. I have not sorted the input sequence. Please help me.

rezaeeEE
New poster
Posts: 25
Joined: Fri May 11, 2007 3:45 pm

help

Post by rezaeeEE » Thu Aug 30, 2007 6:31 pm

i get wa with sorting and without sorting.
can any body help me?

Code: Select all

Removed after AC
Last edited by rezaeeEE on Fri Aug 31, 2007 2:33 pm, edited 1 time in total.

rezaeeEE
New poster
Posts: 25
Joined: Fri May 11, 2007 3:45 pm

help

Post by rezaeeEE » Thu Aug 30, 2007 7:09 pm

what is the output for this input:
2 2 2 ?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: help

Post by Jan » Thu Aug 30, 2007 10:02 pm

rezaeeEE wrote:what is the output for this input:
2 2 2 ?
My accepted code returns.

Output:

Code: Select all

Case #1: 2 2
This is not an A-sequence.
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

rezaeeEE
New poster
Posts: 25
Joined: Fri May 11, 2007 3:45 pm

help

Post by rezaeeEE » Fri Aug 31, 2007 12:22 pm

my code returns this.

can u find any bug in my code?
please explain your algo.
my code returns a correct output for all the test cases .
should i sort the input?
my algo is wrong?
thanks.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Aug 31, 2007 12:39 pm

Try this case:

Code: Select all

5 10 14 18 20 50
----
Rio

rezaeeEE
New poster
Posts: 25
Joined: Fri May 11, 2007 3:45 pm

help

Post by rezaeeEE » Fri Aug 31, 2007 2:30 pm

thank u very much for your tricky test case.

i find my bug and got AC.

thank u.

Sohel_Cuet
New poster
Posts: 4
Joined: Thu Nov 24, 2005 5:47 am
Location: Bangladesh
Contact:

Post by Sohel_Cuet » Tue Sep 04, 2007 12:08 am

I have got WA several times,but could not find the error.Plz someone help me....

Code: Select all

#include<stdio.h>
#define M 60000

typedef long dt;
dt as[M],sa[M],tuk[M];

void main()
{
	dt cas=0,n,num,i,j,m,l,assa,sum,pre;

	while(scanf("%ld",&n)==1)
	{
		cas++;
		printf("Case #%ld:",cas);
		j=0;
		assa=0;
		m=0;
		scanf("%ld",&tuk[1]);
		printf(" %ld",tuk[1]);
		pre=tuk[1];
		for(i=2;i<=n;i++)
		{
			scanf("%ld",&num);
			printf(" %ld",num);
			if(pre>=num)
			sa[num]=1;
			if(sa[num]==1)
			{
				i++;
				assa=1;
				for(;i<=n;i++)
				{
					scanf("%ld",&num);
					printf(" %ld",num);
				}
				break;
			}
			l=j;
			for(;l>0;l--)
			{
				sum=as[l]+num;
				if(sa[sum]==0)
				{
					j++;
					as[j]=sum;
					sa[sum]=1;
				}
				else
				m++;
			}
			for(l=1;l<i;l++)
			{
				sum=tuk[l]+num;
				if(sa[sum]==0)
				{
					j++;
					as[j]=sum;
					sa[sum]=1;
				}
				else
				m++;
			}
			tuk[i]=num;
			pre=num;
		}
		if(assa==1)
			printf("\nThis is not an A-sequence.\n");
		else
			printf("\nThis is an A-sequence.\n");
		for(i=1;i<=j;i++)
			sa[as[i]]=0;
	}

}
Thnx in advance.
Keep dreaming.It costs nothing but makes you living

Post Reply

Return to “Volume 109 (10900-10999)”