## 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);
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;
}


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
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
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
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 print();
function clone : BigNum;
end;

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

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][0][1] := sl.clone;
end;
while not eof do
begin
// n := -1;