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 1022. Genealogical Tree

Why I got WA? Program is here, I'm sure, it's correct!!!
Posted by Akshin 31 Mar 2005 18:21
Here is my program, I dont why I get WA?
My algorithm is correct!

var
  a:array[1..100,1..100] of integer;
  b:array[1..100] of integer;
  i,j,nn,n,k:integer;

procedure readdata;
begin
  readln(n);
  for i:=1 to n do
  begin
    j:=0;
    repeat
      inc(j);
      read(a[i,j]);
    until a[i,j]=0;
    a[i,j]:=-1;
  end;
end;

procedure writedata;
begin
  for i:=1 to n do
  write(b[i],' ');
end;

function check(i,nn:integer):boolean;
var
  j:integer;
begin
  j:=1; check:=false;
  if a[nn,j]<>-1 then
  repeat
    if a[nn,j]=i then
    begin
      check:=true;
      exit;
    end;
    inc(j);
  until a[nn,j]=-1;
end;

procedure push(k,nn:integer);
var
  x,m,j,i:integer;
begin
  j:=1;
  while (b[j]<>k) do inc(j);
  m:=j;

{  x:=b[k];}
  for j:=nn downto k do
  if (j-1<1) then break else
  b[j]:=b[j-1];
{  b[nn]:=x;}

{  j:=nn;
  while (b[j]<>m) do
  begin
    b[j]:=b[j-1];
    dec(j);
  end;}

  b[m]:=nn;
end;

begin
  readdata;
  repeat
    inc(nn);
    b[nn]:=nn;
    k:=0;
    for i:=nn downto 1 do
    if (i<>nn) and (check(i,nn)) then k:=i;
    if k<>0 then push(k,nn);
  until nn=n;
  writedata;
end.
Re: Why I got WA? Program is here, I'm sure, it's correct!!!
Posted by Виктор Крупко 31 Mar 2005 23:42
I shall not assort your algorithm, but I shall offer the.
Search for number present which is not present in a file and deduce him, then remove this element. And all this in a cycle. { I badly know English. }
Re: Why I got WA? Program is here, I'm sure, it's correct!!!
Posted by Cybernetics Team 1 Apr 2005 14:26
Here are some tests:

Test #2:
6
0
0
5 0
0
0
0

Test #3:
2
0
1 0

Test #7:
1
0
Re: Why I got WA? Program is here, I'm sure, it's correct!!!
Posted by iliqn havov 3 Jul 2006 20:39
You just have to use topological sort
Re: Why I got WA? Program is here, I'm sure, it's correct!!!
Posted by Todor Tsonkov 14 Jul 2006 00:21
And you can find about topological sort here:
http://en.wikipedia.org/wiki/Topological_sorting