497 - Strategic Defense Initiative

[nayaya]

[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;
readln(h[n]);
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]

Too much 'Max hits '

[nayaya]

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;
readln(h[n]);
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]

you find ABout multiple input in problemset page.see this ,this is a different input format.

[nayaya]

Thank you. Now I have corrected and got AC.

[hank]

Here is my source

i got WA..

but i cannot find any wrong


please help me

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]

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]

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]

how do u say the following input has a unique solution?!?

3
2
2

!!!!!!

[kmhasan]

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]

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]

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]

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]

Well, I couldn't get it to accept until I fixed the zero case... maybe it was just me..

[jiayaoyu]

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?