497 - Strategic Defense Initiative

[cyfra]

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

[sjn]

Really?
but when i used max=10000 just now, i also got WA again

???????????

[cyfra]

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 e-mail and I will try to help you...

But don't give up..

The mistake must be somewhere here

[Ming Han]

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.

[C8H10N4O2]

That line is fulfill the specifications for the "multiple input".

[SnapDragon]

The problem is the line "if(D[j]<D)". Figure out what you're doing wrong there.

[C8H10N4O2]

Bah, I am so retarded. Fixed it... lol... I forgot to optimize the length. I knew there had to be a "decision statement" some where:) One max and it's all good.

[htl]

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=n-1;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=top-1;y>=0;y--)
printf("%d\n",ans[y]);
}
}
[/c]

[Ivor]

Read the problem description again!

Russian war tactics are fairly strange; their generals are stickers for mathematical precision. Their missles will always be fired in a sequence such that there will only be one solution to the problem posed above.

Ivor

[Ivan Golubev]

AFAIR, there was discussion about multiple possible answers for this problem. My accepted solution outputs '1 4 5 6' for '1 4 3 2 5 6' input.

[htl]

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=n-1;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=top-1;y>=0;y--)
printf("%d\n",ans[y]);
}
}
[/c]

[htl]

After checking my code again and again, I think my original
code is right. But it still gets WA>< Another question: if
the input is '1 3 2 5 4', what should I output?'1 3 5' or
'1 3 4'? Or could you mail me your code and let me read it?

[Ivan Golubev]

'1 3 4' is a correct answer for '1 3 2 5 4'.

I've sent my code to you via private message.

[Caesum]

I managed to get your code working just by some cleaning up and some stricter writing of it - for example you assume that all characters in the input are digits, what about spaces, and other symbols ? You can just rewrite it with sscanf.

[htl]

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