## 497 - Strategic Defense Initiative

Moderator: Board moderators

nayaya
New poster
Posts: 9
Joined: Sat Jun 08, 2002 1:57 pm

[pascal]
program p497(input,output);
type
sss=array[1..2000] of integer;
var
a,b,h,x:sss;
i,j,max1,max2,max,n,s,k:integer;

procedure work;
begin
n:=n+1;
b[n]:=0;
max1:=0;max2:=0;
for i:=1 to n-1 do
if (a>max1) and (h[n]>h) then
begin
max1:=a;
max2:=i;
end;
a[n]:=max1+1;
b[n]:=max2;
if a[n]>max then
begin
max:=a[n];
s:=n;
end;
end;

procedure out;
begin
writeln('Max hits: ',max);
j:=1;
x[1]:=s;
i:=b[s];
while(i>0) do
begin
j:=j+1;
x[j]:=i;
i:=b;
end;
writeln('Max hits: ',max);
for i:=j downto 1 do writeln(h[x]);
end;

Begin
max:=0;n:=0;
while not eof(input) do work;
out;
end.

[/pascal]

Robbie
New poster
Posts: 15
Joined: Wed Aug 07, 2002 11:38 am
Location: Viet Nam

Too much 'Max hits '

nayaya
New poster
Posts: 9
Joined: Sat Jun 08, 2002 1:57 pm

### Still WA! Why?

program p497(input,output);
type
sss=array[1..2000] of integer;
var
a,b,h,x:sss;
i,j,max1,max2,max,n,s,k:integer;

procedure work;
begin
n:=n+1;
b[n]:=0;
max1:=0;max2:=0;
for i:=1 to n-1 do
if (a>max1) and (h[n]>h) then
begin
max1:=a;
max2:=i;
end;
a[n]:=max1+1;
b[n]:=max2;
if a[n]>max then
begin
max:=a[n];
s:=n;
end;
end;

procedure out;
begin
j:=1;
x[1]:=s;
i:=b[s];
while(i>0) do
begin
j:=j+1;
x[j]:=i;
i:=b;
end;
writeln('Max hits: ',max);
for i:=j downto 1 do writeln(h[x]);
end;

Begin
max:=0;n:=0;
while not eof(input) do work;
out;
end.

This time I still get WA. Why? Can you help me? And what is 'multiple input'?

sayeed
New poster
Posts: 8
Joined: Wed Aug 07, 2002 9:00 pm
you find ABout multiple input in problemset page.see this ,this is a different input format.

nayaya
New poster
Posts: 9
Joined: Sat Jun 08, 2002 1:57 pm
Thank you. Now I have corrected and got AC.

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

### p497 Strategic Defense Initiative [ WA ]

Here is my source

i got WA..

but i cannot find any wrong

thanks

[c]
#include "stdio.h"
#include "string.h"
void main()
{

int N;

scanf("%d\n",&N);
for(;N;N--){
int count,data[2001],length,lis[2001],i;
int left,right,mid;
char arr[10];

count=-1;
while( gets(arr) ){
if(strlen(arr)==0) break;
sscanf(arr,"%d",&data[++count]);
}

/**Dynamic Programming -- LIS**/
lis[0]=data[0];
length=0;
for(i=1;i<=count;i++)
if(data>lis[length])
lis[++length]=data;
else if(data<lis[0])
lis[0]=data;
else{
for( left=0,right=length;left!=right-1 ; ) {
mid=(left+right)/2;
(lis[mid]<=data)?(left=mid):(right=mid);
}
lis[right]=data;
}

/**Output**/

printf("Max hits: %d\n",length+1);

for(i=0;i<=length;i++)
printf("%d\n",lis);
putchar('\n');
}
}

[/c]

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
if there is more than one solution what should I print?

I have no idea.....

The problem is not difficult.

But I can't find any wrong in my source...

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### Hi!

Hi!

First read the problem statement carefully Look:
Their missles will always be fired in a sequence such that there will only be one solution to the problem posed above.
And you should see that this is multiple input program...

Try to check your program on this input:
4

4
3
5
4
6
4

1
1
1

1
2
3

3
2
2
Good Luck

saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Contact:
how do u say the following input has a unique solution?!?

3
2
2

!!!!!!

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:
Yes you are right.
3
2
2
does not have a unique solution. But that'd not be a problem I guess. I've used assertion to validate if there's an unique solution to the judge input. And as it turns out (if I'm not mistaken), the solutions are unique.

I'm using the Dynamic Programming for Longest Increasing Sequence without any modification.

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France
What is wrong with this code
can anybody help plz

[cpp]
//misile "dynamic prloblem"

#include<stdio.h>
#include<values.h>
#include<string.h>

#define inf MAXLONG-2

long hit[1000];
long hight[1000];

void show(long max,long i,long ph)
{
long k;
for(k = i;k > 0;k--)
{
if(hit[k] == max)
{
if(ph > hight[k])
{
show(max-1,i-1,hight[k]);
printf("%ld\n",hight[k]);
return;
}
}
}
}

void main(void){
long i,j,n,imax,max,t;
char str[100];
//freopen("497.in","r",stdin);

scanf("%ld\n",&t);
scanf("\n");

while(t--)
{

n=0;
i=1;
while(gets(str))
{
if(!strlen(str))
break;
sscanf(str,"%ld",&hight);
n++;
i++;

}

hit[1] = 1;
imax = 1;

for(i = 2;i <= n;i++)
{
hit = 1;
for(j = i-1;j > 0;j--)
if(hight > hight[j] && hit < hit[j]+1)
hit = hit[j]+1;

if(hit > hit[imax]) imax = i;
}

printf("Max hits: %ld\n",hit[imax]);

show(hit[imax],imax,inf);
printf("\n");
}
}
[/cpp]

Thanks

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Be careful with multiple input and 0 size questions:
(Note the spaces)

Code: Select all

``````5

1

2

3

6
``````
Should output:

Code: Select all

``````Max hits: 1
1

Max hits: 1
2

Max hits: 1
3

Max hits: 0

Max hits: 1
6``````
but you give

Code: Select all

``````Max hits: 1
1

Max hits: 1
2

Max hits: 1
3

Max hits: 1
3

Max hits: 1
6``````

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
Larry wrote:Be careful with multiple input and 0 size questions:
(Note the spaces)

Code: Select all

``````5

1

2

3

6
``````
Hmmm, I don't think there's such kind of input. My prog would crash if there was any blank input (0 size), but i got AC!
So there's no Zero Sized questions

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Well, I couldn't get it to accept until I fixed the zero case... maybe it was just me..

jiayaoyu
New poster
Posts: 5
Joined: Fri Jun 14, 2002 1:10 am
Location: Lancaster.UK
Could someone tell me why '1 3 2 5 4'should give '1 3 4'?

My prog(WA) gives '1 3 5', is there anything i missed out in the problem description?