## 497 - Strategic Defense Initiative

Moderator: Board moderators

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
jiayaoyu wrote: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?
my accepted solution gives '1 3 5', so no problem with this kinda input, because as the problem statement depicts, there's no such input . check your code again, may be you're missing something else.
Istiaque Ahmed [the LA-Z-BOy]

setoj
New poster
Posts: 1
Joined: Sun Mar 30, 2003 7:56 am
Contact:

#include<stdio.h>
#define max 10000
long m,pop[max],b[max],k;

long length(){
long i,j,h;
b[0]=pop[m-1];
h=1;
for(i=m-1-1;i>=0;i--){
if(pop<b[0]){
b[0]=pop;
continue;
}
for(j=h-1;j>=0;j--){
if(pop>b[j]){
if(j==h-1||pop<b[j+1]){
b[++j]=pop;
if(j==h) h++;
break;
}
}
}
}

return h;
}

/*long length(){
long i,j,h=0;
b[m-1]=1;
// h=1;
for(i=m-1-1;i>0;i--){
b=1;
for(j=i+1;j<m;j++)
{
if(pop[j]<pop&&b[j]>=b)
{

b=b[j]+1;
if(b>h){h=b[i];
pri[h]=pop[j];
}
}
}
}

return h;
}

/*long length(long s,long mat,long sm){
long bet,i,best=mat;
for(i=s;i<m;i++)
if(pop[i]<sm){
bet=length(i,mat+1,pop[i]);
if(bet>best) best=bet;
}
return best;
} */
int main()
{
/*@JUDGE_ID: 15769PM 497 C++ "catchar " */

long i=0,p,n,j,pop1[max];
// freopen("c.in","r",stdin);
while(scanf("%ld",&n)==1){
for(i=1;i<=n;i++)
scanf("%ld",&pop1[i]);

m=i;
j=0;
for(i=m-1;i>0;i--)
pop[j++]=pop1[i];
k=0;
m=j;
p=length();
printf("Max hits: %ld\n",p);
for(i=0;i<p;i++)
printf("%ld\n",b[i]);
}

return 0;
}

tzzx
New poster
Posts: 14
Joined: Thu May 15, 2003 6:29 am

### 497 TLE

who can tell me a nlogn one
i need the code.
thanks a lot.
[pascal]//uva497
const
maxn=1000;
var
a,f,pre:array[1..maxn] of longint;
n,best_i,best,i,j:integer;

procedure print(i:integer);
begin
if i<>0 then begin
print(pre);
writeln(a);
end;
end;

begin
n:=0;
while not eof(input) do begin
inc(n);
end;
f[1]:=1;
for i:=2 to n do begin
f:=1;
pre:=0;
for j:=1 to i-1 do
if (a[j]<a) and (f[j]+1>f) then begin
f:=f[j]+1;
pre:=j;
end;
end;
best:=0;best_i:=0;
for i:=1 to n do
if best<f then begin
best:=f;
best_i:=i;
end;
write('Max hits: ');
writeln(best);
print(best_i);

end.
[/pascal]

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
this is a multiple input problem; did you consider this?
http://acm.uva.es/problemset/minput.html
Istiaque Ahmed [the LA-Z-BOy]

tzzx
New poster
Posts: 14
Joined: Thu May 15, 2003 6:29 am
i changed my code a little
but this time it got WA,
could andone post a correct one for me?
[pascal]
//uva497
const
maxn=2000;
var
a,f,pre:array[1..maxn] of longint;
n,best_i,best,i,j:integer;
s:string;
procedure print(i:integer);
begin
if i<>0 then begin
print(pre);
writeln(a);
end;
end;

begin
//assign(input,'in1');reset(input);
repeat
if eof(input) then break;
n:=0;
while true do begin
inc(n);
if s='' then break;
val(s,a[n]);
end;
if n=0 then continue;
f[1]:=1;pre[1]:=0;
for i:=2 to n do begin
f:=1;
pre:=0;
for j:=1 to i-1 do
if (a[j]<=a) and (f[j]+1>f) then begin
f:=f[j]+1;
pre:=j;
end;
end;
best:=0;best_i:=0;
for i:=1 to n do
if best<f then begin
best:=f;
best_i:=i;
end;
write('Max hits: ');
writeln(best);
print(best_i);
writeln;
until false;
end.

[/pascal]

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
your prog seems ok to me, you are still getting puzzled with multiple input problems i think, because you are not handling it correctly still . anyway, multiple input problem starts with with a number to denote how many blocks of input are present, then the blocks of input are given with a seperating blank line, seperating them. so, for this problem the input may be like this:

Code: Select all

3

5
6
2
13

4
5

1
2
3
so modifying your code a little would get accepted:
[pascal]
{ blah blah variable declaration here }
var
mulinput,kounter:integer;
dummystr:string;
{ ... more variables and procedures }

{ main procedure here }
begin
readln(dummystr); { track the blank line }

for kounter:=1 to mulinput do
begin
{ repeat }

if eof(input) then break;
n:=0;
{ ... more code goes here }
{ until false; }
end;
end.[/pascal]this prog should produce P.E, and if you handle the output correctly according to the mulinput procedures, you'll overcome P.E.
ps. i am not familiar with pascal, so sorry if anything is wrong!
Istiaque Ahmed [the LA-Z-BOy]

raymond85
New poster
Posts: 21
Joined: Tue Jul 01, 2003 9:26 am
Location: Hong Kong
Contact:

### 497 - Why P.E.?

I got an AC for this question. However, it shows Accepted(P.E.). I dont know why I got presentation error here. I really want to know since I got P.E. too in another similar question 231.

here's my code for 497, plz help! Thx!

Code: Select all

program q231;
var
a,b,c : array[0..100000] of longint;
i,j,k,m,n,p,y,z : longint;
s : ansistring;

function max(a,b:longint):longint;
begin
if   a>b
then max:=a
else max:=b;
end;

begin
for z:=1 to n do
begin
j:=0;
k:=0;
s:='1';
while (s<>'') do
begin
s:='';
if   s=''
then break;
val(s,k,y);
inc(j);
a[j]:=k;
end;
for i:=1 to j do
b[i]:=1;
for i:=1 to j do
for k:=i+1 to j do
if   a[i]<a[k]
then b[k]:=max(b[i]+1,b[k]);
k:=-1;
for i:=1 to j do
if   b[i]>k
then k:=b[i];
writeln('Max Hits: ',k);
p:=k;
for i:=0 to k do
c[i]:=maxint;
m:=0;
while (p>0) do
begin
for i:=1 to j do
if   (b[i]=p) and (a[i]<=c[m])
then begin
inc(m);
c[m]:=a[i];
break;
end;
dec(p);
end;
for i:=k downto 1 do
writeln(c[i]);
if   (z<>n)
then writeln;
end;
end.

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

### never mind

never mind
Last edited by oriol78 on Wed Jul 30, 2003 10:51 pm, edited 1 time in total.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
This is multiple input problem. Have you take care that ?

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm
no, but i don't understand....

"Input to your program will consist of a sequence of integer altitudes, each on a separate line. "

how can i known how many inputs are?

(sorry, u know my english is poor )

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm
now, the link don't korks well, can you explain me what can i do with my code

(i need learn english, i know, sorry -P )

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Code: Select all

The first line of a multiple input file is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format is the same as the input format, without the integer N (and without the blank line following it, of course), i.e.

The input should be like this:

2 <-- The number of test cases
<-- A blank line
3 <-- First data set
<-- A blank line
3 <-- Second data set.

And the output should be like that:

asdf <-- First output
<-- A blank line
asdf <-- Second output

As an example, for problem number 100 a multiple input/output files could be as follows

Input

3

1 10
100 200
201 210
900 1000

1 10
201 210
900 1000

100 200
201 210

Output

1 10 20
100 200 125
201 210 89
900 1000 174

1 10 20
201 210 89
900 1000 174

100 200 125
201 210 89
hope this helps.

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm
can u send me any inputs for 497 plz?

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
The input is like this oriol:

[code]
input:
3

1
6
2
3
5

7
18
2
3
45
6

1
2

output:
Max hits: 4
1
2
3
5

Max hits: 3
7
18
45

Max hits: 2
1
2
[/code]

Hope it helps.

Best regards,
RS