OJ Board

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

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

???????????

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

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.

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

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

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.

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]

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

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.

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]

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?

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

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

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.

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