Page 4 of 10
Posted: Thu Jan 23, 2003 6:34 am
by the LA-Z-BOy
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.
please help me........ why wrong! p:497
Posted: Mon Mar 31, 2003 10:36 am
by 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;
}
497 TLE
Posted: Sun May 18, 2003 1:27 pm
by 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]
Posted: Sun May 18, 2003 10:53 pm
by the LA-Z-BOy
this is a
multiple input problem; did you consider this?
http://acm.uva.es/problemset/minput.html
Posted: Mon May 19, 2003 1:05 am
by 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]
Posted: Mon May 19, 2003 5:10 pm
by 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:
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!
497 - Why P.E.?
Posted: Tue Jul 01, 2003 9:32 am
by 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.
never mind
Posted: Wed Jul 16, 2003 12:57 pm
by oriol78
never mind
Posted: Fri Jul 18, 2003 4:08 am
by Red Scorpion
This is multiple input problem. Have you take care that ?
Posted: Fri Jul 18, 2003 11:22 am
by 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
)
Posted: Fri Jul 18, 2003 11:44 am
by Dominik Michniewski
read about multiply input in top of index page ....
Best regards
DM
Posted: Fri Jul 18, 2003 6:36 pm
by 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 )
Posted: Mon Jul 21, 2003 6:28 am
by 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.
Posted: Mon Jul 21, 2003 10:23 am
by oriol78
can u send me any inputs for 497 plz?
Posted: Tue Jul 22, 2003 8:50 am
by 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