M00PAIR - 0 0 Pairs

Tác giả: khuc_tuan

Ngôn ngữ: Pascal

// {$APPTYPE CONSOLE}
 {$mode delphi}

const
    MAXCS = 40;
    COSO = 100000000;

type
    BigNum = class
        a : array[1..MAXCS] of integer;
        constructor init;
        procedure add(b : BigNum);
        procedure print();
        function clone : BigNum;
    end;

constructor BigNum.init;
var
    i : integer;
begin
    for i:=1 to MAXCS do
        a[i] := 0;
end;

procedure BigNum.add(b : BigNum);
var
    n, i : integer;
begin
    n := 0;
    for i:=1 to MAXCS do
    begin
        n := n + a[i] + b.a[i];
        a[i] := n mod COSO;
        n := n div COSO;
    end;
end;

procedure BigNum.print;
var
    i, j, c, k, x : integer;
begin
    for i:=MAXCS downto 1 do if a[i]>0 then
    begin
        write(a[i]);
        for j:=i-1 downto 1 do
        begin
            c := COSO;
            x := a[j];
            for k:=1 to 8 do
            begin
                c := c div 10;
                write(x div c);
                x := x mod c;
            end;
        end;
        writeln;
        exit;
    end;
    writeln(0);
end;

function BigNum.clone : BigNum;
var
    r : BigNum;
    i : integer;
begin
    r := BigNum.init;
    for i:=1 to MAXCS do r.a[i] := a[i];
    clone := r;
end;


var
    n, i, j, k : integer;
    F : array[1..1000,0..1,0..1] of BigNum;
    sl : BigNum;
begin
    for i:=1 to 1000 do
        for j:=0 to 1 do
            for k:=0 to 1 do
                F[i,j,k] := BigNum.init;
    sl := BigNum.init;
    F[1][0][1].a[1] := 1;
    sl.a[1] := 1;
    for i:=2 to 1000 do
    begin
        F[i][0][0] := F[i-1][0][1].clone;
        F[i][1][1] := F[i-1][1][0].clone;
        F[i][1][0] := sl.clone;
        F[i][1][0].add(F[i-1][1][1]);
        F[i][0][1] := sl.clone;
        F[i][0][1].add(F[i-1][0][0]);
        sl.add(sl);
    end;
    while not eof do
    begin
        // n := -1;
        readln(n);

        F[n][0][0].print;
    end;
end.

Download