## 231 - Testing the CATCHER

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
I don't know what made you do this, but even if the maxlen is 1, you have to print the "s".

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
I fixes it,but I still got WA

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
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
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
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
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

### 231 Testing The CATCHER

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
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

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
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

### Thanx a lot guys

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
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

### Hi, it's me again

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
New poster
Posts: 1
Joined: Thu May 29, 2003 5:32 pm
Contact:

LeoST
New poster
Posts: 7
Joined: Thu Dec 25, 2003 5:10 pm
Location: Russia

### 231

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);
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;
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);
end;

end.
Best reguards

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
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
New poster
Posts: 7
Joined: Thu Dec 25, 2003 5:10 pm
Location: Russia

### I got ACCEPTED

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

Yen
New poster
Posts: 2
Joined: Mon May 10, 2004 5:32 am
Contact:

### Problem On 231(Testing The CATCHER)

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