Editorial for 0 0 Pairs


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxn=1000;
      base=1000000000;
      digit=9;
type bignum=array[0..40] of longint;
var a,b:array[0..maxn] of bignum;
    t,i,l,j,num,k:longint;
    c:array[1..10000] of longint;
    s:string;

procedure double(k:integer);
var i:integer;  mem:byte;
begin
     b[k,0]:=b[k-1,0];
     mem:=0;
     for i:=1 to b[k,0] do
     begin
          b[k,i]:=b[k-1,i]+b[k-1,i]+mem;
          if b[k,i]<base then mem:=0
          else
          begin
               b[k,i]:=b[k,i]-base; mem:=1;
          end;
     end;
     if mem>0 then
     begin
          inc(b[k,0]);
          b[k,b[k,0]]:=mem;
     end;
end;

procedure plus(k:integer);
var i:integer; mem:byte;
begin
     if a[k-2,0]<=b[k-2,0] then a[k,0]:=b[k-2,0]
     else a[k,0]:=a[k-2,0];
     mem:=0;
     for i:=1 to a[k,0] do
     begin
          a[k,i]:=a[k-2,i]+b[k-2,i]+mem;
          if a[k,i]<base then mem:=0
          else
          begin
               a[k,i]:=a[k,i]-base; mem:=1;
          end;
     end;
     if mem>0 then
     begin
          inc(a[k,0]);
          a[k,a[k,0]]:=mem;
     end;
end;

procedure init;
var i:integer;
begin
     b[0,0]:=1; b[1,0]:=1; b[0,1]:=1; b[1,1]:=1;
     a[1,0]:=1;
     for i:=2 to j do
     begin
          double(i);
          plus(i);
     end;
end;

begin
     assign(input,fi);
     reset(input);
     assign(output,fo);
     rewrite(output);
     i:=0; j:=0;
     while not eof(input) do
     begin
          inc(i);
          readln(c[i]);
          if c[i]>j then j:=c[i];
     end;
     num:=i;
     init;
     for k:=1 to num do
     begin
          t:=c[k];
          for i:=a[t,0] downto 1 do
          begin
               if i<a[t,0] then
               begin
                    str(a[t,i],s);
                    l:=length(s);
                    for j:=l+1 to digit do write(0);
               end;
               write(a[t,i]);
          end;
          writeln;
     end;
     close(output);
     close(input);
end.

Code mẫu của happyboy99x

#include<cstdio>

const int N = 1000, BASE = 1000000000, LOG_BASE = 9, N_DIGIT = 34;
struct BigInteger {
    int d[N_DIGIT], n;

    void operator ++ () {
        for(int i = 0; i < n; ++i)
            if(++d[i] == BASE) d[i] = 0;
            else return;
        d[n++] = 1;
    }

    void operator += (const BigInteger &a) {
        if(a.n > n) n = a.n;
        int rem = 0;
        for(int i = 0; i < n; ++i) {
            int p = d[i] + a.d[i] + rem;
            if(p >= BASE) d[i] = p - BASE, rem = 1;
            else d[i] = p, rem = 0;
        }
        if(rem) d[n++] = rem;
    }

    void print() {
        printf("%d", d[n-1]);
        for(int i = n-2; i >= 0; --i)
            printf("%0*d", LOG_BASE, d[i]);
        printf("\n");
    }
} cOne[N+1], cZero[N+1];

int main() {
    for(int i = 1; i <= N; ++i) {
        cOne[i] = cOne[i-1];
        cOne[i] += cZero[i-1];
        cZero[i] = cOne[i];
        if(i % 2 == 0) ++cZero[i];
    }
    for(int n; scanf("%d", &n) == 1; cZero[n].print());
    return 0;
}

Code mẫu của ladpro98

program m00pair;
uses    math;
type    big=ansistring;
const   maxn=1001;
        fi='';
var     f:array[1..maxn] of big;
        n,i:longint;
        inp:text;

function sum(a,b:big):big;
var     x,y,s,carry,i:longint;
        c:big;

begin
        if length(a)<length(b) then c:=b
        else
        c:=a;
        carry:=0;
        while length(a)<length(b) do a:='0'+a;
        while length(b)<length(a) do b:='0'+b;
        for i:=length(a) downto 1 do
        begin
                x:=ord(a[i])-48;
                y:=ord(b[i])-48;
                s:=x+y+carry;
                carry:=s div 10;
                c[i]:=chr(s mod 10 + 48);
        end;
        if carry>0 then c:='1'+c;
        exit(c);
end;

procedure dp(i:longint);
var     j:longint;
begin
        if i>n then
        begin
                for j:=n+1 to i do
                f[j]:=sum(f[j-1],sum(f[j-2],f[j-2]));
                n:=i;
        end;

end;

begin
        assign(inp,fi);
        reset(inp);
        f[1]:='0';f[2]:='1';n:=2;
        while not eof(inp) do
        begin
                readln(inp,i);
                dp(i);
                writeln(f[i]);

        end;
        close(inp);
end.

Code mẫu của RR

{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=999;
type
  big=array[0..MAXN] of longint;
operator + (a,b:big) c:big;
var
  i,nho:longint;
begin
  fillchar(c,sizeof(c),0);
  c[0]:=max(a[0],b[0]); nho:=0;
  for i:=1 to c[0] do
    begin
      c[i]:=a[i]+b[i]+nho;
      if c[i]<10 then nho:=0
      else begin nho:=1; c[i]-=10; end;
    end;
  if nho=1 then begin inc(c[0]); c[c[0]]:=1; end;
end;
var
  f1,f2:text;
  n,test:longint;
  f00,f01:array[1..MAXN] of big;
  lt2:array[0..MAXN] of big;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1);
  close(f2);
end;
procedure init;
var
  i:longint;
begin
  lt2[0][0]:=1; lt2[0][1]:=1;
  for i:=1 to 999 do lt2[i]:=lt2[i-1]+lt2[i-1];
  f00[1][0]:=1;
  f01[1][0]:=1; f01[1][1]:=1;
  for i:=2 to 999 do
    begin
      f00[i]:=f01[i-1];
      f01[i]:=lt2[i-2]+f00[i-1];
    end;
end;
procedure print(var a:big);
var
  i:longint;
begin
  for i:=a[0] downto 1 do
    write(f2,a[i]);
  writeln(f2);
end;
begin
  init;
  openF;
  while not eof(f1) do
    begin
      readln(f1,n);
      print(f00[n]);
    end;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <string.h>

int main()
{
   // freopen("M00PAIR.in","r",stdin);
    int n;
    char c[1001][600];
    c[0][0]='0';
    c[0][1]='\0';
    c[1][0]='0';
    for(int i=2;i<=1000;i++)
    {
        int l,du;
        if(i%2==0) l=1;
        else l=-1;
        c[i][0]=((c[i-1][0]-48)*2+l)%10 + 48;
        du = ((c[i-1][0]-48)*2+l)/10;
        for(int j=1;j<strlen(c[i-1]);j++)
        {
             //if(i==11) printf("**%d**\n",du);
             c[i][j]=((c[i-1][j]-48)*2+du)%10 + 48;
             du = ((c[i-1][j]-48)*2+du)/10;
        }
        int m=i-1;
        if(du>0)
        {
        c[i][strlen(c[m])]=du+48;
        c[i][strlen(c[m])+1]='\0';
        }
        else c[i][strlen(c[m])]='\0';

      //  printf("%d\n",i);
    }
    int chay=0;
    while(scanf("%d",&n)>0&&n>0)
    {
        chay++;
       // if(chay>1)
       // printf("\n");
       // printf("%s\n",c[n]);
        for(int i=strlen(c[n])-1;i>=0;i--)
             printf("%c",c[n][i]);
        printf("\n");
    }
    //printf("%d",strlen(c[1]));
   // getch();
}

Code mẫu của ll931110

Program M00PAIR;
        Const
                input  = '';
                output = '';
                  maxn = 1000;
                  maxd = 40;
                  maxi = 35;
                remain = 1000000000000;
        Var
                p00,p01,p10,p11: array[1..maxn + 1,1..maxd] of qword;
                              p: array[1..maxd] of qword;
                              n: integer;
                          fi,fo: text;

Procedure openfile;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Assign(fo, output);
                        Rewrite(fo);
          End;

Procedure optimize;
          Var
                i,j: integer;
          Begin
                Fillchar(p00, sizeof(p00), 0);
                Fillchar(p01, sizeof(p01), 0);
                Fillchar(p10, sizeof(p10), 0);
                Fillchar(p11, sizeof(p11), 0);
                Fillchar(p, sizeof(p), 0);

                p[1]:= 1;
                p01[1,1]:= 1;
                For i:= 2 to maxn do
                  Begin
                        For j:= 1 to maxi do
                          Begin
                                p00[i,j]:= p00[i,j] + p01[i - 1,j];
                                If p00[i,j] >= remain then
                                  Begin
                                        p00[i,j + 1]:= p00[i,j + 1] + p00[i,j] div remain;
                                        p00[i,j]:= p00[i,j] mod remain;
                                  End;

                                p11[i,j]:= p11[i,j] + p10[i - 1,j];
                                If p11[i,j] >= remain then
                                  Begin
                                        p11[i,j + 1]:= p00[i,j + 1] + p00[i,j] div remain;
                                        p11[i,j]:= p11[i,j] mod remain;
                                  End;

                                p01[i,j]:= p01[i,j] + p00[i - 1,j] + p[j];
                                If p01[i,j] >= remain then
                                  Begin
                                        p01[i,j + 1]:= p01[i,j + 1] + p01[i,j] div remain;
                                        p01[i,j]:= p01[i,j] mod remain;
                                  End;

                                p10[i,j]:= p10[i,j] + p11[i - 1,j] + p[j];
                                If p10[i,j] >= remain then
                                  Begin
                                        p10[i,j + 1]:= p10[i,j + 1] + p10[i,j] div remain;
                                        p10[i,j]:= p10[i,j] mod remain;
                                  End;
                          End;

                        For j:= 1 to maxi do p[j]:= p[j] * 2;
                        For j:= 1 to maxi do if p[j] >= remain then
                          Begin
                                p[j + 1]:= p[j + 1] + p[j] div remain;
                                p[j]:= p[j] mod remain;
                          End;
                  End;
          End;

Procedure printresult;
          Var
                n,i,j,k: integer;
                      s: string;
          Begin
                While not eof(fi) do
                  Begin
                        Readln(fi, n);
                        If n = 1 then writeln(fo, 0) else
                          Begin
                                k:= maxi;
                                While p00[n,k] = 0 do dec(k);

                                Write(fo, p00[n,k]);
                                For i:= k - 1 downto 1 do
                                  Begin
                                    str(p00[n,i], s);
                                    For j:= 1 to 12 - length(s) do write(fo, 0);
                                    Write(fo, s);
                                  End;
                                  Writeln(fo);
                          End;
                  End;
          End;

Procedure closefile;
          Begin
                Close(fo);
                Close(fi);
          End;

Begin
        openfile;
        optimize;
        printresult;
        closefile;
End.

Code mẫu của khuc_tuan

// {$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.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.