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

Общий форум

To Rybak Michael. Please, give me some hints and tests for problem 1109(Conference). I don't know why I get WA :-( (++)
Послано Nazarov Denis (nsc2001@rambler.ru) 8 фев 2002 21:00
My program:

Program t1109;

Const MaxN=1000;

Var   G         : array[1..MaxN,1..MaxN]of byte;
      M,N,K     : longint;
      i,j,k1,k2 : longint;
      Ans       : longint;
      Sm,Sn     : array[1..MaxN]of longint;
      Mx,Nx     : longint;
      Om,On     : array[1..MaxN]of byte;
      ex        : boolean;

Procedure Add_m(mnum : longint); forward;
Procedure Add_n(nnum : longint); forward;

Procedure Del_m(mnum : longint);
Var i : longint;
 begin
  for i:=1 to M do
   if G[mnum,i]=1 then begin
    if Sn[i]=1 then Add_n(i) else Sn[i]:=Sn[i]-1;
    G[mnum,i]:=0;
   end;
 end;

Procedure Del_n(nnum : longint);
Var j : longint;
 begin
  for j:=1 to N do
   if G[j,nnum]=1 then begin
    if Sm[j]=1 then Add_m(j) else Sm[j]:=Sm[j]-1;
    G[j,nnum]:=0;
   end;
 end;

Procedure Add_m(mnum : longint);
Var j,jk : longint;
 begin
  Ex:=false;
  Ans:=Ans+1;
  for j:=1 to N do
   if G[mnum,j]=1 then begin
    jk:=j;
    break;
   end;
  G[mnum,jk]:=0;
  Om[mnum]:=1;
  On[jk]:=1;
  Sm[mnum]:=0;
  Sn[jk]:=Sn[jk]-1;
  if Sn[jk]>0 then Del_n(jk);
 end;

Procedure Add_n(nnum : longint);
Var i,ik : longint;
 begin
  Ex:=false;
  Ans:=Ans+1;
  for i:=1 to M do
   if G[i,nnum]=1 then begin
    ik:=i;
    break;
   end;
  G[ik,nnum]:=0;
  On[nnum]:=1;
  Om[ik]:=1;
  Sn[nnum]:=0;
  Sm[ik]:=Sm[ik]-1;
  if Sm[ik]>0 then Del_m(ik);
 end;

begin
 Assign(input,'1109.in');Reset(input);
 FillChar(G,SizeOf(G),0);
 FillChar(Sm,SizeOf(Sm),0);
 FillChar(Sn,SizeOf(Sn),0);
 FillChar(Om,SizeOf(Om),0);
 FillChar(On,SizeOf(On),0);
 Read(M,N,K);
 for i:=1 to K do begin
   Read(k1,k2);
   G[k1,k2]:=1;
   Sm[k1]:=Sm[k1]+1;
   Sn[k2]:=Sn[k2]+1;
  end;
 Ans:=0;
 Repeat
  Ex:=true;
  for i:=1 to M do
   if Om[i]=0 then
    if Sm[i]=1 then
     Add_m(i);
  for i:=1 to N do
   if On[i]=0 then
    if Sn[i]=1 then
     Add_n(i);
 Until Ex;
 Mx:=0;
 Nx:=0;
 for i:=1 to M do if Om[i]=0 then Mx:=Mx+1;
 for i:=1 to N do if On[i]=0 then Nx:=Nx+1;
 if Mx>Nx then Ans:=Ans+Mx else Ans:=Ans+Nx;
 if (M=0)or(N=0) then Ans:=0;
 Writeln(Ans);
end.

I have been dubuging my program since 1st January but with no result.
May be my alogrithm is wrong(I think that this program should get TL,
but not WA),though I work at problem 1159 much more.