497 - Strategic Defense Initiative

[the LA-Z-BOy]

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.

[setoj]

#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]

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

this is a multiple input problem; did you consider this?
http://acm.uva.es/problemset/minput.html

[tzzx]

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);
readln(s);
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]

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(mulinput);
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!

[raymond85]

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
   readln(n);
   readln(s);
   for z:=1 to n do
   begin
      j:=0;
      k:=0;
      s:='1';
      while (s<>'') do
      begin
         s:='';
         readln(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]

never mind

[Red Scorpion]

This is multiple input problem. Have you take care that ?

[oriol78]

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]

read about multiply input in top of index page ....


Best regards
DM

[oriol78]

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]

The multiple input problems have the blue sign in index page.

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]

can u send me any inputs for 497 plz?

[Red Scorpion]

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