Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на Pascal:

program PKU1090;
{$I-, s-, q-, r-}

const maxn = 1000;
  maxl = 8;
  modes = 100000000;

type integer = longint;
     node = array[0..100] of integer;

var line: array[1..maxn] of integer;
    f, p, g: array[0..maxn] of node;
    n: integer;

procedure prepare;
var i: integer;
begin
  read(n);
  for i := 1 to n do read(line[i]);
end;

procedure mult(var a: node; k: integer);
var i, tmp: integer;
begin
  tmp := 0;
  for i := 1 to a[0] do begin
    a[i] := a[i] * k + tmp;
    tmp := a[i] div modes;
    a[i] := a[i] - tmp * modes;
  end;
  if tmp > 0 then begin
    inc(a[0]);
    a[a[0]] := tmp;
  end;
end;

procedure add(var a, b: node);
var i, tmp: integer;
begin
  if b[0] > a[0] then a[0] := b[0];
  tmp := 0;
  for i := 1 to a[0] do begin
    a[i] := a[i] + b[i] + tmp;
    tmp := a[i] div modes;
    a[i] := a[i] - tmp * modes;
  end;
  if tmp > 0 then begin
    inc(a[0]);
    a[a[0]] := tmp;
  end;
end;

var st: string;

procedure print(var a: node);
var i: integer;
begin
  if a[0] = 0 then writeln(0) else begin
    write(a[a[0]]);
    for i := a[0] - 1 downto 1 do begin
      str(a[i], st);
      while length(st) < maxl do st := '0' + st;
      write(st);
    end;
    writeln;
  end;
end;

procedure main;
var i: integer;
begin
  fillchar(f, sizeof(f), 0);
  fillchar(g, sizeof(g), 0);
  fillchar(p, sizeof(p), 0);
  p[0, 1] := 1; p[0, 0] := 1;
  for i := 1 to n do begin
    p[i] := p[i - 1];
    mult(p[i], 2);
    if line[i] = 1 then begin
      g[i] := f[i - 1];
      f[i] := g[i - 1];
      add(f[i], p[i - 1]);
    end else begin
      f[i] := f[i - 1];
      g[i] := g[i - 1];
      add(g[i], p[i - 1]);
    end;
  end;
  print(f[n]);
end;

begin
  prepare;
  main;
end.

   Пример решения на C++:

#include "iostream"
#include "string.h"
using namespace std;

const int MAXLEN=330;

void plus(char * num1,char * num2,char * result)
{
    int i,x,y;
    y=1;
    for(i=MAXLEN-1; i >= 0; i--)
    {
        x=num1[i]-'0'+num2[i]-'0'+y;
        y=x/10;
        x=x%10;
        result[i]=x+'0';
    }
}

int main()
{
    int total;
    char sign[1000];
    char change[MAXLEN+1];
    char temp[MAXLEN+1];
    char BeforeResult[2][MAXLEN+1];
    char AfterResult[2][MAXLEN+1];
    int i,j,length;
    cin >> total;
    change[MAXLEN]=BeforeResult[0][MAXLEN]=AfterResult[0][MAXLEN]
        =BeforeResult[1][MAXLEN]=AfterResult[1][MAXLEN]='\0';
    while(cin)
    {
         for(i=0; i < MAXLEN; i++)
        BeforeResult[0][i]=BeforeResult[1][i]=change[i]='0';
        change[MAXLEN-1]='1';
        length=-1;
        for(i=0; i < total; i++)
       {
           cin >> sign[i];
           if(sign[i]=='1') length=i+1;
       }
       if(length==-1) cout << 0 << endl;
       else {
      
       if(sign[0]=='0')
           BeforeResult[1][MAXLEN-1]='1';
       else
           BeforeResult[0][MAXLEN-1]='1';
      
       for(i=1; i < length; i++)
       {
           if(sign[i]=='0')
           {
               plus(BeforeResult[1],change,AfterResult[1]);
               strcpy(BeforeResult[1],AfterResult[1]);
           }
           else
           {   strcpy(temp,BeforeResult[0]);
               plus(BeforeResult[1],change,AfterResult[0]);
               strcpy(BeforeResult[0],AfterResult[0]);
               strcpy(BeforeResult[1],temp);
            }
          for(j=0; j < MAXLEN; j++)
             temp[j]='0';
           plus(change,change,temp);
           strcpy(change,temp);
}
     i=0;
     while(BeforeResult[0][i]=='0')
         i++;
     while(i < MAXLEN)
     {     cout << BeforeResult[0][i]; i++;}
     cout << endl;
   
       }
     cin >> total;
  }
  return 0;
}