Форум Всеукраїнської інтернет-олімпіади NetOI

#include<iostream>

using namespace std;

#define D    100000000

class CBigNumber{
    int a[150],n;
public:
    inline void operator=(int x){
        for(n=0;x;x/=D)
            a[n++]=x%D;
    }
    inline void operator+=(CBigNumber&x){
        for(;n<x.n;a[n++]=0);
        a[n]=0;
        for(int i=0;i<x.n;++i){
            a[i]+=x.a[i];
            if(a[i]>=D)a[i]-=D,++a[i+1];
        }
        if(a[n])++n;
        else while(a[n-1]==0)--n;
    }
    inline void Print(){
        printf("%d",a[n-1]);
        for(int i=n-2;i>=0;--i)
            printf("%08d",a[i]);
    }
}F[6][2];

int n,x,y;
bool a[2][3];

inline CBigNumber& f(int y,int x){
    switch(y){
        case 4:return F[1][x&1];
        case 6:return F[3][x&1];
        case 7:return F[4][x&1];
        default:return F[y][x&1];
    }
}

inline void calc(){
    for(int j=0;j<3;++j)
        if(!a[1][j]){
            a[1][j]=true,calc();
            a[0][j]=true,calc();
            a[0][j]=false;
            if(j<2)if(!a[1][j+1])
                a[1][j+1]=true,calc(),
                a[1][j+1]=false;
            a[1][j]=false;
            return;
        }
    f(y,x)+=f((a[0][0]?1:0)|(a[0][1]?2:0)+(a[0][2]?4:0),x-1);
}

main(){
    cin>>n;
    f(0,1)=3;
    f(1,1)=2;
    f(2,1)=1,f(3,1)=1,f(5,1)=1,f(7,1)=1;
    for(x=2;x<=n;++x)
        for(y=0,f(7,x)=f(0,x-1);y<7;++y){
            if(y==4||y==6)continue;
            a[0][0]=a[0][1]=a[0][2]=false;
            a[1][0]=(y&1)!=0,a[1][1]=(y&2)!=0,a[1][2]=(y&4)!=0;
            f(y,x)=0,calc();
        }
    f(0,n).Print();
    putchar('\n');
    return 0;
}

{$I-,Q-,R-,S-}
Const osn=1000000;
TYpe lmas=array[0..134]of longint;
VAR m                                                           :integer;
    a0,a1,a2,a3,a4,a5,a6,a7,a01,a11,a21,a31,a41,a51,a61,a71,pr  :lmas;

Procedure INIT;
begin
  readln(m);
  a0[0]:=1; a0[1]:=1;
  a1[0]:=1; a1[1]:=1;
  a2[0]:=1; a2[1]:=1;
  a3[0]:=1; a3[1]:=1;
  a4[0]:=1; a4[1]:=1;
  a5[0]:=1; a5[1]:=2;
  a6[0]:=1; a6[1]:=2;
  a7[0]:=1; a7[1]:=3;
end;
Procedure OUT;
var i,k :integer;
    s   :string[10];
begin
  write(a7[a7[0]]);
  for i:=a7[0]-1 downto 1 do begin
    str(a7[i],s);
    k:=6-ord(s[0]);
    while k<>0 do begin write(0); dec(k); end;
    write(a7[i]);
  end;
  writeln;
end;

Procedure CORRECTION(Var k:lmas);
var i   :integer;
begin
  i:=1;
  while i<=k[0] do begin
    inc(k[i+1],k[i] div osn); k[i]:=k[i] mod osn;
    if (i=k[0])and(k[i+1]>0) then inc(k[0]);
    inc(i);
  end;
end;
Function SUMA(a,b,c,d,e,f,g,h,i,j,k,l:lmas):lmas;
var ii   :integer;
    t    :lmas;
begin
  fillchar(t,sizeof(t),0);
  t[0]:=a[0];
  if b[0]>t[0] then t[0]:=b[0];
  if c[0]>t[0] then t[0]:=c[0];
  if d[0]>t[0] then t[0]:=d[0];
  if e[0]>t[0] then t[0]:=e[0];
  if f[0]>t[0] then t[0]:=f[0];
  if g[0]>t[0] then t[0]:=g[0];
  if h[0]>t[0] then t[0]:=h[0];
  if i[0]>t[0] then t[0]:=i[0];
  if j[0]>t[0] then t[0]:=j[0];
  if k[0]>t[0] then t[0]:=k[0];
  if l[0]>t[0] then t[0]:=l[0];
  for ii:=1 to t[0] do t[ii]:=a[ii]+b[ii]+c[ii]+d[ii]+e[ii]+f[ii]+g[ii]+h[ii]+i[ii]+j[ii]+k[ii]+l[ii];
  CORRECTION(t);
  SUMA:=t;
end;
Procedure SOLVE;
var i   :integer;
begin
  for i:=2 to m do begin
    a71:=a7; a61:=a6; a51:=a5; a41:=a4; a31:=a3; a21:=a2; a11:=a1; a01:=a0;
    a0:=a71;
    a1:=SUMA(a71,a61,pr,pr,pr,pr,pr,pr,pr,pr,pr,pr);
    a2:=SUMA(a71,a41,pr,pr,pr,pr,pr,pr,pr,pr,pr,pr);
    a3:=SUMA(a71,a51,pr,pr,pr,pr,pr,pr,pr,pr,pr,pr);
    a4:=SUMA(a51,a61,a71,a21,pr,pr,pr,pr,pr,pr,pr,pr);
    a5:=SUMA(a71,a71,a61,a41,a31,pr,pr,pr,pr,pr,pr,pr);
    a6:=SUMA(a71,a71,a41,a51,a11,pr,pr,pr,pr,pr,pr,pr);
    a7:=SUMA(a71,a71,a71,a51,a41,a61,a31,a21,a11,a01,a61,a51);
  end;
end;

BEGIN
  INIT;
  SOLVE;
  OUT;
END.