10930 - A-Sequence
Moderator: Board moderators
-
- New poster
- Posts: 19
- Joined: Wed Jan 11, 2006 9:57 am
- Location: Dhaka
Waaaaaaa
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
}
........................................................................................................
#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.
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)
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.
-
- New poster
- Posts: 19
- Joined: Wed Jan 11, 2006 9:57 am
- Location: Dhaka
I can't understand
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.
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.
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.
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.
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Re: Waaaaaaa
You don't reinitialize the array a[]:Shuvra(CSE-BUET) wrote:My code gives nasty WA.... Help me pls.(Posting code is bad I know)
Shuvra(CSE-BUET) wrote:
- for(i=0;i<=1000;i++)
- a[0]=0; <-- I think you should change it to a[i]=0
the order matters of course
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.
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.
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;
}
Re: help
My accepted code returns.rezaeeEE wrote:what is the output for this input:
2 2 2 ?
Output:
Code: Select all
Case #1: 2 2
This is not an A-sequence.
Ami ekhono shopno dekhi...
HomePage
HomePage
Try this case:
----
Rio
Code: Select all
5 10 14 18 20 50
Rio
-
- New poster
- Posts: 4
- Joined: Thu Nov 24, 2005 5:47 am
- Location: Bangladesh
- Contact:
I have got WA several times,but could not find the error.Plz someone help me....
Thnx in advance.
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;
}
}
Keep dreaming.It costs nothing but makes you living