ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1112. Покрытие

Help me I got WA!!!
Послано Algorithmus_UA(algorithmus@univ.kiev.ua) 12 июн 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! (+)
Послано shitty.Mishka 13 июн 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.
Послано Algorithmus_UA(algorithmus@univ.kiev.ua) 13 июн 2002 13:55
Your brain is strange - you must read more carefull - ( Ai<>Bi ) - So 1 1 is invalid input!
Послано pes 22 мар 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!!!
Послано xurshid_n 22 дек 2005 18:11
1)beginning values of "h" no defined before while l<> 0

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