231 - Testing the CATCHER

[FlyDeath]

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");
}
}

[junjieliang]

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

[FlyDeath]

I fixes it,but I still got WA

[FlyDeath]

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");
}
}

[FlyDeath]

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>

[Nick]

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

[turuthok]

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-

[Larry]

My answers:

Code: Select all

Test #1:
  maximum possible interceptions: 8

Test #2:
  maximum possible interceptions: 3

Test #3:
  maximum possible interceptions: 1

Test #4:
  maximum possible interceptions: 1

Test #5:
  maximum possible interceptions: 6

Test #6:
  maximum possible interceptions: 5

Test #7:
  maximum possible interceptions: 4

Test #8:
  maximum possible interceptions: 10

Test #9:
  maximum possible interceptions: 6

Test #10:
  maximum possible interceptions: 2

Test #11:
  maximum possible interceptions: 5

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

[Nick]

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

[Nick]

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

[fofo2002ss]

fofo2002ss@hotmail.com

[LeoST]

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.

[junbin]

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

[LeoST]

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

[Yen]

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;
}