497  Strategic Defense Initiative
Moderator: Board moderators
Found Your Mistake ..
Hi!
I think I have found your mistake...
Look you have:
[pascal]
const
max=100;
[/pascal]
But when I have send my own program (It got AC) I had max=8000...
When I have changed in your source code max value to 8000 it had Time Limit Exceeded
I thing you should use better algoritms otherwise you will still have Time Limit..
You can do this using Dynamic Programming...
I hope This will Help..
Good Luck
I think I have found your mistake...
Look you have:
[pascal]
const
max=100;
[/pascal]
But when I have send my own program (It got AC) I had max=8000...
When I have changed in your source code max value to 8000 it had Time Limit Exceeded
I thing you should use better algoritms otherwise you will still have Time Limit..
You can do this using Dynamic Programming...
I hope This will Help..
Good Luck
Hmm....
That's strange....
I couldn't find your mistake...
But I will be searching ...
Meanwhile maybe you will try to write this program again (I it always work
My procedure which solves this task has 5 lines...
Try to use normal dynamic programming with one table...
If you don't know how to do this write me an email and I will try to help you...
But don't give up..
The mistake must be somewhere here
That's strange....
I couldn't find your mistake...
But I will be searching ...
Meanwhile maybe you will try to write this program again (I it always work
My procedure which solves this task has 5 lines...
Try to use normal dynamic programming with one table...
If you don't know how to do this write me an email and I will try to help you...
But don't give up..
The mistake must be somewhere here
I think I know yuor mistake
This should not be there: [cpp] scanf("%dnn",&Z); [/cpp]
The question says that input to your program will consist of a sequence of integer altitudes, each on a separate line.
There is no value to specify the number of lines.
The question says that input to your program will consist of a sequence of integer altitudes, each on a separate line.
There is no value to specify the number of lines.

 Problemsetter
 Posts: 22
 Joined: Tue Jun 11, 2002 12:35 am
Found it
The problem is the line "if(D[j]<D)". Figure out what you're doing wrong there.
497
Why does this code get WA? Is there only one solution to every input set?
If the input is '1 4 3 2 5 6',what should I output?'1 4 5 6' or '1 3 5 6' or '1 2 5 6'?
[c]
#include<stdio.h>
#include<string.h>
void main(void)
{
int data[10000],lis[10000],pos[10000],count,x,y,t,n,max,z,ans[10000],top;
char s[10],c;
scanf("%d\n",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
for(n=0;fgets(s,10,stdin)!=NULL;)
{
s[strlen(s)1]='\0';
if(!strlen(s))
break;
for(y=0,t=0;s[y]!='\0';y++)
t=t*10+s[y]'0';
data[n++]=t;
}
for(y=0;y<n;y++)
lis[y]=1,pos[y]=1;
max=1;
for(y=0;y<n;y++)
{
for(z=0;z<y;z++)
if(data[z]<data[y] && lis[z]+1>lis[y])
lis[y]=lis[z]+1,pos[y]=z;
if(lis[y]>max)
max=lis[y];
}
for(y=n1;y>=0;y)
if(lis[y]==max)
break;
top=0;
while(1)
{
ans[top++]=data[y];
t=pos[y];
if(t==1)
break;
y=t;
}
printf("Max hits: %d\n",max);
for(y=top1;y>=0;y)
printf("%d\n",ans[y]);
}
}
[/c]
If the input is '1 4 3 2 5 6',what should I output?'1 4 5 6' or '1 3 5 6' or '1 2 5 6'?
[c]
#include<stdio.h>
#include<string.h>
void main(void)
{
int data[10000],lis[10000],pos[10000],count,x,y,t,n,max,z,ans[10000],top;
char s[10],c;
scanf("%d\n",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
for(n=0;fgets(s,10,stdin)!=NULL;)
{
s[strlen(s)1]='\0';
if(!strlen(s))
break;
for(y=0,t=0;s[y]!='\0';y++)
t=t*10+s[y]'0';
data[n++]=t;
}
for(y=0;y<n;y++)
lis[y]=1,pos[y]=1;
max=1;
for(y=0;y<n;y++)
{
for(z=0;z<y;z++)
if(data[z]<data[y] && lis[z]+1>lis[y])
lis[y]=lis[z]+1,pos[y]=z;
if(lis[y]>max)
max=lis[y];
}
for(y=n1;y>=0;y)
if(lis[y]==max)
break;
top=0;
while(1)
{
ans[top++]=data[y];
t=pos[y];
if(t==1)
break;
y=t;
}
printf("Max hits: %d\n",max);
for(y=top1;y>=0;y)
printf("%d\n",ans[y]);
}
}
[/c]

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
I modified my code and if the input is '1 4 3 2 5 6' it will output '1 4 5 6'. But it still get WA.
[c]
#include<stdio.h>
#include<string.h>
void main(void)
{
int data[10000],lis[10000],pos[10000],count,x,y,t,n,max,z,ans[10000],top;
char s[10],c;
scanf("%d\n",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
for(n=0;fgets(s,10,stdin)!=NULL;)
{
s[strlen(s)1]='\0';
if(!strlen(s))
break;
for(y=0,t=0;s[y]!='\0';y++)
t=t*10+s[y]'0';
data[n++]=t;
}
for(y=0;y<n;y++)
lis[y]=1,pos[y]=1;
max=1;
for(y=0;y<n;y++)
{
for(z=0;z<y;z++)
if(data[z]<data[y])
{
if(lis[z]+1>lis[y])
lis[y]=lis[z]+1,pos[y]=z;
else if(lis[z]+1==lis[y] && data[z]>data[pos[y]])
pos[y]=z;
}
if(lis[y]>max)
max=lis[y];
}
for(y=n1;y>=0;y)
if(lis[y]==max)
break;
top=0;
while(1)
{
ans[top++]=data[y];
t=pos[y];
if(t==1)
break;
y=t;
}
printf("Max hits: %d\n",max);
for(y=top1;y>=0;y)
printf("%d\n",ans[y]);
}
}
[/c]
[c]
#include<stdio.h>
#include<string.h>
void main(void)
{
int data[10000],lis[10000],pos[10000],count,x,y,t,n,max,z,ans[10000],top;
char s[10],c;
scanf("%d\n",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
for(n=0;fgets(s,10,stdin)!=NULL;)
{
s[strlen(s)1]='\0';
if(!strlen(s))
break;
for(y=0,t=0;s[y]!='\0';y++)
t=t*10+s[y]'0';
data[n++]=t;
}
for(y=0;y<n;y++)
lis[y]=1,pos[y]=1;
max=1;
for(y=0;y<n;y++)
{
for(z=0;z<y;z++)
if(data[z]<data[y])
{
if(lis[z]+1>lis[y])
lis[y]=lis[z]+1,pos[y]=z;
else if(lis[z]+1==lis[y] && data[z]>data[pos[y]])
pos[y]=z;
}
if(lis[y]>max)
max=lis[y];
}
for(y=n1;y>=0;y)
if(lis[y]==max)
break;
top=0;
while(1)
{
ans[top++]=data[y];
t=pos[y];
if(t==1)
break;
y=t;
}
printf("Max hits: %d\n",max);
for(y=top1;y>=0;y)
printf("%d\n",ans[y]);
}
}
[/c]

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
I think data reading is the problem.
The original code:
[c]
for(y=0,t=0;s[y]!='\0';y++)
t=t*10+s[y]'0';
[/c]
got WA.
But when I replaced it with below
[c]
for(y=0,t=0;s[y]!='\0';y++)
if(s[y]>='0' && s[y]<='9')
t=t*10+s[y]'0';
[/c]
or
[c]
t=atoi(s);/*I have included stdlib.h*/
[/c]
got RE.
I skip any characters except the digits and got RE instead.
Do you have any suggestion on this?ex. reading by sscanf
The original code:
[c]
for(y=0,t=0;s[y]!='\0';y++)
t=t*10+s[y]'0';
[/c]
got WA.
But when I replaced it with below
[c]
for(y=0,t=0;s[y]!='\0';y++)
if(s[y]>='0' && s[y]<='9')
t=t*10+s[y]'0';
[/c]
or
[c]
t=atoi(s);/*I have included stdlib.h*/
[/c]
got RE.
I skip any characters except the digits and got RE instead.
Do you have any suggestion on this?ex. reading by sscanf