C++

#include <cstdio>

#include <cstring>

 

using namespace std;

int N,dt[40];

int serch(int n){

    if(n==0)

        return 1;

    if(dt[n]!=-1)

        return dt[n];

    int re=0;

    if(n>=1){

        re+=serch(n-1);

    }

    if(n>=2){

        re+=serch(n-2)*2;

    }

    return re;

}

int main()

{

    memset(dt,-1,sizeof(dt));

    scanf("%d",&N);

    if(N%2==0){

        printf("%d",(serch(N)+serch(N/2)+serch(N/2-1)*2)/2);

    }else{

        printf("%d",(serch(N)+serch(N/2))/2);

    }

    return 0;

}