ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1112. Cover

Help me I got WA!!!
Posted by Algorithmus_UA(algorithmus@univ.kiev.ua) 12 Jun 2002 21:20
type
PointType = record
   X, Y : integer;
 end;

var a:array[1..100]of pointtype;
    c,b,s:array[1..100]of integer;
    N,i,j,max,l,h,ccc:integer;
procedure sort(l,r: integer);
var
  i,j: integer;
  x,y :pointtype;
begin
  i:=l; j:=r; x:=a[(l+r) DIV 2];
  repeat
    while a[i].y<x.y do i:=i+1;
    while x.y<a[j].y do j:=j-1;
    if i<=j then
    begin
      y:=a[i]; a[i]:=a[j]; a[j]:=y;
      i:=i+1; j:=j-1;
    end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;

begin
  readln(N);
  for i:=1 to N do
  begin
    readln(a[i].x,a[i].y);
    if a[i].x>a[i].y then
    begin
     ccc:=a[i].x;a[i].x:=a[i].y;a[i].y:=ccc;
    end;
  end;
  sort(1,N);
  for i:=1 to N do
  begin
    c[i]:=1;b[i]:=0;
    for j:=1 to i-1 do if (a[j].y <= a[i].x)and(c[j]+1>c[i])then
    begin
      c[i]:=c[j]+1;
      b[i]:=j;
    end;
  end;
  max:=-1;
  for i:=1 to N do if max<c[i] then
  begin
    max:=c[i];
    l:=i;
  end;
  while l<>0 do
  begin
    inc(h);
    s[h]:=l;
    l:=b[l];
  end;
  writeln(c[i]);
  for i:=h downto 1 do writeln(a[s[i]].x,' ',a[s[i]].y);
end.
That's really strange! (+)
Posted by shitty.Mishka 13 Jun 2002 12:41
I think I found a bug in my AC program
How do you think, what should be the answer for this test:
2
1 1
1 1
I think it should be
1
1 1
but the answer of my program is
2
1 1
1 1
(this is also the answer of your program)
Anyway, if there's something I don't understand, I found a test on
which the answers of our program differ. Even more, your program
outputs "4" followed by 5 segments instead of 4
Sorry, but I had no time for finding the reason for this.
So, here's the test:

22
1 1
-1 2
-3 3
6 3
1 3
2 5
1 4
2 6
5 7
1 3
4 6
7 9
2 5
5 9
2 9
2 4
3 5
4 6
6 8
5 7
1 3
7 9
Thank you very much, I have so stupid bug! Now I have AC.
Posted by Algorithmus_UA(algorithmus@univ.kiev.ua) 13 Jun 2002 13:55
Your brain is strange - you must read more carefull - ( Ai<>Bi ) - So 1 1 is invalid input!
Posted by pes 22 Mar 2003 15:58

> I think I found a bug in my AC program
> How do you think, what should be the answer for this test:
> 2
> 1 1
> 1 1
> I think it should be
> 1
> 1 1
> but the answer of my program is
> 2
> 1 1
> 1 1
> (this is also the answer of your program)
> Anyway, if there's something I don't understand, I found a test on
> which the answers of our program differ. Even more, your program
> outputs "4" followed by 5 segments instead of 4
> Sorry, but I had no time for finding the reason for this.
> So, here's the test:
>
> 22
> 1 1
> -1 2
> -3 3
> 6 3
> 1 3
> 2 5
> 1 4
> 2 6
> 5 7
> 1 3
> 4 6
> 7 9
> 2 5
> 5 9
> 2 9
> 2 4
> 3 5
> 4 6
> 6 8
> 5 7
> 1 3
> 7 9
>
>
Re: Help me I got WA!!!
Posted by xurshid_n 22 Dec 2005 18:11
1)beginning values of "h" no defined before while l<> 0

2) writeln(c[i]); - no right
   writeln(max) - right