记录编号	19274	评测结果	AAAAAAAAAAAAA
题目名称	[POI 1999] 三色二叉树	最终得分	100
用户昵称	reamb	是否通过	通过
代码语言	Pascal	运行时间	0.050 s
提交时间	2010-10-07 15:27:06	内存使用	0.41 MiB

program sanseerchashu;
var
  l,t:longint;
  f,ff:array[1..10000,0..1]of longint;
  tree:array[1..10000,0..2]of longint;
  code:integer;
  b:char;
  a:array[1..10000]of integer;
function max(x,y:longint):longint;
begin
  if x>y then
    max:=x
  else
    max:=y
end;
function min(x,y:longint):longint;
begin
  if x<y then
    min:=x
  else
    min:=y
end;
procedure treedp(k:integer);
var
  i:longint;
begin
  for i:=1 to a[k] do
  begin
    t:=t+1;
    tree[k,0]:=i;
    tree[k,i]:=t;
    treedp(t)
  end;
  if a[k]=0 then
  begin
    f[k,0]:=0;
    f[k,1]:=1;
    ff[k,0]:=0;
    ff[k,1]:=1
  end
  else
    if a[k]=2 then
    begin
      f[k,1]:=f[tree[k,1],0]+f[tree[k,2],0]+1;
      f[k,0]:=max(f[tree[k,1],1]+f[tree[k,2],0],f[tree[k,1],0]+f[tree[k,2],1]);
      ff[k,1]:=ff[tree[k,1],0]+ff[tree[k,2],0]+1;
      ff[k,0]:=min(ff[tree[k,1],1]+ff[tree[k,2],0],ff[tree[k,1],0]+ff[tree[k,2],1])
    end
    else
    begin
      f[k,1]:=f[tree[k,1],0]+1;
      f[k,0]:=max(f[tree[k,1],1],f[tree[k,1],0]);
      ff[k,1]:=ff[tree[k,1],0]+1;
      ff[k,0]:=min(ff[tree[k,1],1],ff[tree[k,1],0])
    end
end;
begin
  assign (input,'trot.in');
  reset (input);
    repeat
      read(b);
      l:=l+1;
      val(b,a[l],code);
    until code<>0;
    l:=l-1;
  close (input);
  t:=1;
  treedp(1);
  assign (output,'trot.out');
  rewrite (output);
    writeln (max(f[1,1],f[1,0]),' ',min(ff[1,1],ff[1,0]));
  close (output)
end.