记录编号	22210	评测结果	AAAAAAAAAA
题目名称	拯救	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	0.032 s
提交时间	2010-11-17 17:45:40	内存使用	1.26 MiB

{拯救 NOIP模拟2010-11-17
 数值递推 高精度计算
 Author: yangbohua
 Time: 2010-11-17}
 
program savey;
type
  t=array[0..400] of byte;
 
var
  g:array[0..1000] of t;
  lg:array[0..1000] of integer;
  f:array[0..1,0..1000] of t;
  lf:array[0..1,0..1000] of integer;
  n,i,a,p:integer;
 
procedure add(a,b:t;la,lb:integer;var c:t;var lc:integer);
var
  i,l:integer;
begin
  fillchar(c,sizeof(c),0);
  if la>lb
    then l:=la
    else l:=lb;
  for i:=1 to l do
  begin
    c[i]:=c[i]+a[i]+b[i];
    if c[i]>=10 then
    begin
      c[i]:=c[i]-10;
      c[i+1]:=c[i+1]+1;
    end;
  end;
  if c[l+1]>0
    then lc:=l+1
    else lc:=l;
end;
 
begin
  assign(input,'savey.in');
  reset(input);
  assign(output,'savey.out');
  rewrite(output);
  readln(n);
  g[1,1]:=1;
  lg[1]:=1;
  for i:=2 to n do
  begin
    add(g[i-1],g[i-1],lg[i-1],lg[i-1],g[i],lg[i]);
    g[i,1]:=g[i,1]+1;
    p:=1;
    while g[i,p]>=10 do
    begin
      g[i,p]:=g[i,p]-10;
      g[i,p+1]:=g[i,p+1]+1;
      p:=p+1;
      if p>lg[i] then lg[i]:=p;
    end;
  end;
  read(a);
  if a=1 then
  begin
    f[0,1,1]:=1;
    lf[0,1]:=1;
    f[1,1,1]:=0;
    lf[1,1]:=1;
  end
  else
  begin
    f[0,1,1]:=0;
    lf[0,1]:=1;
    f[1,1,1]:=1;
    lf[1,1]:=1;
  end;
  for i:=2 to n do
  begin
    read(a);
    if a=1 then
    begin
      f[1,i]:=f[0,i-1];
      lf[1,i]:=lf[0,i-1];
      add(f[1,i-1],g[i-1],lf[1,i-1],lg[i-1],f[0,i],lf[0,i]);
      f[0,i,1]:=f[0,i,1]+1;
      p:=1;
      while f[0,i,p]>=10 do
      begin
        f[0,i,p]:=f[0,i,p]-10;
        f[0,i,p+1]:=f[0,i,p+1]+1;
        p:=p+1;
        if p>lf[0,i] then lf[0,i]:=p;
      end;
    end
    else
    begin
      f[0,i]:=f[0,i-1];
      lf[0,i]:=lf[0,i-1];
      add(f[1,i-1],g[i-1],lf[1,i-1],lg[i-1],f[1,i],lf[1,i]);
      f[1,i,1]:=f[1,i,1]+1;
      p:=1;
      while f[1,i,p]>=10 do
      begin
        f[1,i,p]:=f[1,i,p]-10;
        f[1,i,p+1]:=f[1,i,p+1]+1;
        p:=p+1;
        if p>lf[1,i] then lf[1,i]:=p;
      end;
    end;
  end;
 
  for i:=lf[0,n] downto 1 do
    write(f[0,n,i]);
  writeln;
  close(input);
  close(output);
end.