497 - Strategic Defense Initiative

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

Moderator: Board moderators

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

497:Why WA?Please help me

Post by 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
New poster
Posts: 15
Joined: Wed Aug 07, 2002 11:38 am
Location: Viet Nam

Re: 497:Why WA?Please help me

Post by Robbie »

Too much 'Max hits '

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

Still WA! Why?

Post by 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
New poster
Posts: 8
Joined: Wed Aug 07, 2002 9:00 pm

Post by sayeed »

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

Post by nayaya »

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 ]

Post by hank »

Here is my source

i got WA..

but i cannot find any wrong


please help me

thanks

:oops:
[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.

Post by 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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Hi!

Post by 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 :wink:

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal »

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

3
2
2

!!!!!! :o

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by 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
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by 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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by 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
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy »

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 :wink:

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

Post by Larry »

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

Post by 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?

Post Reply

Return to “Volume 4 (400-499)”