记录编号	15345	评测结果	AAAAAAAAAAAAA
题目名称	[POI 1999] 三色二叉树	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.031 s
提交时间	2009-11-11 20:57:26	内存使用	0.35 MiB

program trot;
{1=R,2=G,3,B}
var
  s:ansistring;
  tree:array [1..25000] of record
    l,r:integer;
  end;
  dp:array [1..25000,1..3] of integer;
  ans,top,w,i:integer;
procedure build(root:integer);
begin
  if s[w]='2' then begin
    inc(top);
    tree[root].l:=top;
    inc(top);
    tree[root].r:=top;
    inc(w);
    build(tree[root].l);
    build(tree[root].r);
  end
  else if s[w]='1' then begin
    inc(top);
    tree[root].l:=top;
    inc(w);
    build (tree[root].l);
  end
  else inc(w);
end;
procedure getmax(root,c:integer);
var c1,c2:integer;
begin
  dp[root,c]:=0;
  if tree[root].l=0 then begin
    if c=2 then dp[root,c]:=1;
  end
  else if tree[root].r=0 then begin
    if c=1 then begin
      c1:=2;c2:=3;
    end
    else if c=2 then begin
      c1:=1;c2:=3;
      dp[root,c]:=1;
    end
    else begin
      c1:=1;c2:=2;
    end;
    if dp[tree[root].l,c1]=-1 then getmax (tree[root].l,c1);
    if dp[tree[root].l,c2]=-1 then getmax (tree[root].l,c2);
    if dp[tree[root].l,c1]>dp[tree[root].l,c2] then inc(dp[root,c],dp[tree[root].l,c1]) else inc(dp[root,c],dp[tree[root].l,c2]);
  end
  else begin
    if c=1 then begin
      c1:=2;c2:=3;
    end
    else if c=2 then begin
      c1:=1;c2:=3;
      dp[root,c]:=1;
    end
    else begin
      c1:=1;c2:=2;
    end;
    if dp[tree[root].l,c1]=-1 then getmax(tree[root].l,c1);
    if dp[tree[root].r,c2]=-1 then getmax(tree[root].r,c2);
    if dp[tree[root].l,c2]=-1 then getmax(tree[root].l,c2);
    if dp[tree[root].r,c1]=-1 then getmax(tree[root].r,c1);
    if dp[tree[root].l,c1]+dp[tree[root].r,c2]>dp[tree[root].l,c2]+dp[tree[root].r,c1] then
      inc(dp[root,c],dp[tree[root].l,c1]+dp[tree[root].r,c2])
    else inc(dp[root,c],dp[tree[root].l,c2]+dp[tree[root].r,c1]);
  end;
end;
procedure getmin(root,c:integer);
var c1,c2:integer;
begin
  dp[root,c]:=0;
  if tree[root].l=0 then begin
    if c=2 then dp[root,c]:=1;
  end
  else if tree[root].r=0 then begin
    if c=1 then begin
      c1:=2;c2:=3;
    end
    else if c=2 then begin
      c1:=1;c2:=3;
      dp[root,c]:=1;
    end
    else begin
      c1:=1;c2:=2;
    end;
    if dp[tree[root].l,c1]=-1 then getmin (tree[root].l,c1);
    if dp[tree[root].l,c2]=-1 then getmin (tree[root].l,c2);
    if dp[tree[root].l,c1]<dp[tree[root].l,c2] then inc(dp[root,c],dp[tree[root].l,c1]) else inc(dp[root,c],dp[tree[root].l,c2]);
  end
  else begin
    if c=1 then begin
      c1:=2;c2:=3;
    end
    else if c=2 then begin
      c1:=1;c2:=3;
      dp[root,c]:=1;
    end
    else begin
      c1:=1;c2:=2;
    end;
    if dp[tree[root].l,c1]=-1 then getmin(tree[root].l,c1);
    if dp[tree[root].r,c2]=-1 then getmin(tree[root].r,c2);
    if dp[tree[root].l,c2]=-1 then getmin(tree[root].l,c2);
    if dp[tree[root].r,c1]=-1 then getmin(tree[root].r,c1);
    if dp[tree[root].l,c1]+dp[tree[root].r,c2]<dp[tree[root].l,c2]+dp[tree[root].r,c1] then
      inc(dp[root,c],dp[tree[root].l,c1]+dp[tree[root].r,c2])
    else inc(dp[root,c],dp[tree[root].l,c2]+dp[tree[root].r,c1]);
  end;
end;
begin
  fillchar (dp,sizeof(dp),$FF);
  assign (input,'trot.in');
  reset (input);
  readln (s);
  close (input);
  top:=1;w:=1;
  build(1);
  assign (output,'trot.out');
  rewrite (output);
  ans:=0;
  for i:=1 to 3 do begin
    getmax(1,i);
    if dp[1,i]>ans then ans:=dp[1,i];
  end;
  write (ans,' ');
  ans:=maxint;
  fillchar (dp,sizeof(dp),$FF);
  for i:=1 to 3 do begin
    getmin(1,i);
    if dp[1,i]<ans then ans:=dp[1,i];
  end;
  writeln (ans);
  close (output);
end.