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

дистанційна підтримка освіти школярів


Цепь
http://acm.pku.edu.cn/JudgeOnline/problem?id=1090

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

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

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

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

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

   Пример решения на 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;
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)