OJ Board

Kept getting WAs....
It tell us to find out the longest decreasing subsequeue,isn't it??
Can anyone tell me what's the common problem about this question?
following is my code:



#include <stdio.h>
#define MAX 100000

void main()
{
long high[MAX];
long temp=0;
long num=0;
long i,j;
long len[MAX];
long maxlen=0;
long cases=0;
while(1)
{
cases++;
maxlen=0;
num=0;
scanf("%ld",&temp);
if(temp==-1)
break;
high[num]=temp;
num++;
while(1)
{
scanf("%ld",&temp);
if(temp==-1)
break;
high[num]=temp;
num++;
}
for(i=0;i<MAX;i++)
len=0;
len[0]=1;
for(i=0;i<num;i++)
{
for(j=i+1;j<num;j++)
{
if(high[j]<high)
{
if(len[j]<len+1)
len[j]=len+1;
if(maxlen<len[j])
maxlen=len[j];
}
}
}
printf("Test #%ld:n",cases);
if(maxlen==1)
printf(" maximum possible interception: %ldn",maxlen);
else
printf(" maximum possible interceptions: %ldn",maxlen);
printf("n");
}
}

I don't know what made you do this, but even if the maxlen is 1, you have to print the "s".

I fixes it,but I still got WA

The program above gets wrong when I enter such data as " 1 n -1".It print 0,then I fixed it ,but still get WA:

#include <stdio.h>
#define MAX 100000

void main()
{
long high[MAX];
long temp=0;
long num=0;
long i,j;
long len[MAX];
long maxlen=0;
long cases=0;
while(1)
{
cases++;
maxlen=1;
num=0;
scanf("%ld",&temp);
if(temp==-1)
break;
high[num]=temp;
num++;
while(1)
{
scanf("%ld",&temp);
if(temp==-1)
break;
high[num]=temp;
num++;
}
for(i=0;i<MAX;i++)
len=0;
len[0]=1;
for(i=0;i<num;i++)
{
for(j=i+1;j<num;j++)
{
if(high[j]<high)
{
if(len[j]<len+1)
len[j]=len+1;
if(maxlen<len[j])
maxlen=len[j];
}
}
}
printf("Test #%ld:n",cases);
printf(" maximum possible interceptions: %ldn",maxlen);
printf("n");
}
}

I found the problem,just for everybody who has WA with this question:

#include <stdio.h>
#define MAX 100000

void main()
{
long high[MAX];
long temp=0;
long num=0;
long i,j;
long len[MAX];
long maxlen=0;
long cases=0;
while(1)
{
cases++;
maxlen=1;
num=0;
scanf("%ld",&temp);
if(temp==-1)
break;
high[num]=temp;
num++;
while(1)
{
scanf("%ld",&temp);
if(temp==-1)
break;
high[num]=temp;
num++;
}
for(i=0;i<MAX;i++)
len=0;
^^^^^^^^^^
here should be 1!!!


len[0]=1;
for(i=0;i<num;i++)
{
for(j=i+1;j<num;j++)
{
if(high[j]<high)
{
if(len[j]<len+1)
len[j]=len+1;
if(maxlen<len[j])
maxlen=len[j];
}
}
}
printf("Test #%ld:n",cases);
printf(" maximum possible interceptions: %ldn",maxlen);
printf("n");
}
}


<font size=-1>[ This Message was edited by: FlyDeath on 2002-01-04 16:29 ]</font>

could anyone tell me why i got WA??


[c]
#include <stdio.h>

int height[30000];
long int max,intercept;

void count(long int idx, long int itp, int height1, long int maxidx)
{
long int i,limit;

limit=maxidx-idx+itp; /* limit is the max num of missiles that might be intercepted */
if (limit<=max) return; /*so if max already bigger than the limit theres no point of calculating the missiles */

for (i=idx;i<maxidx;i++)
{
if (height<=height1)
{
count(i+1,itp+1,height,maxidx);
}
}
if (itp>max) max=itp;


}



void main(void)
{
long int i,j,k,temp,counter;


#ifndef ONLINE_JUDGE
freopen("231.in","r",stdin);
freopen("231.out","w",stdout);
#endif

counter=1;
do
{

j=0;max=1;
while(scanf("%d",&height[j])==1)
{
if (height[j]==-1) break;

if (height[j]<=height[0]) j++; /* if the height is higher than the first missile, so it would be overriden by the next value*/


}
if (j==0&&height[j]==-1) break;

count(1,1,height[0],j); /*calculate max num of missiles interceptable */


printf("Test #%ld:\n maximum possible interceptions: %ld\n\n",counter,max); /*i think the output format is correct */
counter++;
}
while(1);

}[/c]

my code works on any sample input i could think of....
Does anyone know the tricky input case for this problem??

Here is my input & ouput
25
5
4
3
2
1
0
24
23
22
21
3
2
1


24
24
24
24
24
-1
Test #1:
maximum possible interceptions: 8


233
233
233
-1
Test #2:
maximum possible interceptions: 3

0
-1
Test #3:
maximum possible interceptions: 1


500
-1
Test #4:
maximum possible interceptions: 1

423
312
23
234
234
22
2
32
-1
Test #5:
maximum possible interceptions: 6


423
234
2434
525
23
4343
234
22
312
2
32
-1
Test #6:
maximum possible interceptions: 5


3
432
423
2423
423
423
-1

Test #7:
maximum possible interceptions: 1

3
7324
2352
23
432
432
432
32
324
23
2
22
2
2
-1
Test #8:
maximum possible interceptions: 4


389
207
155
300
299
170
158
65
-1
Test #9:
maximum possible interceptions: 6

23
34
21
-1
Test #10:
maximum possible interceptions: 2

32767
32764
32760
32000
1
-1
Test #11:
maximum possible interceptions: 5

-1

Any help would be appreciated

I don't think that you have to capture the first missile ... You can skip first missile if it will allow you to catch more ...

Or maybe I'm wrong ... ???

-turuthok-

My answers: And turuthok is right, you don't always have to get the first missle..

To Turuthok and Larry, thank you for pointing out my mistakes and your hints. I'll tell you if i got accepted on this one

Again, thank you all

I've made some changes in my code so that it would do what Larry and turuthok told me. And i got accepted.
Once again, thx!! I couldn't have done it without your help

Why WA ?

This is my source


program n231;
type
tpair = array[1..2] of integer;
var heights : array[1..3000000] of tpair;
i,j : integer;
n : integer;
temp : integer;
max,testnr : integer;
begin
testnr := 1;
{assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);}
temp := 0;

fillchar(heights,sizeof(heights),0);
read(temp);
while temp <> -1 do
begin
i := 0;
fillchar(heights,sizeof(heights),0);
while temp <> -1 do
begin
inc(i);
heights[i,1] := temp;
heights[i,2] := 1;
readln(temp);
end;
n := i;
heights[n,2] := 1;
for i := n-1 downto 1 do
begin
max := -1;
for j := I + 1 to n do
begin
if (heights[j,1] < heights[i,1]) and (heights[j,2]>max)then
max := heights[j,2];
end;
heights[i,2] := max;
end;
max := 0;
for i:= 1 to n do if heights[i,2] > max then max := heights[i,2];
writeln('Test #',testnr,':');
inc(testnr);
writeln(' maximum possible interceptions: ',max);
read(temp);
end;





end.

I think you are supposed to read from stdin and stdout instead of files...

another thing... put the pascal tag before and after your code... it's been a long time since I've used Pascal and the removal of white space makes it near complete gibberish. :p

i made some changes
read -> readln
and
heights[i,2] := max -> heights[i,2] := heights[i,2] + max
and got accepted

I have got WA on problem 231(Testing the CATCHER). I have test my code with possible input set and got ok. Here is my code. Please help me.



#include<stdio.h>

long height[1000],length[1000];

int main()
{
long input,total,count,tcase;
long i,j;

tcase=1;
while(1)
{
count=0;
total=0;
scanf("%d",&input);

if(input<0)
break;
do
{
height[total++]=input;
scanf("%d",&input);
}while(input>=0);


for (i = 1;i<=total-1;i++)
for (j = i+1;j<=total;j++)
{
if (height[j] > height)
{
if (length + 1 > length[j])
length[j] = length + 1;
count++;
}
}

printf("Test #%d: ",tcase++);
printf(" \nmaximum possible interceptions: %d\n\n",count);
}

return 0;
}